Programming Praxis – Fibonacci Numbers

In today’s Programming Praxis we have to provide three different methods of calculating the ever-popular Fibonacci numbers; one exponential, one linear and one logarithmic. Let’s get started, shall we?

Some imports:

import Data.List
import Criterion.Main

The naive exponential solution is trivial:

fibexp :: Int -> Integer
fibexp 0 = 0
fibexp 1 = 1
fibexp n = fibexp (n - 1) + fibexp (n - 2)

For the linear method, we use the textbook lazy evaluation-based approach:

fiblin :: Int -> Integer
fiblin n = fibs !! n where fibs = 0:1:zipWith (+) fibs (tail fibs)

The logarithmic solution requires two helper functions: the matrix multiplication function from a previous exercise and a way of raising a matrix to a power in log(n) time.

mult :: Num a => [[a]] -> [[a]] -> [[a]]
mult a b = [map (sum . zipWith (*) r) $ transpose b | r <- a]

matrixpower :: [[Integer]] -> Int -> [[Integer]]
matrixpower m 1 = m
matrixpower m n = (if even n then id else mult m) $
                  matrixpower (mult m m) (div n 2)

All that’s left to do to calculate Fibonacci numbers is raise the given matrix to the correct power and taking the lower-left element.

fiblog :: Int -> Integer
fiblog 0 = 0
fiblog n = matrixpower [[1,1],[1,0]] n !! 1 !! 0

To benchmark the different solutions, we use the Criterion library.

main :: IO ()
main = defaultMain [bench "exp" $ nf fibexp 25
                   ,bench "lin" $ nf fiblin 25000
                   ,bench "log" $ nf fiblog 25000

This gives the following timings: 174 ms for the exponential version, 69 ms for the linear one and 643 microseconds for the logarithmic solution, so we get a 100-fold speedup between the linear and logarithmic version at the cost of a factor of 6 increase in code size. Not a bad trade-off.

About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: