Bignums in Haskell

Marco Morazan morazanm at
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.

Best wishes,


On 6/21/05, karczma at <karczma at> 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

More information about the Glasgow-haskell-users mailing list