Mathew Mills <[EMAIL PROTECTED]> writes: > -- 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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
