[MLton] Re: [Haskell-cafe] fastest Fibonacci numbers in the West
Matthew Fluet
fluet@cs.cornell.edu
Thu, 27 Jan 2005 13:33:17 -0500 (EST)
> > 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";