4 ms·
Naive implementation might be: fib :: Integer -> Integer fib x = truncate $ ( 1 / sqrt 5 ) * ( phi ^ x - psi ^ x ) where phi = ( 1 + sqrt 5 ) / 2
by freyrs3 13y ago
Naive implementation might be:
fib :: Integer -> Integer
fib x = truncate $ ( 1 / sqrt 5 ) * ( phi ^ x - psi ^ x )
where
phi = ( 1 + sqrt 5 ) / 2
psi = ( 1 - sqrt 5 ) / 2
- fhars 13y agoAlas, that version is only correct up to x = 25, because *Main> 1 / sqrt 5 * (((1 + sqrt 5) / 2) ^ 26 - ((1 - sqrt 5) / 2) ^ 26) 121392.99999999999 happens to be just on the wrong side of the truncate.