ANN: HIntegerByInt
Isaac Dupree
isaacdupree at charter.net
Sat Aug 11 11:09:44 EDT 2007
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
More information about the Libraries
mailing list