Berechnung n-te Fibonacci-Zahl, die Formeln in Python

Question

Ich Berechnung der n-te Fibonacci-Zahl mit (a) einen linearen Ansatz und (b) this Ausdruck

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) 

Für n> 71 sehe ich, dass die beiden Funktionen unterschiedliche Werte zurückgeben.

Liegt dies an der Gleitkommaarithmetik, die in efib() involviert ist? Wenn ja, ist es dann ratsam, die Nummer mit der matrix form zu berechnen?

Answer 1

Sie sehen tatsächlich Rundungsfehler.

Die Matrixform ist der genauere und viel schneller Algorithmus. Literateprograms.org listet eine gute Umsetzung, aber es führt auch den folgenden Algorithmus auf Lucas-Zahlen zugrunde:

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 

Werfen Sie einen Blick auf Lecture 3 of the MIT Open Courseware course on algorithms für eine gute Analyse der Matrix-Ansatz.

Sowohl der obige Algorithmus als auch der Matrix-Ansatz haben Θ (lg n) -Komplexität, genau wie die naive rekursive Quadrierungsmethode, die Sie verwendet haben, jedoch ohne die Rundungsprobleme. Der Lucas-Zahlen Ansatz hat die niedrigsten konstant Kosten, den schnelleren Algorithmus zu machen (etwa doppelt so schnell wie den Matrix-Ansatz):

>>> 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 

Answer 2

Liegt die in EFIB beteiligt Kommaarithmetik zu Floating()?

Ja, ist es. Innerhalb efib haben Sie

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

und Python floats have about 53 bits of precision auf x86-64-Hardware, so dass Sie laufen nahe an den Rand.

Answer 3

ich einen sehr einfachen reinen Python-Code habe ...

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])