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

然后returnsb mod 1000，它给出计算的最后3位数字。

到目前为止代码 returns:

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

在最后一个代码中，代码继续运行，但如果迭代次数太大，则需要很长时间，所以它永远不会完成。

有没有办法更快地进行这种计算，或者以更好的方式获得所需的值（mod 1000 次计算完成这么多次）？

Answer 1

数量太大了。处理这个功能需要这么长时间是正常的。您可以尝试使用此进行检查：

long startTime = System.currentTimeMillis(); .....your program.... long endTime = System.currentTimeMillis(); long totalTime = endTime - startTime; System.out.println(totalTime);

预计完成时间。

Answer 2

是的，每次计算都保留运行模数。您不需要计算所有数字，因为您只对最后 3 个数字感兴趣。

第一个改进是：

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.mod(THOUSAND); // <-- only keep the modulo each time so as not calculate all digits
    }
    return b.mod(THOUSAND);
}

通过这样做，您可以意识到您不需要 BigInteger 开始。有关的数字变得足够低，以至于它们保存在原始数据类型中。因此，使用 long（甚至 int）：它的性能会高很多，因为您没有使用 BigInteger.

的开销

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

请注意，此代码仍然不会为您提供 9223372036854775807 的结果作为输入。根本不可能循环9223372036854775807次。但是，这在我的旧机器上不到 5 秒就产生了 1 亿的正确结果。

Answer 3

如果您使用 int 进行计算，速度会快很多。但是，您会意识到在每次迭代中 a 和 b 只有 1,000,000 个可能的起始值，这意味着 a 和 a 的值和结果的最长可能序列b不重复就是一百万。即你可以 n % 1,000,000 很可能有更短的重复序列。

之所以说只有a和b的低三位有关系，是因为你mod 1000的结果，所以无所谓[=12=的高位] 和 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;
}

Java 中的大数计算？

Big numbers calculations in Java?

java

biginteger

long-integer