java - Java中的大数计算？

Question

我有这段用于计算一些数字的 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)？

Answer 1

如果您使用 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;
}