ANN: HIntegerByInt

[Isaac Dupree]

Stefan O'Rear wrote:
> On Mon, Aug 13, 2007 at 03:21:54PM -0700, John Meacham wrote:
>> On Sat, Aug 11, 2007 at 12:09:44PM -0300, Isaac Dupree wrote:
>>> BTW: I estimate that it took me about two solid weeks of time, more than 
>>> I had originally intended to spend :)
>>>
>>>
>>> I think using CPP will prove important, but makes it harder to test in 
>>> Hugs... should I use Cabal if I want to use Hugs with haskell+cpp code?
>> I think if you were willing to use what is provided by the FFI
>> extension, you could make some signifigant improvements without
>> resorting to CPP. mainly, you could use unsigned arithmetic and have
>> access to bit operations.
>>
>> I was thinking a representation like
>>
>> data Integer = Integer !Bool Rest
>> data Rest = Digit !Word Rest | End
>>
>> where the Bool indicates the sign, and the rest are the base-wordsize
>> digits. It would also be possible to just use a sign bit in the number
>> of course. that unboxed strict Word should make a big difference.
> 
> You might also try
> 
> data Integer = Pos !Word | Neg !Word | Big !Word Integer
> 
> since the incremental penalty of 3 constructors is quite small, and it
> eliminates a few indirections.
> 
> (Note: You have to actually specify -funbox-strict-fields for the ! to
> do much good.)

I use the {-# UNPACK #-} pragma where I want that effect.

Simpler representation = simpler for a compiler to output. (although I 
could easily provide a Haskell module containing (Integer -> (that 
thing's shape) ) for compilers to include.)  No-FFI is particularly 
important (this is NOT GMP), but I don't think I need FFI - the compiler 
just has to support it somehow - to use Data.Word.

I do suspect that storing in two's complement style / with separate 
sign, might be more efficient for some operations.  (I'm particularly 
concerned that small numbers should be fast, so that Int doesn't have to 
be used all over the place just for speed reasons. Since my format 
requires two "case"s to determine that an Integer is a small number, 
_if_ that is the most costly operation, it might be improved)  And of 
course any of you can try the variant implementations you propose, if 
you want to put in the work on it!  I'm not interested for a long time.

The more interesting-looking part to me now is seeing what a good 
mechanism is for using these implementations in compilers is (which is 
not entirely obvious to me).  I'm

BTW. base-wordsize digits are not very good for addition speed, 
depending... Even GMP uses a somewhat smaller base than that, I believe.

Look:
* The compiler only has to output lists (it already must do string 
literals), and Ints, in compiled programs.
* No types outside Haskell98 need to be implemented.
* The Int does not need to be a certain large size, does not need to be 
two's-complement bits (except for the extension class Bits which seems 
to assume two's complement implicitly for signed numbers), and does not 
need to have any particular overflow behavior.

I'm not the one with the energy to make compromises between performance 
and portability.  Seeing something like this in Jhc should be 
interesting and there is where decent-good performance will be wanted. 
I know my implementation is quite inferior performance to GMP, in _GHC_ 
:)  I still think GMP is the place to go for the highest, most 
well-rounded performance. (Although "We will release 4.2.2 in spring 
2007." did not come to pass, and still appears on gmplib.org)

I wonder if there's any way (Jhc) compiler optimizations could transform 
a strict inductive data into a UArray sort of representation, since that 
representation is probably more efficient for Integers...

Isaac