Counting big Fibonacci numbers

Question

I am trying to find the last digit of Big Fibonacci numbers, my script can count them and find the last digit fast but when I try to compute numbers from 1000 I get RecursionError.

Here is my scrip:

cache = {}

def last_digit_of_fibonacci_number(n):
    assert 0 <= n <= 10 ** 7

    if n in cache:
        return cache[n]

    if n == 1 or n == 2:
        return 1
    elif n == 0:
        return 0
    else:
        result = (last_digit_of_fibonacci_number(n - 1) + last_digit_of_fibonacci_number(n - 2)) % 10
        cache[n] = result
        return result

any ideas of how to fix my issue without resetting the recursion limit using setrecursionlimit()?

similar post [here](https://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series/18172463) and [here](https://stackoverflow.com/questions/14661633/finding-out-nth-fibonacci-number-for-very-large-n) — Kofi, Jan 10 '22 at 12:50
Even if you're caching, if you call last_digit_of_fibonacci_number(1005) without having called that function before, it's going to require a thousand recursive calls. With caching, you successfully avoided the exponential number of recursive calls, which is quite good already, but not enough to compute values after 1000 in python. — Stef, Jan 10 '22 at 12:53
But note that if you try: `last_digit_of_fibonacci_number(990); last_digit_of_fibonacci_number(1980); last_digit_of_fibonacci_number(2970); last_digit_of_fibonacci_number(4960); print(last_digit_of_fibonacci_number(5950))` in that order, it should work without RecursionError. — Stef, Jan 10 '22 at 12:55
The bottom-line is that you should always avoid recursion in python, except if you know for a fact that the recursion is very shallow. There are some programming languages in which recursion works very well. But python is not one of them. In python, prefer the iterative approach. — Stef, Jan 10 '22 at 13:09
You need to move from O(n) algorithms, which you get with memoization, to O(log n) algorithms in order to break past the recursion barrier at n ~ 1000. See https://www.nayuki.io/page/fast-fibonacci-algorithms for discussion of some of the alternatives. The multiplcations get slow once you get into big integers, but that's true of the O(n) iterative solution as well, so doing far fewer multiplications is still a win. — pjs, Jan 10 '22 at 13:48
Does this answer your question? [Finding out nth fibonacci number for very large 'n'](https://stackoverflow.com/questions/14661633/finding-out-nth-fibonacci-number-for-very-large-n) — pjs, Jan 10 '22 at 13:50
`int('011235831459437077415617853819099875279651673033695493257291'[n%60])` — Paul Hankin, Jan 10 '22 at 14:19
Someone should comment that even if you don't know about the pisano period, you don't need bignums to calculate the last digit of a large fibonacci number: just compute your fibonacci number modulo 10 using any reasonable algorithm (for up to 10**7, O(n) is probably fine). `def g(n): a, b=0, 1; for _ in range(n): a, b, = b, (a+b)%10; return a` computes the last digit of fib(1e7) in half a second. — Paul Hankin, Jan 10 '22 at 14:32

score 2 · Accepted Answer · answered Jan 10 '22 at 14:07

Note that since you are only interested in the last digit of each Fibonacci number, the sequence of results is cyclic: As soon as there are two subsequent results that equal two previous subsequent results, the values repeat.

For example, the results for 1 and 2 are both 1, so as soon as two subsequent later return values are also both 1, we have a cycle. Let's find these cycles:

last_digit_of_fibonacci_number(250)

for n in range(3, 250):
    if cache[n] == cache[n + 1] == 1:
        print(n)

So the length of this cycle is 60, and you can alter your function to exploit this fact:

cache = {}

def last_digit_of_fibonacci_number(n):
    assert 0 <= n <= 10 ** 7

    if n in cache:
        return cache[n]
    if n == 1 or n == 2:
        return 1
    if n == 0:
        return 0
    
    if n > 61:
        n = n % 60
        
    result = (last_digit_of_fibonacci_number(n - 1) 
              + last_digit_of_fibonacci_number(n - 2)) % 10
    cache[n] = result
    return result

Since the cycle length is smaller than the recursion limit, this will avoid any recursion depth problems.

Counting big Fibonacci numbers

1 Answers1