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

[Matthew Fluet]

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

Hmm... I seem to be running on gmp-4.1.2 on the Linux machines I ran the 
tests with.

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

By having wesley compute  exp (fib, n + 1)  instead of  exp (fib, n).
So, my code looks like

----------------------------------------------------------------------
fun eprint s =
   (TextIO.output (TextIO.stdErr, s);
    TextIO.flushOut TextIO.stdErr)

local
   type iinf = IntInf.int
   type iinf2 = iinf * iinf

   fun unfold n =
      if n = 0 then []
	 else 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)) : iinf2 =
      if p 
	 then (f*(f+2*g), f*f+g*g) 
	 else (f*f+g*g, g*(2*f-g))
in
   fun william_fib (n : int) : iinf = 
      #2 (foldl crunch (1, 0) (unfold n))
end

local 
   type iinf = IntInf.int
   type iinf2 = iinf * iinf
   type iinf2x2 = iinf2 * iinf2

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

   fun expt (m, e, a) : iinf2x2 =
      if e = 0
	 then a
      else if e = 1
	 then mul (a, m)
      else expt (mul (m, m), e div 2, expt (m, e mod 2, a))

   fun exp (m, e) : iinf2x2 = 
      expt (m, e, ((1, 0), (0, 1)))
     
   val fib = ((0, 1), (1, 1))
in
   fun wesley_fib (n : int) : iinf =
      #1 (#1 (exp (fib, n + 1)))
end

val n = ((valOf o Int.fromString o hd o CommandLine.arguments) ())
        handle Option => (print ("usage: fib n\n");
			  OS.Process.exit OS.Process.failure)

val () = eprint "Starting william_fib of n\n"
val william_f_n = william_fib n
val () = eprint "Finished william_fib of n\n"

val () = eprint "Starting wesley_fib of n\n"
val wesley_f_n = wesley_fib n
val () = eprint "Finished wesley_fib of n\n"

val () =
   if william_f_n = wesley_f_n
      then eprint "william_fib and wesley_fib agree\n"
      else eprint "william_fib and wesley_fib disagree\n"

val () = eprint "Starting IntInf.toString of william_f_n\n";
val william_f_n_str = IntInf.toString william_f_n
val () = eprint "Finished IntInf.toString of william_f_n\n";

val () = eprint "Starting IntInf.toString of wesley_f_n\n";
val wesley_f_n_str = IntInf.toString wesley_f_n
val () = eprint "Finished IntInf.toString of wesley_f_n\n";

val () = eprint "Starting print of william_f_n_str\n";
val () = print william_f_n_str
val () = print "\n"
val () = eprint "Finished print of william_f_n_str\n";

val () = eprint "Starting print of wesley_f_n_str\n";
val () = print wesley_f_n_str
val () = print "\n"
val () = eprint "Finished print of wesley_f_n_str\n";