java.math.BigInteger pow(exponent) 问题

Question

我对 pow(exponent) 方法做了一些测试。不幸的是，我的数学能力不足以解决以下问题。

我正在使用这段代码:

BigInteger.valueOf(2).pow(var);

结果:

• 变种 |以毫秒为单位的时间
• 2000000 | 11450
• 2500000 | 12471
• 3000000 | 22379
• 350​​0000 | 32147
• 4000000 | 46270
• 4500000 | 31459
• 5000000 | 49922

看到了吗？ 2,500,000 指数的计算速度几乎与 2,000,000 一样快。 4,500,000 的计算速度比 4,000,000 快得多。

这是为什么？

为了给你一些帮助，下面是 BigInteger.pow(exponent) 的原始实现:

 public BigInteger pow(int exponent) {
    if (exponent < 0)
        throw new ArithmeticException("Negative exponent");
    if (signum==0)
        return (exponent==0 ? ONE : this);

    // Perform exponentiation using repeated squaring trick
        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
    int[] baseToPow2 = this.mag;
        int[] result = {1};

    while (exponent != 0) {
        if ((exponent & 1)==1) {
        result = multiplyToLen(result, result.length, 
                                       baseToPow2, baseToPow2.length, null);
        result = trustedStripLeadingZeroInts(result);
        }
        if ((exponent >>>= 1) != 0) {
                baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
        baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
        }
    }
    return new BigInteger(result, newSign);
    }

Answer 1

该算法使用重复的平方 (squareToLen) 和乘法 (multiplyToLen)。这些操作运行的时间取决于所涉及的数字的大小。接近计算末尾的大数乘法比开始时的大数乘法代价高得多。

仅当此条件为真时才执行乘法:((exponent & 1)==1)。平方运算的次数取决于数字中的位数(不包括前导零)，但只有设置为 1 的位才需要乘法。通过查看二进制更容易看出所需的运算数字的表示:

2000000: 00001111010000100100000002500000: 00010011000100101101000003000000: 00010110111000110110000003500000: 00011010101100111111000004000000: 00011110100001001000000004500000: 00100010010101010001000005000000: 0010011000100101101000000

请注意，2.5M 和 4.5M 是幸运的，因为它们设置的高位比它们周围的数字少。下次发生这种情况是在 8.5M:

8000000: 00111101000010010000000008500000: 01000000110110011001000009000000: 0100010010101010001000000

甜蜜点是 2 的精确幂。

1048575: 0001111111111111111111111 // 16408 ms1048576: 0010000000000000000000000 //  6209 ms