Python: Calculate the last digit of a large Fibonacci Number with less time

Question

# Uses python3

# Compute the Last Digit of a Large Fibonacci Number
def Fib_Last_Digit(n):

    if n == 0 : return 0
    elif n == 1: return 1
    else:

        a,b = 0,1
        for i in range(1,n):
            c = a + b;
            a = b;
            b = c;
        # Calculate the last digit of the final number 
        lastdigit = int(repr(c)[-1]);
        print(lastdigit);

n = int(input(""));
Fib_Last_Digit(n);

This code works very well. However, I want to revise the algorithm to save more time and memory. By the way, the input and output should be kept the same with the previous version.

To get the last digit, you might as well do modulo 10: `lastdigit = c % 10` — L3viathan, Oct 17 '16 at 20:08
I try this way. However, when n is given as 999999, the calculation takes as much time as the previous one. — , Oct 17 '16 at 20:10
http://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series — Padraic Cunningham, Oct 17 '16 at 20:25

L3viathan · Accepted Answer · 2020-06-21T20:07:42.807

Only keeping the last digit during calculation saves a lot of time:

def fib_last_digit(n):
    if n < 2: return n
    else:
        a, b = 0, 1
        for i in range(1,n):
            a, b = b, (a+b) % 10
        print(b)

n = int(input())
fib_last_digit(n)

Handling numbers that fit in fewer bytes saves time.

When you're working with huge numbers, you can save a lot of time using the answer described here, slightly modified to only keep track of the last digit:

def fib_last_digit(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = (v2*v2) % 10
        v1, v2, v3 = (v1*v1+calc) % 10, ((v1+v3)*v2) % 10, (calc+v3*v3) % 10
        if rec == '1': v1, v2, v3 = (v1+v2) % 10, v1, v2
    return v2

And finally, based on the concept described in Eugene Yarmash's answer (the last digits repeat every 60 steps) we can make an even faster solution (O(1)):

def fib_last_digit(n):
    return (
        [1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0]
        [n % 60 - 1]
    )

I have another question: When I change modulo 10 to modulo m (any positive integer) and run a case as n = 99999999999999999, m = 2, it takes me much time. Do you have any good solutions? — , Oct 17 '16 at 20:50
I added a superfast solution stolen from [here](http://stackoverflow.com/a/23462371/1016216). — L3viathan, Oct 18 '16 at 10:39

Eugene Yarmash · Answer 2 · 2019-04-16T13:33:58.173

The series of final digits of Fibonacci numbers repeats with a cycle length of 60. Therefore, the Nth Fibonacci number has the same last digit as the (N % 60)th, which should be pretty fast to calculate. As an additional optimization, you can keep only the last digit of each term:

def fib_last_digit(n):
    a, b = 0, 1
    for i in range(n % 60):
        a, b = b, (a + b) % 10
    return a    

print([fib_last_digit(n) for n in range(1, 11)])

Output:

[1, 1, 2, 3, 5, 8, 3, 1, 4, 5]

score 0 · Answer 3 · answered Oct 17 '16 at 20:20

0

def fib(n): 
    phi = (1 + 5 ** 0.5) / 2
    fib_n = round(((phi** n) - (phi**-n) )/(5 ** .5))
    return fib_n % 10

Phi is your friend.

answered Oct 17 '16 at 20:20

corn3lius

4,857
2
31
36

Doesn't work with very large numbers (`OverflowError: (34, 'Result too large')`) – L3viathan Oct 18 '16 at 10:41

score 0 · Answer 4 · answered Oct 30 '18 at 22:22

def fib_digit(n):
    f=[1,1]
    for i in range(2,n):
        f.append((f[i-1]+f[i-2])  % 10 ) 
    return f[-1]

n = int(input())
print(fib_digit(n))

This is one of the simplest answers,i'm sure, there is a faster algorithm.

Here is what I found:

f1, f2 = 0, 1
for i in range(int(input())-1):
    f1, f2 = f2, (f1+f2)%10
print(f2)

score 0 · Answer 5 · answered Sep 11 '19 at 23:51

It took only --- 0.002832174301147461 seconds --- to complete the code.

import time
n = 100000000000000000000000000000000000000000


def printfib(previous, latest, n):
    if(latest > n):
        return
    print(', ', latest, end='')
    printfib(latest, previous + latest, n)


start_time = time.time()
print(0, end='')
printfib(0, 1, n)
print(" ")
print("--- %s seconds ---" % (time.time() - start_time))

Python: Calculate the last digit of a large Fibonacci Number with less time

5 Answers5