How I counted the millionth Fibonacci number

, . , (), , . Fullstack- Python , Python . n .






, . , , ; , ? , .





— . — , 0 1. :





0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...







, :





  1. .





  2. .





  3. .





  4. .





  5. 1000000- .





, , , , , Python — 3.9.1.





N- Python:





def recursiveFib(n):
    if n == 1 or n == 2:
        return 1

    return recursiveFib(n - 1) + recursiveFib(n - 2)
      
      



, , . , : 2 , 2 . .





, , , 1,43 , 35- . , .





2 , , . functools LRU ; . .





from functools import lru_cache

@lru_cache()
def recursiveFibCached(n):
    if n == 1 or n == 2:
        return 1

    return recursiveFibCached(n - 1) + recursiveFibCached (n - 2)
      
      



-, lru_cache functools . maxsize, , , 128, . , 200- 0,0002252 !





, 501- , RecursionError: maximum recursion depth exceeded in comparison. , , , :





import sys

sys.setrecursionlimit(5000)
      
      



1000- , 0,001198 . : - 1553- , , , . , .





, , . :





def iterativeFib(n):
    a, b = 0, 1

    for i in range(n):
        a, b = b, a + b

    return a
      
      



, ( ), , 1000- 0,0028195 .





, 1000000- , , , . , , .





— , n- , , ; . :





Binet's formula for calculating the nth Fibonacci number
n- Fibonacci

PHI (ϕ), :





Golden ratio equation, phi
, phi

Python :





def formulaFib(n):
    root_5 = 5 ** 0.5
    phi = ((1 + root_5) / 2)

    a = ((phi ** n) - ((-phi) ** -n)) / root_5

    return round(a)
      
      



: Python , Python , .





, , ? , . - 1475- , : OverflowError: (34, result too large). , python , , , .





. decimal, :





import decimal

def formulaFibWithDecimal(n):
    decimal.getcontext().prec = 10000

    root_5 = decimal.Decimal(5).sqrt()
    phi = ((1 + root_5) / 2)

    a = ((phi ** n) - ((-phi) ** -n)) / root_5

    return round(a)
      
      



10000 , 5 . 10000- 0,0692986 , .





1000000-

, , , , n=10000. , , , 10000 . .





. - , n 89200, , , , ; n , , .





Graph showing the running time of the Binet formula and iterative solution
,

. , n . n. , . , , , — decimal.getcontext().prec = 300000.





. , 1000000- , :





  • 8,832661 ;





  • 1,151380 , 7,7 !





, 208988 209 :





, , , , , . : , 310,8467 , . Fullstack- Python — . — .





, :





  • Data Scientist





  • Data Analyst





  • Data Engineering









  • Fullstack- Python





  • Java-





  • QA- JAVA





  • Frontend-









  • C++





  • Unity





  • -





  • iOS-





  • Android-









  • Machine Learning





  • "Machine Learning Deep Learning"





  • " Data Science"





  • " Machine Learning Data Science"





  • "Python -"





  • " "









  • DevOps








All Articles