Answer to Question #93054 in C++ for siddharrth

Question

How many multiplication operations will be enough for calculating 3^8 ?

Answer 1

Answer is 3

We can use a method of binary exponentiation.

That is, we can decrease even power number of exponent dividing by 2, and replacing that operation with simple squaring.

In the task case we can see that

3^8 = 3^4 * 3^4 = (3^4)^2.

Continuing analogously, we get:

3^8 = (3^4)^2 = ((3^2)^2)^2

So 3 operations of squaring and then 3 multiplications. If we follow the process from bottom up,

3*3 = 9

9*9=81

81*81=6561