ANN: HIntegerByInt

[Isaac Dupree]

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?


Bulat Ziganshin wrote:
> Hello Isaac,
> 
> Friday, August 10, 2007, 7:56:25 PM, you wrote:
> 
>>    The internal format is (currently) a list([]) of Ints
> 
> my first thought is that using list of large chunks as in lazy
> bytestrings may improve efficiency in future

My first aim is portability, as Yhc demonstrated it could be helped by a 
portable Integer that is usually within the size of an Int.  I hated the 
idea that Int was being hackily used in place of Integer :)

For very large numbers, that (i.e. unboxed-array equivalents) would be 
more memory- as well as possibly speed efficient.  Almost all the 
operations in my implementation are defined inductively, not knowing the 
exact size of the result in advance, so that would be somewhat different.

One *interesting* aspect of the format I used is that unbalanced-size 
addition (and .&., .|.) are on average O(min(m,n)), because the tail of 
the list can stay the same except for carrying. e.g. 3 + 
2789234879453889743578934589893459834589345898945378974358798973487...
is about as fast as (3 + 4).  (Note that this asymptotic behavior will 
only actually be true in my implementation when my version of assertions 
are turned off, which verify that each generated integer is valid list 
format.  Also it does not work for the second argument of subtraction 
(nor negate, abs, xor) because negation really does have to change the 
whole list, given its current format (hmm... abs could short-circuit if 
it sees its argument is positive, I suppose).)

Johm Meacham wrote:
 > Excellent! this has always been a project I wanted to do in the back
 > of my mind. I will likely make it the default Integer implementation
 > for jhc. I look forward to the fun compiler optimizations it will
 > inspire to make it speed comparable to gmp

I can imaging speed near GMP for small-to-moderate size numbers, but GMP 
implements LOTS of algorithms as well as a number of sophisticated 
low-level foundations to make itself very fast.  One "advantage" we have 
is if we're only trying to implement the basic Integer algorithms... 
Anyway I would be quite happy even with a Haskell implementation that 
only works very fast for up to, say a few-hundred-digit(base 10) 
numbers, which I can imagine we might be able to manage. (GMP 4.2.x in 
my experience starts getting very slow for 1000-10000 digit(base 10) 
numbers and up.)  GMP development goes on and, well, *I'm* not that 
interested in duplicating it - I prefer the idea of one powerful bignum 
implementation to be perfected.  (GMP's implementation code is not very 
readable to an outsider - I've tried a little - I'd prefer to win on 
understandability in Haskell, but as you say, compiler optimizations 
have the *potential* to really help the speed of a readable implementation.)



Isaac