迭代对数幂 [英] Iterative logarithmic exponentiation

问题描述

我最近轰炸了一次采访(带有collabedit的电话屏幕). 这是问题: 编写一个交互式O(lg n)算法以求x ^ y的幂(x是双精度，y> 0是整数).

I bombed an interview (phone screen with collabedit) recently. Here is the question: Write an interative O(lg n) algorithm for finding the power of x^y (x is a double, y>0 is an int).

我首先进行递归除法并征服一个，然后尝试将其转换为迭代式……但我无法:S 是否有一种将递归转换为迭代的方法(尾递归很容易，但是具有两个可能的递归调用的递归函数又取决于条件来决定将调用哪个调用)?

I first did the recursive divide and conquer one and tried to convert it to iterative... and I couldn't :S Is there a method to convert recursion to iterative (it is easy for tail recursion, but how about recursive functions with two possible recursive calls which depend on conditions to decide which call will be invoked) ?

推荐答案

展开此操作的典型方法是使用b的按位表示.计算a ¹ ，a ² ，a ⁴ ，a ⁸ 等，并在每个步骤中确定是否为不要将其乘以总数.显示在这里:

The typical way to unroll this uses the bitwise representation of b. Compute a¹, a², a⁴, a⁸, etc. and at each step determine whether or not to multiply it into the total. This is shown here:

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 ^4相乘.

For example, to compute 3⁵, we'd notice that 5 has binary representation 101, so we'd multiply in 3¹ and 3⁴.

希望这会有所帮助！

这篇关于迭代对数幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！