algorithm - 你如何确定计算 X 的 30 次方的最小乘法次数？

Question

在书中Algorithms for interviewers ，有这样一个问题:

How would you determine the minimum number of multiplications to evaluate X to the power 30?

谁能告诉我这个问题是什么意思？

“计算 X 的 30 次方”是什么意思？

我猜有两种可能的含义:

1. 我们有一个 X，然后这个问题问我“计算 X^30 需要多少次乘法？”。
2. 我们有一个 X，然后它问我“y 是多少才能使 y^30 = X，你需要乘多少次才能计算出 y？”

我不知道我猜的哪个是正确的，或者它有第三层含义？

谢谢

Answer 1

题目假设有一种方法可以写一个函数:

int f(int x) { return pow(x, 30); }

仅使用乘法。

事实上，一种方式如下:

int f(int x)
{
    int y = 1;
    for (int i = 0; i < 30; i++)
        y *= x;
    return y;
}

这使用了 30 次乘法。

但是考虑一下:

int f(int x)
{
    int z = x*x;
    int y = 1;
    for (int i = 0; i < 15; i++)
        y *= z;
    return y;
}

这使用了 16 次乘法。

所以问题是问乘法的最小次数是多少？

这里有 6 个乘法，可能是面试官理想的解决方案:

int f(int x)
{
    x_3 = x * x * x;
    x_6 = x_3 * x_3;
    x_12 = x_6 * x_6
    x_24 = x_12 * x_12
    return x_24 * x_6
}

这与其说是一个编程问题，不如说是一个脑筋急转弯。实幂函数不使用乘法(或者至少不使用问题暗示的方式)