[Haskell-cafe] fastest Fibonacci numbers in the West

[William Lee Irwin III]

Inspired by a discussion on freenode #haskell, I tried to write the
fastest Fibonacci number function possible, i.e. given a natural
number input n to compute F_n.

mlton seems to enjoy substantially better speed despite equivalent
algorithms; it may be enlightening to determine the causes of this,
at least for those concerned about performance and the inner workings
of the Haskell runtime system(s). In general, I am not usually very
concerned about performance, nor am I in this case. But it's something
of a mindless microbenchmark or similar.

The things I'd normally think of to speed this up would be getting
some primitives to find the highest bit of an integer (floor . lg)
and to test a given bit of an integer (something vaguely like
fromEnum . fromIntegral . (`mod` 2) . (/2^k)), both in some lightweight
O(1) with low-hidden-constant manner. This doesn't appear to be a factor
in the testing I did, as they're largely 1:1 translations of each other.
Still, such things would be useful in various other algorithms, of far
greater importance than this one.

For the moment, mlton-generated binaries crash computing fib (10^8-1),
and there is a 6:1 speed difference for fib (10^7-1) between the two,
where mlton-generated binaries take just under 1 minute, and ghc-
generated binaries take just under 6 minutes.

Anyway, thoughts on how to improve all this from the programmer's
point of view, or otherwise explaining what's going on or ameliorating
whatever effect is at work here would be appreciated.


-- wli
-------------- next part --------------
module Main where
import System.Environment
import Data.List

fib n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
	where
		unfoldl f x = case f x of
				Nothing -> []
				Just (u, v) -> unfoldl f v ++ [u]
		divs 0 = Nothing
		divs k = Just (uncurry (flip (,)) (k `divMod` 2))
		fib' (f, g) p	| p = (f*(f+2*g), f^2 + g^2)
				| otherwise = (f^2+g^2, g*(2*f-g))

main = getArgs >>= mapM_ (print . fib . read)
-------------- next part --------------
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))

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

val _ = print (IntInf.toString (myfib n) ^ "\n")