Bignums in Haskell

[Simon Peyton-Jones]

There's nothing inherently imperative about bignums.  The current
algorithms may have an imperative flavour, but that may be partly
because that's what suits the implementation language.  If the
algorithms are divide-and-conquer, perhaps a tree representation would
work very nicely.

And even in the imperative case there is no reason in principle why a
runST-encapsulated imperative algorithm should be slower than C ---
although at the moment GHC does not do a consistently good job of
compiling imperative code.

So I rather agree with John: implementing bignums in Haskell, and trying
to make an efficient implementation based on the state of the art on the
numerical side (as opposed to just writing the first code that comes
into your head), would be an interesting project for someone to try.  It
might also expose useful optimisations that are missing in GHC or jhc.

It's essential to optimise the 'small bignum' case.  In practice, most
"bignums" easily fit in 32 bits.

Simon

| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org
[mailto:glasgow-haskell-users-
| bounces at haskell.org] On Behalf Of Marco Morazan
| Sent: 22 June 2005 00:39
| To: karczma at info.unicaen.fr
| Cc: glasgow-haskell-users at haskell.org
| Subject: Re: Bignums in Haskell
| 
| 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
| >
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users