Dan Weber's Journal

Fibonacci : Haskell edition
On my run through the haskell language, I implement my hello world like program for every language which is fibonacci.

Here is my haskell implementation:

diffsquares a b = 2*n*b + n^2
where n = (a-b)

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib 2 = 1

fib n | (n `mod` 2) == 0 = diffsquares (fib ((n `div` 2) + 1)) (fib ((n `div` 2) - 1))
| otherwise = (fib (n `div` 2))^2 + (fib ((n `div` 2) + 1))^2

Diffsquares is a little differencing squares hack only squaring the distance between the two numbers. The fibonacci implementation is based on fib(n)^2 + fib(n+1)^2 = fib(2n+1)

Advertisement