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

[Wesley W. Terpstra]

--TB36FDmn/VVEgNH/
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Thu, Jan 27, 2005 at 09:09:10AM -0500, Matthew Fluet wrote:
> > For the moment, mlton-generated binaries crash computing fib (10^8-1),
> 
> As one of the MLton developers, I'm quite saddened to here it. ;-)

I can confirm this bug independently; attached is fib.sml.
./fib 99999999 segfaults as he mentioned.

Since I doubt he used exactly the same algorithm, this is probably just a
problem with the sheer size of the computed numbers. This program completes
for 10^7-1 in 11 seconds (faster machine).

In fact, my suspicion (unverified) is a bug in libgmp's conversion to base
10 during the output phase. This is a very hard thing to do well. My
reasoning is that the program takes longer as you grow the number beyond 
the crash point, but always segfaults before output.

The program works for 
	./fib 19999999
and creates a 4MB file, but crashes for
	./fib 25999999

-- 
Wesley W. Terpstra

--TB36FDmn/VVEgNH/
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="fib.sml"

open LargeInt
fun mul (((a, b), (c, d)), ((u, v), (w, x))) =
  ((a*u + b*w, a*v + b*x), (c*u + d*w, c*v + d*x))

open Int
fun expt (m, 0, a) = a
  | expt (m, 1, a) = mul (a, m)
  | expt (m, e, a) = expt (mul (m, m), e div 2, expt (m, e mod 2, a))
fun exp (m, e) = expt (m, e, ((1, 0), (0, 1)))

val fib = ((0, 1), (1, 1))
val n = (valOf o fromString o hd o CommandLine.arguments) ()
val ((a, b), (c, d)) = exp (fib, n)
val () = print (LargeInt.toString a ^ "\n")

--TB36FDmn/VVEgNH/--