Pow函数从递归到迭代

Question

我的任务是做一个复杂度为O(logn(的递归pow函数，然后以迭代的方式做同样的算法。第一个我认为我有它，但是，我在以迭代的方式做同样的事情时遇到了麻烦。我有一个是O(logn(，但它不是同一个。

public static BigInteger powV2(int x, int y) {
if (y == 0) {
return BigInteger.ONE;
}
BigInteger powerOfHalfX = powV2(x, y / 2);
if (y % 2 == 0) {
return powerOfHalfX.multiply(powerOfHalfX);
} else {
return BigInteger.valueOf(x).multiply(powerOfHalfX).multiply(powerOfHalfX);
//x * powerOfHalfX * powerOfHalfX;
}
}

这是迭代的：

public static BigInteger iterativePowV2(int x, int y) {
BigInteger result = BigInteger.ONE;
while (y > 0) {
if (y % 2 == 1) {
result = result.multiply(BigInteger.valueOf(x));
}
y = y >> 1; //y = y/2
x = x * x; //
}
return result;
}

Answer 1

你非常接近。在我看来，这两段代码中都有正确的方法，但在迭代版本的循环体中略有失误：

x = x * x;

应该是：

result = result.multiply(result)

因为你想要的是你的运行总量的平方，而不是输入变量。在一些小的输入上测试一下，看看它是否正常工作！

编辑：仍然没有工作，在这里找到了一个解决方案：迭代对数求幂