Last Digit of a Large Fibonacci Number fast algorithm

Question

I'm trying to solve Fibonacci using java, but my code takes so long with big numbers.

Problem Description Task. Given an integer , find the last digit of the th Fibonacci number (that is, mod 10).

Input Format. The input consists of a single integer .

Constraints. 0 ≤ ≤ 10⁷.

Output Format. Output the last digit of .

My code:

public class FibonacciLastDigit {

private static int getFibonacciLastDigitNaive(int n) {
    if (n <= 1) {
        return n;
    }
    BigInteger first = BigInteger.ZERO;
    BigInteger second = BigInteger.ONE;
    BigInteger temp;

    for (int i = 1; i < n; i++) {
        temp = first.add(second);
        first = second;
        second = temp;
    }
    return second.mod(BigInteger.TEN).intValue();
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println(getFibonacciLastDigitNaive(n));
}}

My code fails if input = 613455 it takes 30 seconds to get value and max allowed time is 1.5 second.

I had to use big Integer because long isn't enough.

I don't get it.. constraint says n<=107? Why enter 613455 then? — Yamuk, Feb 01 '19 at 13:17
[Hint: modulo addition](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction). — meowgoesthedog, Feb 01 '19 at 13:20
I don't know why this happens if I stop him from entering more than 107 test case fails, so i had to remove this constraint — Kero Fawzy, Feb 01 '19 at 13:21
Yes it is meant to fail, isn't it? That means there won't be any input higher than 107. Also, you don't need big numbers. @meowgoesthedog's hint is excellent. — Yamuk, Feb 01 '19 at 13:23
If you are interested in a solution for large n and other modulo than 10, read [fibonacci matrix method](http://raganwald.com/2015/12/20/an-es6-program-to-compute-fibonacci.html). It works based on calculating the powers of the 2x2 matrix (0 1 1 1) — Adder, Feb 01 '19 at 13:27
I expect "107" should be 10⁷. I made an edit to fix the question. — Paul Hankin, Feb 01 '19 at 13:49
@PaulHankin: That makes sense, by why can't the OP notice this and clarify? — President James K. Polk, Feb 01 '19 at 17:25
See this [related question](https://stackoverflow.com/q/14661633/238704), and in particular [this answer](https://stackoverflow.com/a/48171368/238704) — President James K. Polk, Feb 01 '19 at 18:46

Ole V.V. · Answer 1 · 2019-02-01T13:35:15.187

14

There is a cycle in the last digit of the Fibonacci numbers. It repeats for every 60 numbers. So just build a table of the last digit of the first 60 numbers, then do a modulo 60 operation on the input and a table lookup.

You may see the cycle in any online (or offline) table of Fibonacci numbers. One link at the bottom.

For building the table, for each calculated number you may subtract 10 if it’s over 9 since you only need the last digit, and the last digit of each number only depends on the last digit of the two previous numbers. You can use int math (you neither need long nor BigInteger).

Link: The first 300 Fibonacci numbers, factored

edited Feb 01 '19 at 13:35

answered Feb 01 '19 at 13:24

Ole V.V.

81,772
15
137
161

2

If this is anything else than a comp sci exercise (and even then), then this should be the only acceptable answer. Because this algorithm pretty much guarantees constant computational complexity. – apriede Feb 04 '19 at 15:17

score 12 · Accepted Answer · answered Feb 01 '19 at 13:27

Your implementation is indeed naive, because you're asked to get the last digit of the Fibonacci number not the actual Fibonacci number itself. You only need to keep the track of the last digit, other digits don't matter.

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println(getFibonacciLastDigit(n));
}

private static int getFibonacciLastDigit(int n) {
    if (n <= 1) {
        return n;
    }
    int first = 0;
    int second = 1;
    int temp;

    for (int i = 1; i < n; i++) {
        temp = (first + second) % 10;
        first = second;
        second = temp;
    }
    return second;
}

This is also less than optimal, since there is an algorithm that takes O(log(n)) steps in addition to the algorithm in the other answer. — President James K. Polk, Feb 01 '19 at 17:27

score 0 · Answer 3 · answered Jun 05 '21 at 17:16

Here I attach a program in c++ and can use the logic to write the program in java. By this code, we only need to find the 60th Fibonacci number. And this will execute very fastly, doesn't need to hold large number also.

#include <iostream>

using namespace std;

long long int findOutTheFibonacciNumber(int n)
{
    int number = n % 60;
    if (number <= 1)
    {
        return number;
    }
    else
    {
        long long int a = 0;
        long long int b = 1;
        long long int c = 1;
        for (int i = 2; i <= number; i++)
        {
            c = (long long)a + b;
            a = b;
            b = c;
        }
        return c % 10;
    }
}

int main()
{
    int n;
    cin >> n;
    cout << findOutTheFibonacciNumber(n);
    return 0;
}

score -1 · Answer 4 · edited Jun 06 '21 at 15:47

-1

Code in py must be

lookup = {0:0,1:1}
N = int(input())
for i in range(2,N+1):
       lookup[i] = (lookup[i-1] + lookup[i-1])%10
print(lookup[N])

edited Jun 06 '21 at 15:47

gdrt

3,160
4
37
56

answered Jun 08 '20 at 02:43

Shubham Kondekar

1
3

Last Digit of a Large Fibonacci Number fast algorithm

4 Answers4