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