Bignums in Haskell

[Simon Marlow]

On 21 June 2005 22:52, John Meacham wrote:

> On Tue, Jun 21, 2005 at 03:48:44PM +0100, Simon Peyton-Jones wrote:
>> 
>>>>> Do any of you have insight into why GHC uses GMP as opposed to
>>>>> another library for arbitrary precision numbers?
>>>> 
>> ...
>>> 
>>> Right - that's three reasons to use it.  Some reasons *not* to use
>>> it are: it has an awkward license, it's big, it needs updating, and
>>> we run into problems when the Haskell program wants to use GMP
>>> itself via the FFI (it's possible by essentially renaming
>>> everything in our local copy of GMP so it doesn't conflict, but we
>>> haven't done that). 
>> 
>> In fact, we have long wanted to replace GMP with another library for
>> exactly these reasons.  It's a nice, well-specified, self-contained
>> project, which is just waiting for someone to step up and do it.  Of
>> course, we'd only want to replace GMP if the alternative was also
>> fast and reliable. 
>> 
>> If anyone is interested in tackling this, let us know!
> 
> 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.

GHC currently lacks some of the primitives that you'd need to build an
efficient bignum library (eg. add with carry), but you could add these.
Also, the fact that GMP contains hand-tuned assembly versions of several
operations makes me skeptical that you could get the same performance
from GHC-compiled Haskell.  However, getting close might be good enough.

Cheers,
	Simon