April 7th, 2008:

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))

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))