Rotating Header Image


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))
Be Sociable, Share!

One Comment

  1. stbuehler says:

    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)

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>