[Haskell-cafe] Fibbonachi numbers algorithm work TOO slow.

[ajb at spamcop.net]

G'day all.

Quoting jerzy.karczmarczuk at 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