Python: Calculate the last digit of a large Fibonacci Number with less time
fibonacci, python-3.x
Solution
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]
)
Problem
``` # 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.