http://stackoverflow.com/questions/4327846/calculating-fibonacci/4328194#4328194 http://stackoverflow.com/questions/4327846/calculating-fibon... It's straightf

http://stackoverflow.com/questions/4327846/calculating-fibonacci/4328194#4328194 http://stackoverflow.com/questions/4327846/calculating-fibon... It's straightforward (if messy) to calculate two rationals exactly, then approximate √5 to within certain error bounds. I wrote some code which does this, just as an experiment... and it's unbearably slow. Just try it. import Control.Arrow import Data.Ratio newtype Matrix2 a = Matrix2 (a, a, a, a) deriving (Show, Eq) instance (Num a) => Num (Matrix2 a) where Matrix2 (a, b, c, d) * Matrix2 (e, f, g, h) = Matrix2 (a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h) fromInteger x = let y = fromInteger x in Matrix2 (y, 0, 0, y) fib n = let Matrix2 (_, x, _, _) = Matrix2 (1, 1, 1, 0) ^ n in x binom n = scanl (\a (b, c)-> a*b `div` c) 1 $ takeWhile ((/=) 0 . fst) $ iterate (pred *** succ) (n, 1) evens (x:_:xs) = x : evens xs evens xs = xs odds (_:x:xs) = x : odds xs odds _ = [] iterate' f x = x : (iterate f $! f x) powers b = iterate (b *) 1 esqrt e n = x where (_, x):_ = dropWhile ((<=) e . abs . uncurry (-)) $ zip trials (tail trials) trials = iterate (\x -> (x + n / x) / 2) n fib' n = (a, b) where d = 2 ^ n a = sum (zipWith (*) (odds $ binom n) (powers 5)) % d b = sum (zipWith (*) (evens $ binom n) (powers 5)) % d fib2 n = numerator r `div` denominator r where (a, b) = fib' n l = lcm (denominator a) (denominator a) r = a + esqrt (1 % l) (b * b / 5) + 1 % 2