[MLton] Re: [Haskell-cafe] fastest Fibonacci numbers in the West

[Wesley W. Terpstra]

On Thu, Jan 27, 2005 at 09:47:50AM -0500, Matthew Fluet wrote:
> > In all honesty, I'd expect runtime crashes due to e.g. unhandled
> > allocation failures in lower-level arbitrary-precision arithmetic
> > libraries relied upon by the runtime upon to be normal for exceedingly
> > large integer results, so I don't think it's significant, but he did.
> 
> We agree with your opinion, which is why the MLton implementation of the
> Basis Library explicitly performs the allocation for all IntInf.int
> objects (as a word vector, invoking the GC when necesary), before handing
> off to the GnuMP library.  The lower-level library should never need to
> perform allocation; hence, there are no unhandled allocation failures.

If it is an allocation problem, it's not due to memory pressure. With the
tail-recursive exp function in my version, the program uses less than 100MB
of RAM on a machine with 1GB.

> > There is actually more bizarre news. The naive implementation of the
> > Fibonacci recurrence in mlton actually outperforms my O(lg(n))
> > bitreversal etc. algorithm implemented in Haskell up to around 10^5-1.
> > The ability of the efficient runtime to compensate for naive algorithms
> > in this case is a particularly promising result for mlton.

bitreversal? Are you referring to unrolling the exp recursion or a method
for computing the FFT? I would be curious to know your algorithm.

-- 
Wesley W. Terpstra