java.math.BigInteger pow(指数)问题
我对 pow(exponent) 方法做了一些测试。不幸的是，我的数学能力不足以解决以下问题。
我正在使用这段代码：
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,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);
}
I did some tests on pow(exponent) method. Unfortunately, my math skills are not strong enough to handle the following problem.
I'm using this code:
BigInteger.valueOf(2).pow(var);
Results:
- var | time in ms
- 2000000 | 11450
- 2500000 | 12471
- 3000000 | 22379
- 3500000 | 32147
- 4000000 | 46270
- 4500000 | 31459
- 5000000 | 49922
See? 2,500,000 exponent is calculated almost as fast as 2,000,000. 4,500,000 is calculated much faster then 4,000,000.
Why is that?
To give you some help, here's the original implementation of 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);
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
该算法使用重复平方 (
squareToLen) 和乘法 (multiplyToLen)。这些操作运行的时间取决于所涉及数字的大小。接近计算结束时的大数乘法比开始时的大数乘法要昂贵得多。仅当以下条件为真时才会进行乘法：
((exponent & 1)==1)。平方运算的次数取决于数字中的位数（不包括前导零），但只有设置为 1 的位才需要乘法。通过查看二进制更容易了解所需的运算数字的表示：请注意，2.5M 和 4.5M 很幸运，因为它们的高位设置比它们周围的数字要少。下一次发生这种情况是在 8.5M 处：
最佳点恰好是 2 的幂。
The algorithm uses repeated squaring (
squareToLen) and multiplication (multiplyToLen). The time for these operations to run depends on the size of the numbers involved. The multiplications of the large numbers near the end of the calculation are much more expensive than those at the start.The multiplication is only done when this condition is true:
((exponent & 1)==1). The number of square operations depends on the number of bits in the number (excluding leading zeros), but a multiplication is only required for the bits that are set to 1. It is easier to see the operations that are required by looking at the binary representation of the number:Note that 2.5M and 4.5M are lucky in that they have fewer high bits set than the numbers surrounding them. The next time this happens is at 8.5M:
The sweet spots are exact powers of 2.
只是猜测：
指数是逐位处理的，如果最低有效位是 1，则需要完成额外的工作。
如果 L 是指数中的位数
A 为 1 的位数
t1 处理公共部分的时间
t2 是 LSbit 为 1 时的额外处理时间，
则运行时间将为
Lt1 + At2
或者时间取决于二进制表示中 1 的数量。
现在写一个小程序来验证我的理论......
Just a guess:
the exponent is handled bit by bit, and if the least significant bit is 1 additional work is done.
If L is the number of bits in the exponent
and A the number of bits which are 1
and t1 the time to process the common part
and t2 the additional time processing when the LSbit is 1
then the run time would be
Lt1 + At2
or the time is dependent on the number of 1's in the binary representation.
now writing a little program to verify my theory...
我不确定你已经运行了多少次计时。正如一些评论者指出的那样，您需要多次对操作进行计时才能获得良好的结果（而且它们仍然可能是错误的）。
假设你已经很好地把握了时间，请记住，数学中有很多捷径可以走。您不必执行 5*5*5*5*5*5 运算来计算 5^6。
这是一种可以更快地完成此操作的方法。 http://en.wikipedia.org/wiki/Exponentiation_by_squaring
I'm not sure how many times you've run your timings. As some of the commenters have pointed out, you need to time operations many, many times to get good results (and they can still be wrong).
Assuming you have timed things well, remember that there are a lot of shortcuts that can be taken in math. You don't have to do the operations 5*5*5*5*5*5 to calculate 5^6.
Here is one way to do it much more quickly. http://en.wikipedia.org/wiki/Exponentiation_by_squaring