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)