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

[William Lee Irwin III]

At some point in the past, I wrote:
>>> 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.

On Thu, Jan 27, 2005 at 04:30:09PM +0100, Wesley W. Terpstra wrote:
> bitreversal? Are you referring to unrolling the exp recursion or a method
> for computing the FFT? I would be curious to know your algorithm.

Unrolling the exp recursion. It may be productive for me to look for
bit testing primitives, since that would save the trouble of
constructing a list. The bitreversal method won out vs. various
alternatives (e.g. matrices) in Haskell-vs-Haskell benchmarks.

It may be feasible to assume the input is a small integer, since memory
constraints on systems will generally prevent the computation from
succeeding for even relatively small numbers, in which case there are
generally bit testing primitives available.


-- wli