Bignums in Haskell
morazanm at gmail.com
Tue Jun 21 19:39:15 EDT 2005
This is a rather interesting question. Most "efficient"
implementations use array-based representations for bignums that are
mutable. The use of mutable arrays appears to be justified, because of
divide-and-conquer multiplication and division algorithms (e.g.
Karatsuba) that perform these operations in place. The problem,
however, is not this straighforward. Array-based implementations
require copying bigits into the array. A list-based implementation
simply points to the rest of the bignum avoiding any copying.
If bignums are immutable structures (as in a true functional data
structure), then we should not be surprised if list-based
representations are as good or better than array-based
implementations. In this case, arrays are forced to copy bigits to new
memory locations while lists can continue to point to pieces of a
bignum. To avoid excessive memory allocation for pure bignums
real-time garbage collection on bignum operations can be used.
It is certainly a rich and interesting line of research. It also
appears to me that having native support for bignums is desirable. It
would certainly make using bignum libraries seamless.
On 6/21/05, karczma at info.unicaen.fr <karczma at info.unicaen.fr> wrote:
> John Meacham writes:
> > I wonder if it would be feasable to implement arbitrary precision
> > integers in pure haskell. unboxed values would probably want to be used
> > in some places for speed and it would be very motivating to improve
> > ghc's optimizer. There should be no reason manually unboxed haskell code
> > should compile slower than C.
> Of course, bignums (integers) can be quite nicely implemented in Haskell,
> this is btw. a known student exercise. The implementation is nice, elegant,
> etc., but the efficiency... This is not only having unboxed chunks, but
> also the global policy of memory allocation. Putting number chunks in lazy
> lists involves a substantial overhead. I am not sure how slow it will be,
> since our pedagogic games didn't care at all, but we can try to benchmark
> it one day...
> Jerzy Karczmarczuk
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users