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)