fibonacci_functions.py

"""
    Fibonacci functions
"""
import time

def fibonacci_1(n):
    """
    Classic Fibonnacci function

    Fibonnacci is a serie of numbers whose the value is equal to the sum of the 2 previous : 1 1 2 3 5 8 13 21 ...
    :param n: index of the fibonnacci value to calculate. Example fibonnacci(3) = 3, fibonnacci(6) = 13,
    :return: the fibonnaci value corresponding to the n index if n >= 0 else None
    """
    if n < 0 :
        return None
    elif n == 0 or n == 1:
        return 1
    else:
        return fibonacci_1(n - 1) + fibonacci_1(n - 2)

v = None
index = 25
start_time = time.time()
# v = [fibonacci1(i) for i in range(index+1)]       # to get the full list but can took a lot of time
v = fibonacci_1(index)
end_time = time.time() - start_time
print( f"fibonacci_1({index}) =", v, "\n", len(str(v)), "characters in", end_time, "seconds")


def fibonacci_2(n):
    """
    Optimized Fibonnacci function

    Fibonnacci is a serie of numbers whose the value is equal to the sum of the 2 previous : 1 1 2 3 5 8 13 21 ...
    :param n: index of the fibonnacci value to calculate. Example fibonnacci(3) = 3, fibonnacci(6) = 13,
    :return: an iterator of the fibonnacci list until the fibonnaci value corresponding to the index
    """
    p = pp = 1
    for i in range(n+1):
        if i==0 or i==1:
            yield 1
        else:
            n = p + pp
            p, pp = n, p
            yield n


v=None
# over is this value, str() returns ValueError: Exceeds the limit (4300 digits) for integer string conversion;
index = 20576
start_time = time.time()
#v = [i for i in fibonacci2(index)]     # to get the full list in milliseconds
v = [val for idx, val in enumerate(fibonacci_2(index)) if idx == index ]
end_time = time.time() - start_time
print( f"fibonacci_2({index}) =", *v, "\n", len(str(*v)), "characters in", end_time, "seconds")

# RESULTS
# fibonacci_1(25) = 121393
#  6 characters in 0.06116628646850586 seconds
# fibonacci_2(20576) = 9754127354447731664413464877733194642324162792154990277417906043260981700928350843612737359888951573660962713912365529681569456686655351237894935384042220801220882049324010924553031788263232667669395835460595613868586607590722580174611190230505848926683274986885438381310759325261767284171806619155670742105041612838874997686605998240595985226676071288207099679889619094124815694288115706853096471583308341099304022789310697352409404663792413151019974961646662692476926455507726209503091764128212251301110233774919326592483263183948463380192520278297720868314170290776202527389709110685428211398871370690408919668164274590324631884987684062274915038709235319401019210061505607061585118713722174462056727129101719729228404880964198060054070160193010624331361954960794239717314766327842194808733539019997881113013318654612942104879499538928316485300243367340387394641692200919115744791313736637910347312939832961058097756734579935358453674150082772195302427315653527124821722171523738951424316025874880764829037134510939838884200286043441233548524838054837139585873568921481622419078492858137670827775938795535042632462227826780801991495836080804534751196552905247005418010377864866791442378706444042696741192484294777924027321908036929969876517473431424829087133827066458341092832667046538705059230114457764084164214890830880388872130154520379188617354559385976854668563282031149390158692678204206656653572082996095731877898144497603320925855132400382160823679552509794498211444065498044573592045813989818422932692663892116861864731682696116017436631179938488770015908393323771086206978840777735476056241500876292938054047483522069024548260886144754236304992883225127999720780482273192657892936539889540654114718004405236367065957517201029780761425406554204206338092760797892233862020106289695340159035600557031226237154242540105346411489141705171807170750323903897886329143831379796824330417171256056812684085645393159087927630504602935935856368127336259197560593899869386875350865034008998480431607884256415963504930764739400482489604831943664355157856843969748480302827527765080669602110698369566425660993840768286461571659767707309837358308635188139335813066262561299940543908282454530465866170968995549990181423910696368689278870108664787841725619015171651921770772819779727824871284873887426337178078393012392835906392441655421374690610239864964481279794327956716177079670903187089339877448224254139616853495083178338147075748235436946157383130345907522756566242120516056947801139287199046666018344755188869261391168559213440802302510483500844896495945968045658227969034040888412558411582784968910883005570959895521502400722264116534242403339241509021533098667967218955247092844593298839791929816420404223861516514214061129993687748986158994704740127998084520244625462969145517545694614677820701490283347056026342298069094449031609826421724498950210848695425417619681239138590306804743892307538959632979543747335832004346377472282754229988100782210443363019471529649105190750558629386169813967000458378430771682942442610817256304829805454071079821924375844216065997846313487903180452210812960868302631371404696098872228683580844968023401451294475039926826688194608854951773921123020826297768178538974292379180392846490638153328063710649268249330760903408184939474904680932236183110635621189463546370242155069748842215198072888850403000041613532168004120064368910640555629755679574191349322499915265477532609153683139064910911870821930028442674042010575021051702426935059809470716662575872439616036693596346606195323099729335332408215058969490494618639689676093413769540499715588471873054695856274633145333608271919227517578915791844609594673811976018262788657157290549061408474771676814964706618063905887500032072029506703822835371164765274769028282894653781476222081194458792759625519836894655434621261478671703189558902511496964758950338212196622083606340872945252474816785704836379582878939493371924228386251933570220427482510903238320349398124916124403368013753076067128335086239926071033685460459178520083359290362518170588003197192233848668046952824179066520971343543911953779634644566462503916372033650296896254658436766866567535151621949412798749974278239667244181908178583997815085283724213464087282319076233469002534939318122677916444152254906667817534469379734029021723237563490150882
#  4300 characters in 0.02410411834716797 seconds