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

[William Lee Irwin III]

At some point in the past, I wrote:
>> For the moment, mlton-generated binaries crash computing fib (10^8-1),

On Thu, Jan 27, 2005 at 09:09:10AM -0500, Matthew Fluet wrote:
> As one of the MLton developers, I'm quite saddened to here it. ;-)
> Seriously, if you are getting a segfault or related crash, please report a
> bug.  If you are getting an unexpected uncaught exception, we would still 
> be interested in hearing more details.
> Given that you successfully compute fib (10^7-1), it is clear that you are 
> computing the result at IntInf.int.  I don't see any reason why going up 
> an order of magnitude would cause any problems.

This was originally reported by Excedrin on freenode #haskell; I
managed to reproduce the issue locally. He claimed that he was going
about reporting it properly and I've deferred completely to him on this.

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.

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.


-- wli