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@haskell.org
[mailto:glasgow-haskell-users-
| bounces@haskell.org] On Behalf Of Marco Morazan
| Sent: 22 June 2005 00:39
| To: karczma@info.unicaen.fr
| Cc: glasgow-haskell-users@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@info.unicaen.fr
participants (1)
-
Simon Peyton-Jones