The "O(1)" Fibonaccis algorithm

fibs.hs

-- Golden pair data type; GP x y represents x + y phi where phi ** 2 = 1 - phi
data GoldenPair = GP { r :: Integer, phi  :: Integer } deriving (Eq, Show)

-- (a + b phi) * (1 + 1 phi) = (a + b) + a phi so we have the Fibonacci relation directly.

instance Num GoldenPair where
  (GP a b) + (GP c d) = GP (a + c) (b + d)
  (GP a b) * (GP c d) = GP (k + b*d) (k - (a - b)*(c - d)) where k = a*c
  fromInteger x = GP x 0

fibs :: Int -> Integer
fibs n = phi $ GP 1 1 ^ n

An earlier version did exponentiation by squaring but it turns out that this is already part of the definition of ^ in the Prelude, as is the check for negative numbers. The extra details of Num were ugly so I got rid of them. Finally, I played around with using 2 * rt5 $ GP 1 1 ^ n rather than rt5 $ GP 1 1 ^ n - GP 1 (-1) ^ n and trying to get rid of the 1/2 factor, and it turned out that what I was doing could be summed up in an even more elegant way by not representing the Golden Ratio as (GP 1 1) / n but rather just as GP 0 1.

Finally I made a change which seems to make a bit of difference: I managed to get the number of multiplications in the multiplication step down from 5 to 3, though I don't see a way to do 2. The n'th Fibonacci number has about n digits and adding n-digit numbers is O(n) while multiplying them is O(n²) so it makes us do 3/5 the work. I tried to get it down to two but I still don't see a good way.

As the scare quotes say, there is no such thing as an O(1) Fibonacci algorithm because the n'th Fibonacci has O(n) digits and writing all of them in memory takes at least O(n) time. This means that the "O(n)" algorithm is really O(n²). This algorithm is sometimes called the O(1) algorithm because it appears as round(phi ** n / sqrt(5)) rather than a recursive or looping algorithm, but in fact this algorithm is also asymptotically O(n²), with a somewhat lower multiplying coefficient in practice. This is simply because we multiply Fibonaccis to get the same effect as adding them, but multiplying two numbers with k digits takes O(k²) operations.

[You may wonder if it is not in O(n²) but rather O(n² log(n)) -- the answer is that the sum of terms (2ⁱ)² from i=0 to log2(n) is geometric, yielding an upper bound of O(n²).]