我对pow(指数)方法做了一些测试.不幸的是,我的数学技能不足以解决以下问题.
我正在使用此代码：
BigInteger.valueOf(2).pow(var);
结果：
> var |时间以毫秒为单位
> 2000000 | 11450
> 2500000 | 12471
> 3000000 | 22379
> 3500000 | 32147
> 4000000 | 46270
> 4500000 | 31459
> 5000000 | 49922
看到？ 2,500,000指数的计算速度几乎与2,000,000一样快. 4,000的计算速度比4,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,null);
basetoPow2 = trustedStripLeadingZeroInts(basetoPow2);
}
}
return new BigInteger(result,newSign);
}
解决方法
该算法使用重复平方(squaretoLen)和乘法(multiplyToLen).这些操作的运行时间取决于所涉及的数字的大小.在计算结束时大数的乘法比开始时的大得多.
乘法仅在此条件为真时完成：((指数& 1)== 1).平方运算的数量取决于数字中的位数(不包括前导零),但只有设置为1的位才需要乘法.通过查看二进制文件,可以更容易地看到所需的操作代表人数：
2000000: 0000111101000010010000000 2500000: 0001001100010010110100000 3000000: 0001011011100011011000000 3500000: 0001101010110011111100000 4000000: 0001111010000100100000000 4500000: 0010001001010101000100000 5000000: 0010011000100101101000000
请注意,2.5M和4.5M是幸运的,因为它们设置的高位比周围的数字少.下次发生这种情况的时间是8.5M：
8000000: 0011110100001001000000000 8500000: 0100000011011001100100000 9000000: 0100010010101010001000000
甜蜜点是2的精确力量.
1048575: 0001111111111111111111111 // 16408 ms 1048576: 0010000000000000000000000 // 6209 ms