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

Question

In the book Algorithms for interviewers, there is such a question:

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

Can anyone tell me what this question means?

What means "evaluate X to the power 30"?

There are two possible meanings, i guess:

1. we have a X, then this question asks me "how many multiplications do I need to calculate X^30?".
2. We have a X, then it asks me "What y is so that y^30 = X, and how many multiplications do you need to calculate y?"

I don't know which of what I guess is correct, or it has a 3rd meaning?

Thanks

Answer 1

The question supposes that there is a way to write a function:

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

using only multiplications.

In fact one way would be the following:

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

This uses 30 multiplications.

However consider this:

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

This uses 16 multiplications.

So the question is asking what is the minimum number of multiplications possible?

Here is 6 multiplications, and likely the interviewers ideal solution:

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
}

This is more a brainteaser than a programming problem. A real power function does not use multiplication (or at least not in the way implied by the question)