Fibonacci rápido en python

No es gran cosa, pero aquí teneis una versión de los números de Fibonacci que no se demora mucho para obtener números grandes, por ejemplo, para el número de Fibonacci 10000, tarda 0.1 segundos

(Eliminé los números que hay por el medio para que no quede una imágen excesivamente grande)

El código es simplemente:

---

global fibo
fibo={} # El diccionario, este es el quid de la question

def fibonacci(i):
    global fibo
    if (i in fibo): # Si esta en el diccionario
        return fibo[i] # No hay que buscarlo
    else:
        if (i < 2): # Si es trivial, no hay que memorizarlo
            return 1
        else: # Sino, se busca
            res = fibonacci(i - 1)+ fibonacci(i - 2)
            fibo[i] = res # Se mete en el diccionario
            return res # Y se devuelve

---

El truco está en el diccionario, que evita que haya que recorrer todos los números muchas veces, a costa, claro, de un gasto de memoria.

Hay una cosa a tener en cuenta, llamar directamente a la función (sin haber llamado a otra, que construyese el diccionario antes) con un número mayor o igual a 1000, producirá una excepción:

---

RuntimeError: maximum recursion depth exceeded

---

Para evitar eso, se puede construir el diccionario paso a paso (que se hace con apenas pérdida de rendimiento)

---

import sys

limit = 1000

if (len(sys.argv) > 1):
    limit = int(sys.argv[1])

for i in xrange(1, limit):
    fibonacci(i)

print fibonacci(limit) # Para demostrarlo :)

---

O completo

---

#!/usr/bin/env python
global fibo
fibo={} # El diccionario, este es el quid de la question

def fibonacci(i):
    global fibo
    if (i in fibo): # Si esta en el diccionario
        return fibo[i] # No hay que buscarlo
    else:
        if (i < 2): # Si es trivial, no hay que memorizarlo
            return 1
        else: # Sino, se busca
            res = fibonacci(i - 1)+ fibonacci(i - 2)
            fibo[i] = res # Se mete en el diccionario
            return res # Y se devuelve

import sys

limit = 1000

if (len(sys.argv) > 1):
    limit = int(sys.argv[1])

for i in xrange(1, limit):
    fibonacci(i)

print fibonacci(limit) # Para demostrarlo :)

---

Este método permite buscar incluso el número 100000 sin jubilarse por el camino, en poco más de 2 segundos =P

Hasta otra.