Java中的大数字计算？

我有这个用于计算某些数字的Java代码

import java.math.BigInteger;

class Challenge {

    final static BigInteger THOUSAND = new BigInteger("1000");

    private static BigInteger compute(long n) {
        BigInteger a = BigInteger.ONE;
        BigInteger b = BigInteger.ONE;
        for (long i = 0; i < n; i++) {
            BigInteger next = b.multiply(b).add(a);
            a = b;
            b = next;
        }
        return b.mod(THOUSAND);
    }

    public static void main(String args[]) {
        for (long n : new long[] { 1L, 2L, 5L, 10L, 20L, Long.MAX_VALUE }) {
            System.out.print(n + " ---> ");
            System.out.println(compute(n));
        }
    }
}

代码根据给定的长数(1,2,5等)迭代几次,从a=1和开始b=1:

next = (b*b)+a
a = b
b = next

然后它返回b mod 1000,它给出了计算的最后3位数.

到目前为止,代码返回:

1 ---> 2
2 ---> 5
5 ---> 783
10 ---> 968
20 ---> 351
9223372036854775807 ---> 

在最后一个代码保持工作,但如果迭代是如此之大,它需要永远,所以它永远不会完成.

有没有办法更快地进行这种计算,或者以更好的方式获得所需的值(多次计算的mod 1000)？

如果你使用一个int计算,它会快得多.然而,你会更快地意识到在每次迭代中只有1,000,000个可能的起始值a,b这意味着最长的值序列和结果有a和b没有重复是一百万.即你n % 1,000,000很可能有一个较短的重复序列.

我说只有较低的三个数字的原因a和b问题是,你mod 1000的结果,所以没有关系什么的高数位a,并b在它们被忽略,因此所有你关心的是价值观0,以999

您可以记住从1,1开始的所有可能结果,它只是一个查找.

private static long compute(long n) {
    int a = 1;
    int b = 1;
    for (int i = 0, max = (int) (n % 1000000); i < max; i++) {
        int next = b * b + a;
        a = b;
        b = next % 1000;
    }
    return b % 1000;
}