# [Haskell] Fast computation of Fibonacci sequence

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