Am Donnerstag, 27. Januar 2005 06:08 schrieb 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.
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.
Obviously, your machine is significantly faster than mine. On mine, fib (10^6) takes a little under two minutes, fib (10^7-1) I ^C-ed after twenty. I think ,more readable than 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)) would be unfoldl f x = case f x of Nothing -> [] Just (q,r) -> unfoldl f q ++ [r] divs 0 = Nothing divs k = Just (n `quotRem` 2) -- this has no influence on performance, since it's optimized anyway.
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.
I thought, I'd do it in the ring of integers in Q(sqrt(5)), code attached, this was a whiff faster for n = 700000 on my machine, a whiff slower for n = 10^6 -- any idea how that may come?
-- wli
Daniel