Next month I start at Google in Zurich. Been busy with trying to finish my phd, though it seems I will still have some writing left to do after I start my new job. Anyways, I’m definitely excited about this opportunity.
The fact I’ve been busy explains the silence on my blog. But here, in the spirit of A Faster Fibonacci here is a quick Haskell version. I will leave the explanation for the other blog post. Basically the execution is quadratic, and memoization is used to speed it up even more by removing duplicate calculations:
module Main where
import Data.Array
fib n = arr ! n
where arr = array (0,max 2 n) $ [(0,0), (1,1), (2,1)] ++
[(i, val i) | i <- [3..n]]
val i = let x = i `div` 2
in (arr ! x) * (arr ! (i - x - 1)) + (arr ! (x + 1)) * (arr ! (i - x))
for the calculation of a single entry the matrix multiplication was faster on my machine (ghci):
fib n = let (_,f,_,_) = mexp (1,0,0,1) (0,1,1,1) n in f where
matmult (a1,a2,a3,a4) (b1,b2,b3,b4) = (a1*b1+a2*b3, a1*b2+a2*b4, a3*b1+a4*b3, a3*b2+a4*b4)
mexp r m 0 = r
mexp r m n = mexp (if n `mod` 2 == 1 then matmult r m else r) (matmult m m) (n `div` 2)