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

[Stephen Weeks]

> 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.

Excedrin reported the bug on #sml last night.  I saw it and ran a
couple of tests.  The bug he reported was for William's version of the
code with an input of 99999999.  I was not able to reproduce the bug
using the gmp-4.1.2-2 RPM on my Linux machine.  I left a version
running overnight on another machine, which runs gmp-4.0.1-3.  That
one failed to terminate after 10 hours.  It is looking more and more
like a bug in some versions of GnuMP.

I ran the versions that William and Wesley sent to this list on the
input 25999999, using gmp-4.1.2-2.  Both terminated normally.
Wesley's produced a 5,433,679 byte output file in 85 seconds, while
William's produced a 5,433,680 byte output file in 50 seconds.  Both
used semispaces under 100M and had GC time at 0.1% of total time
(i.e. it doesn't stress the runtime at all).  I also compiled them
with -debug true (which does lots of assertion checking in the C
code), and they still terminated normally.

I suspect the difference in output file sizes is an off by one error
in the index of the number being printed.  I'm curious how Matthew got
them to agree.  Below is the code that I used to compare them -- it
fails with "not equal" for any input value.

----------------------------------------------------------------------

fun william n =
   let
      fun unfold 0 = []
	| unfold n = let val ((q:int), (r:int)) = (n div 2, n mod 2)
		     in (unfold q) @ [if r = 1 then true else false]
		     end
      fun crunch (p, (f, g)) =
	 if p then (f*(f+2*g), f*f+g*g) else (f*f+g*g, g*(2*f-g))
      fun myfib n = #2 (foldl crunch (1, 0) (unfold n))
   in
      myfib n
   end

fun wesley n =
   let
      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 ((a, b), (c, d)) = exp (fib, n)
   in
      a
   end

val n = valOf (Int.fromString (hd (CommandLine.arguments())))
val () = print "starting wesley\n"
val wesley = wesley n
val () = print "starting william\n"
val william = william n
val () = print "comparing\n"
val () =
   if wesley = william
      then ()
   else raise Fail "not equal"
val () = print "converting to decimal\n"
val s = LargeInt.toString wesley
val () = print "printing\n"
val () = print s
val () = print "\n"