G'day all. Quoting jerzy.karczmarczuk@info.unicaen.fr:
There is one solution missing there (unless I skipped it) fib n=((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5 If some of you complain that this is real, not integer, please remember that Leonardo of Pisa thought of applying this to rabbits. Well, rabbits are not integers, they eat carrots and have long ears. They are real thing.
As noted, floating-point arithmetic diverges from integer arithmetic fairly quickly in this case. Of course, we can avoid this by doing computations in the field extension Q[sqrt 5]: data QS5 = QS5 Rational Rational infixl 7 <*>, infixl 6 <->,<+> conjugate :: QS5 -> QS5 conjugate (QS5 a1 a2) = QS5 a1 (negate a2) (<+>),(<->),(<*>),() :: QS5 -> QS5 -> QS5 (QS5 a1 a2) <+> (QS5 b1 b2) = QS5 (a1+b1) (a2+b2) (QS5 a1 a2) <-> (QS5 b1 b2) = QS5 (a1-b1) (a2-b2) (QS5 a1 a2) <*> (QS5 b1 b2) = QS5 (a1*b1 + 5*a2*b2) (a1*b2 + a2*b1) a@(QS5 a1 a2) b@(QS5 b1 b2) = let QS5 c1 c2 = a <*> conjugate b s = (b1*b1 - 5*b2*b2) in QS5 (c1 / s) (c2 / s) qpow :: QS5 -> Integer -> QS5 qpow q n | n < 3 = case n of 0 -> QS5 1 0 1 -> q 2 -> q <*> q | even n = let q' = qpow q (n `div` 2) in q' <*> q' | otherwise = let q' = qpow q (n `div` 2) in q' <*> q' <*> q fib ::Integer -> Integer fib n = let (QS5 fn _) = (qpow phi n <-> qpow phi' n) s5 in numerator fn where phi = QS5 (1%2) (1%2) phi' = QS5 (1%2) (negate 1%2) s5 = QS5 0 1 However, this is still an O(log n) algorithm, because that's the complexity of raising-to-the-power-of. And it's slower than the simpler integer-only algorithms. It might be amusing to see if this could be transformed into one of the simpler algorithms, though. Cheers, Andrew Bromage