Calculating Fibonacci numbers: a non-recursive formula

I recently discovered that there is a non-recursive formula for calculating Fibonacci numbers. fibn below is a naive implementation in Python (with fibr as a matching naive implementation of the recursive algorithm):

from math import sqrt

def fibn(x):
    sqrt5 = sqrt(5)
    r = (1 + sqrt5) / 2.0
    s = (1 - sqrt5) / 2.0
    result = ( (r ** x) - (s ** x) ) / sqrt5
    return int(result)

def fibr(x):
    if x == 1: return 1
    if x == 2: return 1
    return fibr(x-1) + fibr(x-2)

Remarkably result in fibn~ is a whole number. It has to be implemented as a float because of the √5s.

The non-recursive version is a lot faster, even for smallish numbers, and makes larger fibonacci numbers accessible. eg: fibn(20) is more than 800 times faster than fibr(20); fibn(200) returned immediately – I stopped fibr(200) after five minutes.

>>> proc.fibn(20)
6765
>>> proc.fibr(20)
6765
>>> 
>>> t_no_rec = timeit.timeit('proc.fibn(20)', setup='import proc', number=100)
>>> t_yes_rec = timeit.timeit('proc.fibr(20)', setup='import proc', number=100)
>>> 
>>> t_yes_rec / t_no_rec
844.0452218686785
>>> 
>>> proc.fibn(200)
280571172992512015699912586503521287798784

I picked up the formula in Combinatorics: a very short introduction, which is a fun read.

Unlike the recursive version, the non-recursive formula could be a continuous function, ie take floats as input. However, s is a negative number (-0.6180339887498949), so fractional powers of this will be complex numbers.

It might be interesting to prove that the formula always returns whole numbers – given integer input, but that's a story for another day.

fib :: Integer -> Integer
fib x = floor (((r ** y) - (s ** y)) / sqrt5)
  where
    y = fromIntegral x
    sqrt5 = sqrt (5 :: Double)
    r = (1 + sqrt5) / 2.0
    s = (1 - sqrt5) / 2.0