I want to present 3 algorithms of computing Fibonacci numbers written in Haskell: exponential, linear and logarithmic.

1. Brute-force algorithm

fibo 0 = 0
fibo 1 = 1
fibo x = fibo (x-1) + fibo(x-2)

This algorithm is easy to code and analyse 😀
Unfortunately, due to exponential complexity, computing even 30th element of sequence took some time.

2. Linear algorithm

fibo n = head (fibo2 n)
fibo2 0 = [0,0]
fibo2 1 = [1,0]
fibo2 n = [f1+f2,f1] where (f1:f2:r)  = fibo2 (n-1)

Algorithm can quickly compute up to 15000th element – then I have stack overflow in Hugs environment.

3. Logarithmic solution
There is formally faster solution, based on Binet formula and fast exponentiation algorithm. It fails for n larger than 75 because of arithmetics errors.

fibo x = round(if x==0 then 0 else (fibo2(x, 1, (1+sqrt(5))/2) - fibo2(x, 1, (1-sqrt(5))/2))/sqrt(5))
fibo2 (0,y,z) = y
fibo2 (x,y, z) = 
    fibo2 (div  x 2, 
	(if mod x 2 == 1 then  y*z else y),
	z*z)