Last Digit of a Large Fibonacci Number fast algori

Question

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

Problem Description Task. Given an integer

标签： java algorithm fibonacci biginteger

举报

Answer 1

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;
}

Answer 2

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