Geek asks and answers

Calculating the nth fibonacci number using formulas in python

I calculate the nth fibonacci number using (a) a linear approach and (b) this expression

Python Code:

'Different implementations for computing the n-th fibonacci number'

def lfib(n):
    'Find the n-th fibonacci number iteratively'
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def efib(n):
    'Compute the n-th fibonacci number using the formulae'
    from math import sqrt, floor
    x = (1 + sqrt(5))/2
    return long(floor((x**n)/sqrt(5) + 0.5))


if __name__ == '__main__':
  for i in range(60,80):
    if lfib(i) != efib(i):
      print i, "lfib:", lfib(i)
      print "   efib:", efib(i)

For n> 71, I see that two functions return different values.

Is this related to the floating point arithmetic associated with efib ()? If so, is it appropriate to calculate the number using the matrix form ?

+5
source share
3 answers

You really see rounding errors.

Matrix form is a more accurate and much faster algorithm. Literateprograms.org lists a good implementation, but also contains the following algorithm based on Lucas numbers:

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

3 MIT Open Courseware .

Θ (lg n), , , . Lucas , ( , ):

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)
0.40711593627929688
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)
0.20211100578308105
+11

, efib()?

, . efib

>>> log(x**72)/log(2)
49.98541778140445

Python 53 x86-64, .

+3

...

def fibonum(n):   # Give the nth fibonacci number
    x=[0,1]
    for i in range(2,n):
        x.append(x[i-2]+x[i-1])
    print(x[n-1])
-1

More articles:


All Articles