Dan Weber (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} mirrorlynx) wrote,@ 2005-04-25 20:24:00 |
|
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)
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)
