1

我注意到，在使用 Java 的 BigInteger 类时，基本算术运算似乎比它们的原始运算效率低得多，即使使用相同的数字和运算也是如此。使用数字的 BI 表示的算法比使用相同数字的长表示的完全相同的算法花费的时间要多得多。

为了说明我的意思，我提供了一个工作代码示例。在下面的示例中，我简单地遍历了 1 到 1000000000 之间的所有整数，对每次迭代执行 mod 2 操作，然后打印出循环的总运行时间。我首先使用 long，然后使用 BigInteger：

import java.math.BigInteger;

public class FunWithNumbers {

    public static void main(String[] args) {
        
        long myNumL = 100000000L; // Long representation of some number n
        BigInteger myNumB = new BigInteger("100000000"); // BI representation of same number
        
        /* long version */
        long startTime = System.nanoTime();
        for (long i=1L; i<= myNumL; i++) {
            long a = myNumL % 2;
        }
        System.out.println("Total computation time (long representation): " + 
        (System.nanoTime() - startTime)*Math.pow(10, -9) + " seconds.");
        
        
        /* BI version */
        startTime = System.nanoTime();
        BigInteger index = new BigInteger("1");
        while (!index.equals(myNumB)) {
            BigInteger b = myNumB.remainder(index);
            index = index.add(BigInteger.ONE);
        }
        System.out.println("Total computation time (BI representation): " + 
        (System.nanoTime() - startTime)*Math.pow(10, -9) + " seconds.");
    }
}

这会生成以下输出：

总计算时间（长表示）：0.035671096 秒。

总计算时间（BI 表示）：7.031978092 秒。

如您所见，运行时间甚至无法进行远程比较。我的问题是我需要处理太大而无法放入“长”数据类型的数字。

有没有办法恢复原始算术的效率，并且仍然能够处理超过 long 的最大大小的任意大数字？

如果需要的话，我可以切换到另一种语言；我绝不会被 Java 束缚。

4

3 回答 3

2

我建议你尝试 C 或 C++。有各种 C/C++ 库可以有效地进行更大的整数运算。例如，我遇到了一个看起来很有希望的名为“ ttmath ”的东西。

效率问题的很大一部分BigInteger是它用不可变对象对数字进行建模。所以每一个大的算术运算都会导致一个新BigInteger的被创建。

于 2013-10-05T06:26:08.020 回答
0

有没有办法恢复原始算术的效率，并且仍然能够处理超过 long 的最大大小的任意大数字？

不，在 Java 的情况下。

于 2013-10-05T06:13:50.573 回答
-1

如果您不需要确切的答案，请考虑加倍。它具有范围广和非常快的算术，代价是仅代表 53 个有效位。

于 2013-10-05T06:41:58.163 回答