[简短回答：糟糕的基准测试方法。你可能认为我现在已经明白了。]
该问题被表述为“找到一种快速计算x^y的方法，其中x和y是正整数”。典型的“快速”算法如下所示：
public long fastPower(int x, int y) {
// Replaced my code with the "better" version described below,
// but this version isn't measurably faster than what I had before
long base = x; // otherwise, we may overflow at x *= x.
long result = y % 2 == 1 ? x : 1;
while (y > 1) {
base *= base;
y >>= 1;
if (y % 2 == 1) result *= base;
}
return result;
}
我想看看这比调用 Math.pow() 或使用简单的方法（例如将 x 乘以 y 次）快多少，如下所示：
public long naivePower(int x, int y) {
long result = 1;
for (int i = 0; i < y; i++) {
result *= x;
}
return result;
}
编辑：好的，有人（正确地）向我指出我的基准测试代码没有消耗结果，这完全让一切都失败了。一旦我开始使用结果，我仍然发现简单方法比“快速”方法快约 25%。
原文：
I was very surprised to find that the naive approach was 4x faster than the "fast" version, which was itself about 3x faster than the Math.pow() version.
我的测试使用 10,000,000 次试验（然后是 1 亿次，只是为了绝对确保 JIT 有时间预热），每个试验都使用随机值（以防止调用被优化掉）2
据我所知，对于小指数，天真的版本预计会更快。 “快速”版本有两个分支而不是一个，并且通常会执行两倍于天真的分支的算术/存储操作 - 但我预计对于大指数，这仍然会导致快速方法节省一半的操作最好的情况和最坏的情况大致相同。
任何人都知道为什么简单的方法会比“快速”版本快得多，即使数据偏向“快速”版本（即更大的指数）？该代码中的额外分支是否会在运行时造成如此大的差异？
基准测试代码（是的，我知道我应该使用一些框架来进行“官方”基准测试，但这是一个玩具问题）-更新以热身并使用结果：
PowerIf[] powers = new PowerIf[] {
new EasyPower(), // just calls Math.pow() and cast to int
new NaivePower(),
new FastPower()
};
Random rand = new Random(0); // same seed for each run
int randCount = 10000;
int[] bases = new int[randCount];
int[] exponents = new int[randCount];
for (int i = 0; i < randCount; i++) {
bases[i] = 2 + rand.nextInt(2);
exponents[i] = 25 + rand.nextInt(5);
}
int count = 1000000000;
for (int trial = 0; trial < powers.length; trial++) {
long total = 0;
for (int i = 0; i < count; i++) { // warm up
final int x = bases[i % randCount];
final int y = exponents[i % randCount];
total += powers[trial].power(x, y);
}
long start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
final int x = bases[i % randCount];
final int y = exponents[i % randCount];
total += powers[trial].power(x, y);
}
long end = System.currentTimeMillis();
System.out.printf("%25s: %d ms%n", powers[trial].toString(), (end - start));
System.out.println(total);
}
产生输出：
EasyPower: 7908 ms
-407261252961037760
NaivePower: 1993 ms
-407261252961037760
FastPower: 2394 ms
-407261252961037760
使用随机数和试验的参数确实会改变输出特性，但测试之间的比率始终与所示的相同。
