Jugando a Fibonacci

Los conejos no pierden el tiempo...

"Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también"

Leonardo de Pisa (Fibonacci)

La solución al problema planteado es la sucesión 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., donde cada elemento de la sucesión representa el número de parejas de conejos y cada posición de la sucesión los meses. La famosa y omnipresente Sucesión de Fibonacci, cuya definición recursiva es

-->  f0 = 0             para n = 0,

-->  f1 = 1             para n = 1,

-->  fn = fn-1 + fn-2   para n = 2, 3, 4,..., n.

Este año me he propuesto aprender a programar. Ando metido en cursos de MATLAB y Python en los que espero aprender ciertas nociones básicas para que un día haga 'click' en mí un modo de pensamiento computacional. Buscando este 'click' me he puesto a jugar a Fibonacci picando código para hacer un sencillo programita que calcule elementos de la sucesión a partir de esta definición recursiva, tan elegante. La idea es sencilla: al ejecutarse le dices cuántos elementos de la sucesión quieres calcular y él los calcula y los imprime en pantalla.

  


Et voilà. La sucesión para 25 y 40 elementos. Le he añadido al programa unas líneas para que imprima el tiempo de cálculo. Parece sorprendente que para calcular 25 elementos tarde 0,4 segundos y para calcular 40 se dispare hasta los 255 segundos (4 minutos y 15 segundos). ¿Algo falla?. Pues no. Es lo que hay. Con esta definición el número de operaciones que tiene que realizar el ordenador crece exponencialmente, y exponencialmente es 'a toda hostia': si quisiera calcular la sucesión de 100 elementos y se comenzara a ejecutar el programa en el Big Bang todavía estaría esperando sentado delante de la pantalla unos 13700 millones de años más viejo (y eso que el ordenador hace del orden de millones de operaciones por segundo). Esto hay que optimizarlo, no puedo esperar tanto, que tengo dentista la semana que viene.

El Tenor me habló de la memoization. Se trata de una técnica de optimización para acelerar la ejecución con llamadas a la función que evitan el cálculo de resultados para entradas procesadas con anterioridad. Una función memoizada 'recuerda' los resultados de una serie de entradas específicas. Haber A ver si así me ahorro algo de tiempo.

 


Del orden de los miles de millones de años al orden de los segundos. No está mal. No está nada mal. Por cierto, para terminar. ¿Qué pasa si divido un número de la sucesión por el anterior? (para n tendiendo a infinito, pero para un n grande ya me vale)

  

¿Te suena ese número?
¡Exacto!

PD: Tenore, si he escrito alguna aberración en estas líneas ruego que me pegues una colleja.