Mathew Mills
-- fib x returns the x'th number in the fib sequence fib :: Integer -> Integer fib x = let phi = ( 1 + sqrt 5 ) / 2 phi' = ( 1 - sqrt 5 ) / 2 in truncate( ( 1 / sqrt 5 ) * ( phi ^ x - phi' ^ x ) )
-- Seems pretty quick to me, even with sqrt and arbitrarily large numbers.
You don't actually need the part with phi'^x. Since |phi'| < 1, phi'^x gets small fast as x increases. In fact |phi'^x| is always smaller than 1/2, so -phi'^x in the expression above can be replaced by +0.5. Unfortunately with arbitrarily large numbers it gets the answer wrong. "Arbitrarily large" in this case is smaller than 100.
fib 100 354224848179261800448
The correct answer is 354224848179261915075 The relative error is very small, so it is a good approximation.