Calcolo numero di Fibonacci ennesima utilizzando le formule in python

Question

Sto calcolando il numero di Fibonacci all'ennesima utilizzando (a) un approccio lineare, e (b) this espressione

codice Python:

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

Per n> 71 vedo che le due funzioni restituiscono valori diversi.

È dovuto all'aritmetica in virgola mobile coinvolta in efib()? Se è così, è consigliabile calcolare il numero utilizzando lo matrix form?

Answer 1

In effetti si verificano errori di arrotondamento.

Il modulo a matrice è il più preciso algoritmo e. Literateprograms.org elenca una buona implementazione, ma elenca anche il seguente algoritmo in base ai numeri di Lucas:

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 

Date un'occhiata a Lecture 3 of the MIT Open Courseware course on algorithms per una buona analisi del approccio a matrice.

Sia l'algoritmo precedente sia l'approccio matrix hanno complessità Θ (lg n), proprio come il metodo di squadratura ricorsiva ingenuo utilizzato, ma senza problemi di arrotondamento. L'approccio numeri Lucas ha il più basso costo costante, il che rende l'algoritmo più veloce (circa due volte più veloce come l'approccio a matrice):

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

È questo a causa di aritmetica in virgola mobile coinvolti in EFIB()?

Sì, lo è. All'interno efib avete

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

e Python floats have about 53 bits of precision su hardware x86-64, quindi si sta eseguendo vicino al bordo.

Answer 3

Ho un codice puramente python molto semplice ...

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