减少此特定斐波那契数代码所用时间的方法？

Question

作为一个有趣的项目，我开始了这段代码，每次我都想找到斐波那契数平方的最后一位。它工作正常，但我想减少它花费的时间...有什么建议吗？

琐事：我求斐波那契数，平方，然后求和。

import java.util.*;
import java.math.*;

public class FibonacciSumSquares {
    private static BigInteger getFibonacciSumSquares(int n) {
        if(n<=2)return BigInteger.valueOf(n);
    BigInteger sum = BigInteger.valueOf(2);
    long last = 1, lastTwo = 1, current = 0;
    BigInteger lastBigInteger = BigInteger.ONE;
    BigInteger lastTwoBigInteger = BigInteger.ONE;
    BigInteger currentBigInteger;
    boolean isUsePrimary = true;

    for (int i = 3; i <=n; i++) {
    if (isUsePrimary){
        current = last + lastTwo;
        current = current * current;
        if (String.valueOf(current).length()<12) {
            lastTwo = last;
            last = current;
            sum = sum.add(BigInteger.valueOf(current));
        } else {
            isUsePrimary = false;
            lastTwoBigInteger = BigInteger.valueOf(lastTwo);
            lastBigInteger = BigInteger.valueOf(last);
            currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
            currentBigInteger = currentBigInteger.pow(2);

            sum = sum.add(currentBigInteger);
        }
    } //end of outer if
    else {
        currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
        lastTwoBigInteger=lastBigInteger;
        currentBigInteger = currentBigInteger.pow(2);
        lastBigInteger= currentBigInteger;
        sum = sum.add(currentBigInteger);
    }
   }//end of for
  return sum.remainder(BigInteger.valueOf(10));
}//end of function


public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();

    System.out.println(getFibonacciSumSquares(n));
}

}

Answer 1

哦，你只想要最后一位数字，这是经典的数学转折:-)

要注意的是，如果您只需要最后一位，则可以忽略所有步骤之间的所有其他数字，只要它只是加法或乘法即可。

您的公式基本上是 f(n+2) = [f(n) + f(n+1)]^2，为此，最后一位仅取决于先前结果的最后一位.此外，总和的最后一位仅取决于您添加的每个数字的最后一位。

因此您可以对每个当前值或总和值执行 mod 10，并且您不需要 BigInteger 甚至 long 来执行此操作，您可以只使用 int。

private static int getFibonacciSquaredSumMod10(int n) {
    if (n <= 1)
        return n;
    int sum = 0;
    int last = 1, lastTwo = 1, current = 0;

    for (int i = 2; i <= n; i++) {
            current = last + lastTwo;
            current = (current * current) % 10;
            lastTwo = last;
            last = current;
            sum = (sum + current) % 10;
    }
    return sum;
}

减少此特定斐波那契数代码所用时间的方法？

way to reduce time taken by this particular code for fibonacci numbers?

java

performance

fibonacci

time-complexity