Hey guys does anyone of you know techniques to calculate 10000th Fibonacci number?

Question

Recursion can barely compute until like 50th Fibonacci number and probably will take eternity to compute 10k th number as it's complexity is exponential , the formula doesn't do so well either it computes only until 1500 th Fibonacci number

Answer 1

Python's ints don't overflow.

As long as you don't use recursion, it should work.

I leave it to you to google no. 10,000 and compare digits. 😁

a, b = 0, 1
count = 0
while True:
count += 1
if count == 10000:
print(count, b)
break
a, b = b, a+b

Answer 2

Hm, you can translate the iterative approach I showed here, but you'll probably have to do some 'array math' in order to prevent overflow:

Simulate by-hand addition, digit by digit, carry and all that, and store the digits in a vector.

Two codes where you hopefully find something:

https://code.sololearn.com/cz7MX8k6RK0d/?ref=app
https://code.sololearn.com/cV3o3NWxVZ11/?ref=app

Answer 3

right there I think it I got this thanks, HonFu :)

Answer 4

Thanks buddy, but for some reason I can't use Python , I am able to code in Python but I should be only using c++ and besides the actual boundary for n is 10^18 which is a gigantic number