Bignums in Haskell

[John Meacham]

On Wed, Jun 22, 2005 at 12:47:02AM +0200, 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...
> 

I should mention I have an ulterior motive for encouraging this. jhc
currently has no bignum support. (Integer is the same size as the native
intmax_t) However, I'd like to support them by implementing them in
haskell directly and then attempting to improve jhc to the point where
they run fast enough. If the work can be shared with ghc then so much
the better.

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈