Bignums in Haskell

[Marco Morazan]

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.

Best wishes,

Marco

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
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>