迭代对数取幂

Question

我最近轰炸了一次采访(带有collabedit的电话屏幕).这是一个问题:写一个迭代的O(lg n)算法来找到x ^ y的幂(x是一个double,y> 0是一个int).

我首先做了递归划分并征服了一个并尝试将其转换为迭代...而我不能:S是否有一种方法将递归转换为迭代(它很容易进行尾递归,但是如何使用两个递归函数可能的递归调用,取决于条件来决定调用哪个调用)？

Answer 1

展开它的典型方法是使用b的按位表示.计算¹,a ²,a ⁴,a ⁸等,并在每一步确定是否将其乘以总数.这显示在这里:

double result = 1;
double multiplier = a;
for (double multiplier = a; b != 0; multiplier *= multiplier, b /= 2) {
    if (b % 2 == 1) {
       result *= multiplier;
    }
}

例如,为了计算3 ⁵,我们注意到5具有二进制表示101,因此我们将乘以3 ¹和3 ⁴.

希望这可以帮助!