java - 新的 BigInteger(String) 性能/复杂性

Question

我想知道使用 new BigInteger(String) 构造函数构造 BigInteger 对象的性能/复杂性。

考虑以下方法:

  public static void testBigIntegerConstruction()
  {
    for (int exp = 1; exp < 10; exp++)
    {
      StringBuffer bigNumber = new StringBuffer((int) Math.pow(10.0, exp));
      for (int i = 0; i < Math.pow(10.0, exp - 1); i++)
      {
        bigNumber.append("1234567890");
      }

      String val = bigNumber.toString();
      long time = System.currentTimeMillis();
      BigInteger bigOne = new BigInteger(val);
      System.out.println("time for constructing a 10^" + exp
          + " digits BigInteger : " + ((System.currentTimeMillis() - time))
          + " ms");
    }
  }

此方法创建 BigInteger 字符串对象，10^x 个数字，其中 x=1 开始，并且随着每个数字增加迭代。它测量并输出构造相应的 BigInteger 对象所需的时间。

在我的机器上(Intel Core i5 660，JDK 6 Update 25 32 位)输出是:

time for constructing a 10^1 digits BigInteger : 0 ms
time for constructing a 10^2 digits BigInteger : 0 ms
time for constructing a 10^3 digits BigInteger : 0 ms
time for constructing a 10^4 digits BigInteger : 16 ms
time for constructing a 10^5 digits BigInteger : 656 ms
time for constructing a 10^6 digits BigInteger : 59936 ms
time for constructing a 10^7 digits BigInteger : 6227975 ms

虽然忽略了 10^5 行(由于(处理器)缓存效应​​、JIT 编译等可能引入的失真)，我们可以清楚地看到 O(n^2) 的复杂度 这里。请记住，由于不变性，BigInteger 上的每个操作都会创建一个新操作，这是对大数字的主要性能惩罚。

问题:

• 我错过了什么吗？

• 为什么会这样？

• 这在最近的 JDK 中是否已修复？

• 还有其他选择吗？

更新:

我做了进一步的测量，我可以从一些答案中证实这个说法:
BigInteger 似乎针对后续的数值运算进行了优化，但代价是大量的构建成本更高这对我来说似乎是合理的。

Answer 1

从 source 简化某种程度上，这是因为在“传统的”字符串解析循环中

for each digit y from left to right:
  x = 10 * x + y

您遇到的问题是，10 * x 的时间不可避免地与 x 的长度呈线性关系，并且该长度会或多或少地增长一个常数因子每一个数字，也是不可避免的。

(实际的实现比这更聪明——它试图一次解析一个 int 的二进制数字，因此循环中的实际乘数更有可能是 1 或20 亿——但是，是的，它总体上仍然是二次方。)

就是说，10^6 位的数字至少是一个 googol，这比我听说过的任何用于加密目的的数字都大。您正在解析一个占用 2 MB 内存 的字符串。是的，这需要一段时间，但我怀疑 JDK 作者没有看到针对这种罕见用例进行优化的意义。