Last Digit of a Large Fibonacci Number

Source

Introduction

The goal is to find the last digit of the n-th Fibonacci number. The problem is that Fibonacci numbers grow exponetially fast. For instance

\[ F_{200} = 280 571 172 992 510 140 037 611 932 413 038 677 189 525 \]

So even our iterative version will prove too slow. Also, it may produce numbers that are too large to fit in memory. So instead we are going to only save the last digit of each number.

\[ F_i \gets (F_{i-1} + F_{i-2}) \mod 10 \]

Problem Description

  Description
Task Given an integer n, find the last digit of the /n/th Fibonacci number \(F_n\) (\(F_n \mod 10\))
Input A single integer n.
Constraints \(0 \le n \le 10^7\)
Output The last digit of \(F_n\)

Samples

Input Output
3 2
331 9
327305 5

Constants

MAX_INPUT = 10**7
MAX_TIME = 5

Imports

from datetime import (
    datetime,
    timedelta,
    )
# this project
from algorithmic_toolbox.helpers import time_it

Naive Implementation

By taking the modulo of 10 for the final number you reduce it to the final digit because it's the remainder of some number times 10. For example, 112 is 110 + 2, so \(112 \mod 10\) is \(112 - (11 \times 10) = 2\). 

def get_fibonacci_last_digit_naive(n):
    if n <= 1:
	return n

    previous = 0
    current  = 1

    for _ in range(n - 1):
	previous, current = current, previous + current
    return current % 10

time_it(get_fibonacci_last_digit_naive, "Naive", 3, 2, max_input=MAX_INPUT)

time_it(get_fibonacci_last_digit_naive, "Naive", 331, 9, max_input=MAX_INPUT)

Modulo Version

Each number in the sequence is the sum of the previous two numbers. The last digit is always the sum of the last digits of the previous two numbers. So to calculate the last digit you only need to keep track of the last digit of each number. By taking the modulus of 10, you are always. 

first = (0, 1)
def get_fibonacci_last_digit_modulo(n):
    if n in first:
	return n

    previous, current = first

    for _ in range(n - 1):
	previous, current = current, (previous + current) % 10
	print("Current: {}".format(current))
    return current

time_it(get_fibonacci_last_digit_modulo, "Modulo", 3, 2, max_input=MAX_INPUT)

time_it(get_fibonacci_last_digit_modulo, "Modulo", 331, 9, max_input=MAX_INPUT)

time_it(get_fibonacci_last_digit_modulo, "Modulo", 327305, 5, max_input=MAX_INPUT)

time_it(get_fibonacci_last_digit_modulo, "Modulo", 200, 5, max_input=MAX_INPUT)

This is the grader output. 

Good job! (Max time used: 0.12/5.00, max memory used: 9580544/536870912.)