Discrete Math number of multiplications it takes to calculate $x^{15}$

Question

This is in the topic of time complexity and algorithms in my list of problems and I really wanted to figure it out how to take a grip.

Here's the problem:

Find the number of multiplications needed to calculate $x^{15}$ as:

• $((x^2)^2 \cdot x)^3$
• $((x^2)^2)^2 \cdot(x^2)^2 \cdot x^2 \cdot x$

Can I use some math magic to solve even first problem and then get going for any one like that? Or do I have to simplify them?

Answer 1

You don’t want to simplify them: you want to count the multiplications required in order to calculate $x^{15}$ in each of those two ways. Assuming that you store intermediate results, so that you don’t have to recalculate them, the second approach takes $6$ multiplications:

• one to get $x\cdot x=x^2$;
• one to get $x^2\cdot x^2=(x^2)^2$;
• one to get $(x^2)^2\cdot(x^2)^2=\big((x^2)^2\big)^2$
• one to get $\big((x^2)^2\big)^2\cdot(x^2)^2$;
• one to multiply that by $x^2$; and
• one to multiply that by $x$.

Now can you count the multiplications required if you organize the calculation as $\big((x^2)^2\cdot x\big)^3$?