El problema de la sucesión de Fibonacci¶
Nombre: Carlos Javier Bravo Intriago
Link: https://colab.research.google.com/drive/1_2rwV2dJGILuH3S_88fiQ52e1bSqGV1H?usp=sharing
La serie de Fibonacci esta definida como: $$ F(n) = \left\{ \begin{array}{cl} F(0)=1 \\ F(1)=1 \\ F(n) = F(n-1)+F(n-2) & : \ n \ge 2 \end{array} \right. $$
La secuencia es de la forma $0,1,1,2,3,5,8,13,21,\dots$
En la Enciclopedia Online de las Secuencias de números Enteros (OEIS) se lo encuentra con el identificativo A000045
In [1]:
first_300_fibonacci_terms = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 573147844013817084101, 927372692193078999176, 1500520536206896083277, 2427893228399975082453, 3928413764606871165730, 6356306993006846248183, 10284720757613717413913, 16641027750620563662096, 26925748508234281076009, 43566776258854844738105, 70492524767089125814114, 114059301025943970552219, 184551825793033096366333, 298611126818977066918552, 483162952612010163284885, 781774079430987230203437, 1264937032042997393488322, 2046711111473984623691759, 3311648143516982017180081, 5358359254990966640871840, 8670007398507948658051921, 14028366653498915298923761, 22698374052006863956975682, 36726740705505779255899443, 59425114757512643212875125, 96151855463018422468774568, 155576970220531065681649693, 251728825683549488150424261, 407305795904080553832073954, 659034621587630041982498215, 1066340417491710595814572169, 1725375039079340637797070384, 2791715456571051233611642553, 4517090495650391871408712937, 7308805952221443105020355490, 11825896447871834976429068427, 19134702400093278081449423917, 30960598847965113057878492344, 50095301248058391139327916261, 81055900096023504197206408605, 131151201344081895336534324866, 212207101440105399533740733471, 343358302784187294870275058337, 555565404224292694404015791808, 898923707008479989274290850145, 1454489111232772683678306641953, 2353412818241252672952597492098, 3807901929474025356630904134051, 6161314747715278029583501626149, 9969216677189303386214405760200, 16130531424904581415797907386349, 26099748102093884802012313146549, 42230279526998466217810220532898, 68330027629092351019822533679447, 110560307156090817237632754212345, 178890334785183168257455287891792, 289450641941273985495088042104137, 468340976726457153752543329995929, 757791618667731139247631372100066, 1226132595394188293000174702095995, 1983924214061919432247806074196061, 3210056809456107725247980776292056, 5193981023518027157495786850488117, 8404037832974134882743767626780173, 13598018856492162040239554477268290, 22002056689466296922983322104048463, 35600075545958458963222876581316753, 57602132235424755886206198685365216, 93202207781383214849429075266681969, 150804340016807970735635273952047185, 244006547798191185585064349218729154, 394810887814999156320699623170776339, 638817435613190341905763972389505493, 1033628323428189498226463595560281832, 1672445759041379840132227567949787325, 2706074082469569338358691163510069157, 4378519841510949178490918731459856482, 7084593923980518516849609894969925639, 11463113765491467695340528626429782121, 18547707689471986212190138521399707760, 30010821454963453907530667147829489881, 48558529144435440119720805669229197641, 78569350599398894027251472817058687522, 127127879743834334146972278486287885163, 205697230343233228174223751303346572685, 332825110087067562321196029789634457848, 538522340430300790495419781092981030533, 871347450517368352816615810882615488381, 1409869790947669143312035591975596518914, 2281217241465037496128651402858212007295, 3691087032412706639440686994833808526209, 5972304273877744135569338397692020533504, 9663391306290450775010025392525829059713, 15635695580168194910579363790217849593217, 25299086886458645685589389182743678652930, 40934782466626840596168752972961528246147, 66233869353085486281758142155705206899077, 107168651819712326877926895128666735145224, 173402521172797813159685037284371942044301, 280571172992510140037611932413038677189525, 453973694165307953197296969697410619233826, 734544867157818093234908902110449296423351, 1188518561323126046432205871807859915657177, 1923063428480944139667114773918309212080528, 3111581989804070186099320645726169127737705, 5034645418285014325766435419644478339818233, 8146227408089084511865756065370647467555938, 13180872826374098837632191485015125807374171, 21327100234463183349497947550385773274930109, 34507973060837282187130139035400899082304280, 55835073295300465536628086585786672357234389, 90343046356137747723758225621187571439538669, 146178119651438213260386312206974243796773058, 236521166007575960984144537828161815236311727, 382699285659014174244530850035136059033084785, 619220451666590135228675387863297874269396512, 1001919737325604309473206237898433933302481297, 1621140188992194444701881625761731807571877809, 2623059926317798754175087863660165740874359106, 4244200115309993198876969489421897548446236915, 6867260041627791953052057353082063289320596021, 11111460156937785151929026842503960837766832936, 17978720198565577104981084195586024127087428957, 29090180355503362256910111038089984964854261893, 47068900554068939361891195233676009091941690850, 76159080909572301618801306271765994056795952743, 123227981463641240980692501505442003148737643593, 199387062373213542599493807777207997205533596336, 322615043836854783580186309282650000354271239929, 522002106210068326179680117059857997559804836265, 844617150046923109759866426342507997914076076194, 1366619256256991435939546543402365995473880912459, 2211236406303914545699412969744873993387956988653, 3577855662560905981638959513147239988861837901112, 5789092068864820527338372482892113982249794889765, 9366947731425726508977331996039353971111632790877, 15156039800290547036315704478931467953361427680642, 24522987531716273545293036474970821924473060471519, 39679027332006820581608740953902289877834488152161, 64202014863723094126901777428873111802307548623680, 103881042195729914708510518382775401680142036775841, 168083057059453008835412295811648513482449585399521, 271964099255182923543922814194423915162591622175362, 440047156314635932379335110006072428645041207574883, 712011255569818855923257924200496343807632829750245, 1152058411884454788302593034206568772452674037325128, 1864069667454273644225850958407065116260306867075373, 3016128079338728432528443992613633888712980904400501, 4880197746793002076754294951020699004973287771475874, 7896325826131730509282738943634332893686268675876375, 12776523572924732586037033894655031898659556447352249, 20672849399056463095319772838289364792345825123228624, 33449372971981195681356806732944396691005381570580873, 54122222371037658776676579571233761483351206693809497, 87571595343018854458033386304178158174356588264390370, 141693817714056513234709965875411919657707794958199867, 229265413057075367692743352179590077832064383222590237, 370959230771131880927453318055001997489772178180790104, 600224643828207248620196670234592075321836561403380341, 971183874599339129547649988289594072811608739584170445, 1571408518427546378167846658524186148133445300987550786, 2542592393026885507715496646813780220945054040571721231, 4114000911454431885883343305337966369078499341559272017, 6656593304481317393598839952151746590023553382130993248, 10770594215935749279482183257489712959102052723690265265, 17427187520417066673081023209641459549125606105821258513, 28197781736352815952563206467131172508227658829511523778, 45624969256769882625644229676772632057353264935332782291, 73822750993122698578207436143903804565580923764844306069, 119447720249892581203851665820676436622934188700177088360, 193270471243015279782059101964580241188515112465021394429, 312718191492907860985910767785256677811449301165198482789, 505988662735923140767969869749836918999964413630219877218, 818706854228831001753880637535093596811413714795418360007, 1324695516964754142521850507284930515811378128425638237225, 2143402371193585144275731144820024112622791843221056597232, 3468097888158339286797581652104954628434169971646694834457, 5611500259351924431073312796924978741056961814867751431689, 9079598147510263717870894449029933369491131786514446266146, 14691098406862188148944207245954912110548093601382197697835, 23770696554372451866815101694984845480039225387896643963981, 38461794961234640015759308940939757590587318989278841661816, 62232491515607091882574410635924603070626544377175485625797, 100694286476841731898333719576864360661213863366454327287613, 162926777992448823780908130212788963731840407743629812913410, 263621064469290555679241849789653324393054271110084140201023, 426547842461739379460149980002442288124894678853713953114433, 690168906931029935139391829792095612517948949963798093315456, 1116716749392769314599541809794537900642843628817512046429889, 1806885656323799249738933639586633513160792578781310139745345, 2923602405716568564338475449381171413803636207598822186175234, 4730488062040367814077409088967804926964428786380132325920579, 7654090467756936378415884538348976340768064993978954512095813, 12384578529797304192493293627316781267732493780359086838016392, 20038668997554240570909178165665757608500558774338041350112205, 32423247527351544763402471792982538876233052554697128188128597, 52461916524905785334311649958648296484733611329035169538240802, 84885164052257330097714121751630835360966663883732297726369399, 137347080577163115432025771710279131845700275212767467264610201, 222232244629420445529739893461909967206666939096499764990979600] # https://r-knott.surrey.ac.uk/fibonacci/fibtable.html
In [2]:
import sys
import time
import tracemalloc
from typing import List
from functools import wraps
import numpy as np
# verdadero para hacer resultados imprimibles, falso para retornar los
# valores como diccionario (útil para graficar)
VERBOSE = False
# Decorador medidor de tiempo
def measure_time(func):
@wraps(func)
def wrapper(*args, **kwargs):
start_time = time.time()
result = func(*args, **kwargs)
end_time = time.time()
elapsed_time = end_time - start_time
if VERBOSE:
print(f"Tiempo de ejecucion: {elapsed_time} seg")
return result
if isinstance(result, tuple) and len(result) == 2 \
and isinstance(result[1], dict):
result[1]["time"] = elapsed_time
return result
else:
return result, {"time": elapsed_time}
return wrapper
# Decorador medidor de Memoria
def measure_memory(func):
@wraps(func)
def wrapper(*args, **kwargs):
tracemalloc.start()
result = func(*args, **kwargs)
_, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
# 1 << 10 = 1024, 1 << (10*2) = 1024**2 Conversion a MB
peak = peak/(1<<(10*2))
if VERBOSE:
print(f"Memoria usada aproximada: {peak} MB")
return result
if isinstance(result, tuple) and len(result) == 2 \
and isinstance(result[1], dict):
result[1]["memory"] = peak
return result
else:
return result, {"memory": peak}
return wrapper
Se propondrá variantes tanto las que se usan de forma intuitiva (educativa), como aquellas con estrategias tanto algorítmicas y matemáticas para lograr conseguir el $n$-estimo término de la serie.
Variante 1. Uso de Recursividad y la técnica del Divide y Vencerás ¶
Este es el algoritmo que se enseña por excelencia, es fácil, corto e intuitivo.
In [3]:
VERBOSE = True # para hacer _printable_ el resultado
def _fibonacci_recursive(n: int) -> int:
if n <= 1:
return n
return _fibonacci_recursive(n-1) + _fibonacci_recursive(n-2)
@measure_time
@measure_memory
def fibonacci_recursive(n: int) -> int:
return _fibonacci_recursive(n)
# inviable a partir del 40-ésimo termino, toma más de 40 segundos
print(fibonacci_recursive(20))
Memoria usada aproximada: 0.009495735168457031 MB Tiempo de ejecucion: 0.006249427795410156 seg 6765
Sin embargo, esconde a primera vista un problema, hay operaciones que se repiten en cada llamada a recursion.
Si no se controla las llamadas repetidas, la eficiencia se "resiente". Lo cual hace que su complejidad temporal sea exponencial $O(2^n)$. Nada óptimo. (En estas pruebas ya con un valor superior a 42 requiere más de 1 minuto)
Fig 1. Arbol de recursion para el problema de la secuencia de Fibonacci, cada nodo coloreado es el nodo que se vuelve a recalcular. La busqueda es en profundidad, llega hasta el ultimo nodo de la rama mas a la izquierda. Obtenido de https://textbooks.cs.ksu.edu/cc210/16-recursion/06-example-fibonacci/
Para evitar que en cada recursion recalcule el $k$ término en casos repetidos, se debe aplicar una técnica llamada Memoization. Esta técnica ayudará evitar dichos casos repetidos al almacenarlos en una estructura de datos, y posteriormente poderlos reusar sin necesidad de recalcularlos nuevamente.
Variante 2. Uso de Recursividad y Memoization¶
La técnica de Memoization permitirá "omitir" o "podar" los casos repetidos. Esto es una reducción en su complejidad temporal, puesto que ahora únicamente recorrerá en los casos faltantes o que no estén dentro de la estructura usada para memoization, y eso implica una complejidad lineal $O(N)$
In [4]:
memo_dict = {}
def _fibonacci_recursive_with_global_dictionary_memoization(n: int) -> int:
if n <= 1:
return n
if n in memo_dict: # búsqueda constante teórica si no existe colisión
return memo_dict[n]
memo_dict[n] = _fibonacci_recursive_with_global_dictionary_memoization(n - 1) \
+ _fibonacci_recursive_with_global_dictionary_memoization(n - 2)
return memo_dict[n]
@measure_time
@measure_memory
def fibonacci_recursive_with_global_dictionary_memoization(n: int) -> int:
return _fibonacci_recursive_with_global_dictionary_memoization(n)
print("Primera llamada")
# desde 2969 se arrojará la excepción RecursionError
print(fibonacci_recursive_with_global_dictionary_memoization(2968))
print("Segunda llamada")
# desde 2969 se arrojará la excepción RecursionError
print(fibonacci_recursive_with_global_dictionary_memoization(2968))
Primera llamada Memoria usada aproximada: 1.2742977142333984 MB Tiempo de ejecucion: 0.322188138961792 seg 84300715318709162396591528018538503371795904295540866109356011374712936562170324448172601734359735721220005090755858264569259058774779133512066732443546915400817555383478685602408220621379068693802409392342263516477344022956138868162590869395162809970902363996812274617940341603156797523887458637621901455197625024653446242730572776575068808397205552741980093661931130048448736693957616175512897398083711363707552699988833964306329866334180235885379420009486406820695229821325267251644421352303581915889381631216030096651720261788384136231488256628403127347559331324324061865997149205393090161181111434634621102766427691 Segunda llamada Memoria usada aproximada: 0.0 MB Tiempo de ejecucion: 1.2874603271484375e-05 seg 84300715318709162396591528018538503371795904295540866109356011374712936562170324448172601734359735721220005090755858264569259058774779133512066732443546915400817555383478685602408220621379068693802409392342263516477344022956138868162590869395162809970902363996812274617940341603156797523887458637621901455197625024653446242730572776575068808397205552741980093661931130048448736693957616175512897398083711363707552699988833964306329866334180235885379420009486406820695229821325267251644421352303581915889381631216030096651720261788384136231488256628403127347559331324324061865997149205393090161181111434634621102766427691
In [5]:
# Inspirado de: https://www.geeksforgeeks.org/dsa/program-for-nth-fibonacci-number/
def _fibonacci_recursive_with_local_memoization(n: int, memo: List[int]) -> int:
if n <= 1:
return n
if memo[n] != -1:
return memo[n]
memo[n] = _fibonacci_recursive_with_local_memoization(n - 1, memo) \
+ _fibonacci_recursive_with_local_memoization(n - 2, memo)
return memo[n]
@measure_time
@measure_memory
def fibonacci_recursive_with_local_memoization(n: int) -> int:
memo = [-1]*(n+1) # Crea un Array lleno de -1 de tamaño (n+1)
return _fibonacci_recursive_with_local_memoization(n, memo)
print("Primera llamada")
# desde 2969 se arrojará la excepción RecursionError
print(fibonacci_recursive_with_local_memoization(2968))
print("Segunda llamada")
# desde 2969 se arrojará la excepción RecursionError
print(fibonacci_recursive_with_local_memoization(2968))
Primera llamada Memoria usada aproximada: 1.3042278289794922 MB Tiempo de ejecucion: 0.32247066497802734 seg 84300715318709162396591528018538503371795904295540866109356011374712936562170324448172601734359735721220005090755858264569259058774779133512066732443546915400817555383478685602408220621379068693802409392342263516477344022956138868162590869395162809970902363996812274617940341603156797523887458637621901455197625024653446242730572776575068808397205552741980093661931130048448736693957616175512897398083711363707552699988833964306329866334180235885379420009486406820695229821325267251644421352303581915889381631216030096651720261788384136231488256628403127347559331324324061865997149205393090161181111434634621102766427691 Segunda llamada Memoria usada aproximada: 1.222151756286621 MB Tiempo de ejecucion: 0.31734275817871094 seg 84300715318709162396591528018538503371795904295540866109356011374712936562170324448172601734359735721220005090755858264569259058774779133512066732443546915400817555383478685602408220621379068693802409392342263516477344022956138868162590869395162809970902363996812274617940341603156797523887458637621901455197625024653446242730572776575068808397205552741980093661931130048448736693957616175512897398083711363707552699988833964306329866334180235885379420009486406820695229821325267251644421352303581915889381631216030096651720261788384136231488256628403127347559331324324061865997149205393090161181111434634621102766427691
El motivo probablemente del porqué a partir de 2969 término de la serie de Fibonacci con el método antes propuesto arroje la excepción RecursionError es debido a que Python por defecto tiene un límite de llamadas recursivas.
Aclaratoria: En el equipo donde se ejecutaron estas pruebas, el límite de llamadas recursivas es 3000. Con base en la documentación se puede incrementar este límite de llamadas recursivas; sin embargo, es algo no recoendable, puesto que si se asigna un valor demasiado alto, podría bloquear/congelar el equipo.
In [6]:
print(sys.getrecursionlimit())
3000
Ambas propuestas (fibonacci_recursive_with_global_dictionary_memoization, y fibonacci_recursive_with_local_memoization) aplican la técnica de Memoization, pero cada una tiene cierta diferencia:
La propuesta fibonacci_recursive_with_global_dictionary_memoization usa un diccionario, y este diccionario es declarado como variable global (desaconsejado en Clean Code), esto permite reutilizar este diccionario tantas veces sean necesarias, puede incrementar sin necesidad de preallocate la estructura de datos que almacenara los visitados, y su búsqueda amortizada es de complejidad constante
La propuesta fibonacci_recursive_with_local_memoization por otra parte, cada vez que se invoca al método general (no al recursivo), creara una nueva lista de tamaño $n+1$.
La diferencia es a nivel de reutilización, mientras que la propuesta con diccionario se puede reusar para cualquier llamada, la propuesta con lista requerirá construir nuevamente la lista de valores visitados.
Variante 3. Fibonacci iterativo¶
Esta variante aplica un enfoque iterativo basado en la relación de recurrencia lineal $F(n) = F(n-1)+F(n-2)$.
Debido a que es un unico bucle for, su complejidad temporal es $O(N)$.
In [7]:
def _fibonacci_iterative(n: int) -> int:
if n <= 1:
return n
grandparent = 0
parent = 1
current = 0
for i in range(2, n+1):
current = parent + grandparent
grandparent = parent
parent = current
return current
@measure_time
@measure_memory
def fibonacci_iterative(n: int) -> int:
return _fibonacci_iterative(n)
print(fibonacci_iterative(5000))
Memoria usada aproximada: 0.0022802352905273438 MB Tiempo de ejecucion: 0.0038406848907470703 seg 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
Variante 4. Exponencial Matricial¶
Esta variante se basa en la representación matricial:
$$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ n = \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} $$
Se implementará de manera ingenua o naive esta potencia matricial con Numpy.
In [8]:
@measure_time
@measure_memory
def fibonacci_matrix_numpy(n): # version más teórica, sin optimizaciones
if n <= 1:
return n
mat1 = np.array([[1, 1], [1, 0]])
mat1 = np.linalg.matrix_power(mat1, n - 1)
return mat1[0][0].astype(int)
# hasta 92 acierta, 93 en adelante falla por desbordamiento
print(fibonacci_matrix_numpy(92))
Memoria usada aproximada: 0.001953125 MB Tiempo de ejecucion: 0.00019073486328125 seg 7540113804746346429
Sí se implementa la operacion matricial con Numpy, (después de probar iteración a iteración), se acierta los valores de la secuencia desde 0 hasta 92, del 93 en adelante tiende a arrojar valores erráticos, esto debido a la limitante de que los enteros de Numpy son enteros de 64 bits (int64), el cual el valor máximo admitido es $9,223,372,036,854,775,807$, para el $93$-ésimo término de la serie el número es $12,200,160,415,121,876,738$, desbordando el límite de la variable.
Para superar esta limitación, se crea una clase Matrix2x2 con números nativos de Python 3, el tipo int ya es de precisión arbitraria. Es decir, Python maneja nativamente números tan grandes como la memoria RAM permita.
Otra estrategia implementada para optimizar las operaciones dentro de la potenciación es la llamada Exponenciación binaria o Exponentiation by squaring, la cual aplica la estrategia de Divide y Vencerás y se representa de la forma recursiva:
$$
x^n= \left\{ \begin{array}{cl}
x(x^2)^{(n-1)/2} & \text{si }n \text{ es impar}\\
(x^2)^{n/2} & \text{si }n \text{ es impar}
\end{array} \right.
$$
Dado que las operaciones matriciales se realizan sobre una matriz de tamaño fijo $(2\times 2)$, su costo es constante. En consecuencia, se deduce teóricamente, el algoritmo Exponentiation by squaring es de complejidad temporal $O(log(n))$. Dado que las operaciones matriciales se realizan sobre una matriz de tamaño fijo $(2\times 2)$, su costo es constante. En consecuencia, se deduce que esta variante para encontrar el $n$-ésimo término de la serie de Fibonacci es $O(log(n))$ también.
In [9]:
class Matrix2x2:
def __init__(self, e00: int, e01: int, e10: int, e11: int):
self.e00 = e00
self.e01 = e01
self.e10 = e10
self.e11 = e11
# sobrecarga del operador * (multiplicación)
def __mul__(self, other: 'Matrix2x2') -> 'Matrix2x2':
return Matrix2x2(
e00=self.e00 * other.e00 + self.e01 * other.e10,
e01=self.e00 * other.e01 + self.e01 * other.e11,
e10=self.e10 * other.e00 + self.e11 * other.e10,
e11=self.e10 * other.e01 + self.e11 * other.e11
)
# https://en.wikipedia.org/wiki/Exponentiation_by_squaring#With_constant_auxiliary_memory
# sobrecarga del operador ** (potenciación)
def __pow__(self, n: int) -> 'Matrix2x2':
if n < 0:
raise ValueError("n should be >= 0")
result = Matrix2x2(1, 0, 0, 1) # Matriz Identidad
_self = self
n = n+1
while n != 0:
if (n & 1) != 0: # otra forma de verificar si n % 2 != 0
result *= _self
n >>= 1 # equivalente a n //=2
_self = _self * _self
return result
@measure_time
@measure_memory
def fibonacci_matrix_python_optimized(n: int) -> int:
if n <= 1:
return n
fib = Matrix2x2(0, 1, 1, 1)**n
return fib.e00
print(fibonacci_matrix_python_optimized(5000))
Memoria usada aproximada: 0.009952545166015625 MB Tiempo de ejecucion: 0.0006465911865234375 seg 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
Variante 5. Fast Doubling¶
Esta propuesta se basa en el experimento realizado por Nayuki, quien demuestra por método de inducción que dado $F(k)$ y $F(k+1)$, se obtiene que: $$ \begin{array}{rcl} F(2k) & = & F(k)\left[2F(k+1)−F(k)\right] \\ F(2k+1) & = & F(k+1)^2+F(k)^2 \end{array} $$
Según comentarios del autor:
Estas identidades pueden extraerse del algoritmo de exponenciación matricial. En cierto sentido, este algoritmo es el algoritmo de exponenciación matricial sin los cálculos redundantes. Debería ser un factor constante más rápido que la exponenciación matricial, pero la complejidad temporal asintótica se mantiene. Nayuki, (2023).
Este algoritmo teóricamente tiene complejidad temporal $O(log(N))$
Se ha usado el código fuente proporcionado por Nayuki en Python.
In [10]:
# source: https://www.nayuki.io/res/fast-fibonacci-algorithms/fastfibonacci.py
def _fibonacci_fast_doubling(n):
# Returns the tuple (F(n), F(n+1))
if n == 0:
return 0, 1
else:
# a = F(k), b = F(k+1), c=F(2k), d=F(2k+1)
a, b = _fibonacci_fast_doubling(n >> 1) # equivalente a n // 2
c = a * (b * 2 - a) # F(2k) = F(k) * (2*F(k+1)-F(k))
d = a * a + b * b # F(2k+1) = F(k+1)*F(k+1) + F(k) * F(k)
if (n & 1) == 0: # otra forma de verificar si n % 2 == 0
return c, d
else:
return d, c + d
@measure_time
@measure_memory
def fibonacci_fast_doubling(n):
if n <= 1:
return n
return _fibonacci_fast_doubling(n)[0]
print(fibonacci_fast_doubling(5000))
Memoria usada aproximada: 0.00823211669921875 MB Tiempo de ejecucion: 0.00013875961303710938 seg 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
Validación con los primeros 300 términos de la serie de Fibonacci¶
In [11]:
# Validación con los primeros 300 términos de la serie de Fibonacci
# (https://r-knott.surrey.ac.uk/fibonacci/fibtable.html)
VERBOSE=False # no imprima en pantalla los tiempos ni memoria consumidas
validation_data = {
"fibonacci_recursive": {
"max":35,
"callback": fibonacci_recursive
},
"fibonacci_recursive_with_global_dictionary_memoization": {
"max":2968,
"callback": fibonacci_recursive_with_global_dictionary_memoization
},
"fibonacci_recursive_with_local_memoization": {
"max":2968,
"callback": fibonacci_recursive_with_local_memoization
},
"fibonacci_iterative": {
"callback": fibonacci_iterative
},
"fibonacci_matrix_numpy": {
"max":92,
"callback": fibonacci_matrix_numpy
},
"fibonacci_matrix_python_optimized": {
"callback": fibonacci_matrix_python_optimized
},
"fibonacci_fast_doubling": {
"callback": fibonacci_fast_doubling
},
}
for fibo_variant_name, values in validation_data.items():
_max_value = min(300, values.get("max", 300))
for i in range(_max_value+1): # que itere al maximo valor admitido por cada variante
response = values["callback"](i)
if response[0] != first_300_fibonacci_terms[i]:
print(f"El {i}-ésimo termino de la serie con el algoritmo {fibo_variant_name} no es correcto")
break
print(f"Se ha validado los primeros {_max_value} de la serie con el algoritmo {fibo_variant_name}, y todos son correctos")
Se ha validado los primeros 35 de la serie con el algoritmo fibonacci_recursive, y todos son correctos Se ha validado los primeros 300 de la serie con el algoritmo fibonacci_recursive_with_global_dictionary_memoization, y todos son correctos Se ha validado los primeros 300 de la serie con el algoritmo fibonacci_recursive_with_local_memoization, y todos son correctos Se ha validado los primeros 300 de la serie con el algoritmo fibonacci_iterative, y todos son correctos Se ha validado los primeros 92 de la serie con el algoritmo fibonacci_matrix_numpy, y todos son correctos Se ha validado los primeros 300 de la serie con el algoritmo fibonacci_matrix_python_optimized, y todos son correctos Se ha validado los primeros 300 de la serie con el algoritmo fibonacci_fast_doubling, y todos son correctos
Comparación tiempo de ejecución por cada variante:¶
Se comprobará el tiempo de ejecución para cada algoritmo en los primeros 5000 términos de la Serie de Fibonacci
In [12]:
memo_dict = {} # reiniciamos el diccionario de memoization
result_dict = {}
validation_data["fibonacci_recursive"]["max"]=30
for fibo_variant_name, values in validation_data.items():
_max_value = min(5000, values.get("max", 5000))
result_dict[fibo_variant_name] = {"time": [], "memory": []}
for i in range(_max_value + 1):
n_term, data = values["callback"](i)
result_dict[fibo_variant_name]["time"].append(data["time"])
result_dict[fibo_variant_name]["memory"].append(data["memory"])
In [13]:
import matplotlib.pyplot as plt
fig, (ax_time, ax_mem) = plt.subplots(2, 1, figsize=(12, 10), sharex=True)
for i, (name, metrics) in enumerate(result_dict.items()):
times = metrics["time"]
memories = metrics["memory"]
color = plt.cm.tab10.colors[i]
x_time = range(len(times))
ax_time.plot(x_time, times, '.-', label=name, color=color, alpha=0.8, linewidth=1.5)
x_mem = range(len(memories))
ax_mem.plot(x_mem, memories, '.-', label=name, color=color, alpha=0.8, linewidth=1.5)
ax_time.set_title("Gráfica $N$ Término VS Tiempo de ejecución [Escala logarítmica]")
ax_time.set_ylabel("Tiempo (segundos)")
ax_time.legend()
ax_time.grid(True, linestyle=':', alpha=0.6)
ax_time.set_yscale('log')
ax_mem.set_title("Gráfica $N$ Término VS Consumo de Memoria [Escala logarítmica]")
ax_mem.set_ylabel("Memoria (MB)")
ax_mem.set_xlabel("$N$-ésimo término")
ax_mem.legend()
ax_mem.grid(True, linestyle=':', alpha=0.6)
ax_mem.set_yscale('log')
plt.tight_layout()
plt.show()
Pensamientos finales:¶
- A la hora de obtener términos $N$-ésimos de la serie de Fibonacci se puede deducir que el algoritmo con mejor resultado en tiempo de ejecución es
fast_doublingpropuesto por Nayuki en su blog personal, aprovechando las capacidades de python para manejar enteros muy grandes, este algoritmo permite encontrar cualquier término en complejidad temporal $O(\log N)$. - Si el término $N$ de la serie es un valor por debajo del límite recursivo, el algoritmo con una complejidad temporal más baja (debido a su
Memoizationglobal) esfibonacci_recursive_with_global_dictionary_memoization. Se aprovecha de que la complejidad temporal es Lineal, y la búsqueda en el diccionario está amortizado a tiempo constante $O(1)$. Sin embargo, aquí existe la probabilidad de que debido a que el entero es mucho más grande que_PyHASH_MODULUS, lo cual la búsqueda pasa a ser en el peor escenario de complejidad temporal $O(N)$. - Pese a que no se ha mencionado en ninguna de las variantes la complejidad espacial, vale acotar que algoritmo más amigable con el uso de la memoria es
fibonacci_recursive_with_global_dictionary_memoization. Los picos sugieren que el diccionario en esa instancia se ha llenado (o su espacio asignado en memoria), Python (al igual que varios lenguajes de programacion) reasigna memoria dinámicamente, y esa reasignación típicamente suele constar de: 1) Asignación de un nuevo espacio de memoria $2^{n+1}$ veces más grande que la anterior, 2) copiar profundo, o mover los punteros correspondientes al nuevo espacio.
Nota sobre el uso de herramientas de IA generativa¶
En la elaboración de este notebook se utilizaron herramientas de inteligencia artificial generativa de forma puntual y limitada, exclusivamente como apoyo para la definición de estructuras $LaTeX$ con fines de presentación, y en el script para generar la representación gráfica de los resultados.
La redacción del contenido, el desarrollo del código, el diseño del análisis y la interpretación de los resultados son de autoría propia, o se basan en material proporcionado en clase y en recursos disponibles públicamente en línea, los cuales han sido referenciados, reelaborados y/o adaptados para los objetivos de este trabajo.
Referencias¶
- [1] Project Nayuki, "Fast Fibonacci algorithms," Project Nayuki. [En línea]. [Accedido: 24 de enero de 2026].
- [2] N. J. A. Sloane, Ed., "Sequence A000045: Fibonacci numbers," The On-Line Encyclopedia of Integer Sequences (OEIS). [En línea]. [Accedido: 24 de enero de 2026].
- [3] Kansas State University, "Example: Fibonacci," en CC 210: Fundamental Computer Programming Concepts, Computational Core. [En línea]. [Accedido: 24 de enero de 2026].
- [4] "Fibonacci sequence," Wikipedia, The Free Encyclopedia. [En línea]. [Accedido: 24 de enero de 2026].
- [5] "Exponentiation by squaring," Wikipedia, The Free Encyclopedia. [En línea]. [Accedido: 24 de enero de 2026].
- [6] R. Knott, "The First 300 Fibonacci Numbers," University of Surrey. [En línea]. [Accedido: 24 de enero de 2026].
- [7] Python Software Foundation, "sys — System-specific parameters and functions," Python 3.12 Documentation. [En línea]. [Accedido: 24 de enero de 2026].