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

**William Lee Irwin III
**
wli@holomorphy.com

*Thu, 27 Jan 2005 07:35:30 -0800*

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