El ésimo número de Fibonacci se puede calcular en tiempo lineal utilizando la siguiente recurrencia:
def fib(n):
i, j = 1, 1
for k in {1...n-1}:
i, j = j, i+j
return i
El ésimo número de Fibonacci también puede calcularse como [ φ n / √. Sin embargo, esto tiene problemas con problemas de redondeo incluso paranrelativamente pequeño. Probablemente hayformas de evitar esto,pero prefiero no hacerlo.
¿Hay una manera eficiente (en el valor logarítmico o mejor) algoritmo para calcular el n ésimo número de Fibonacci que no se basa en la aritmética de punto flotante? Suponga que las operaciones de enteros ( + , - , × , / ) se pueden realizar en tiempo constante.
Respuestas:
Puede usar la alimentación de matriz y la identidad En su modelo de cómputo, este es un algoritmo O ( log n ) si usa un cuadrado repetido para implementar el encendido.
fuente
Puede leer este artículo matemático: Un algoritmo rápido para calcular grandes números de Fibonacci (Daisuke Takahashi): PDF .
Más simple, implementé varios algoritmos de Fibonacci en C ++ (sin y con GMP) y Python. Fuentes completas en Bitbucket. Desde la página principal también puede seguir enlaces a:
Las fórmulas más útiles son:
Ten cuidado con el algoritmo. No debe calcular el mismo valor varias veces. Un algoritmo recursivo simple (en Python):
fuente
Consulte el libro gratuito Matters Computational y el código pari / gp.
fuente