Question

Given a real number x and a positive integer k, determine the number of multiplications used to find x2k starting with x 24 2k and successively squaring (to find x , x , and so on). Is this a more efficient way to find x than by multiplying x by itself the appropriate number of times

Answer 1

Answer:

In 1st case the multiplication is to be done for the k times, in the second case the number of multiplication is given as $2^k-1$ times.

As the value of k will always be less than that of  $2^k-1$, thus the case 1 is an efficient way of finding the values.

Step-by-step explanation:

Case No 1 is given as:

In this case  the value of ${x^2}^k$ is found by subsequent squaring such that

${{x^2}^k}=x(x^2.x^4.x^8......{x^2}^k)\\{{x^2}^k}=x({x^2}^1.{x^2}^2.{x^2}^3......{x^2}^k)$

So in this case the multiplication is to be done for the k times.

Case No 2 is given as

${x^2}^k=x(x.x.x.x.x...x) 2^k-1 times$

So in this case the number of multiplication is given as $2^k-1$ times.

As the value of k will always be less than that of  $2^k-1$, thus the case 1 is an efficient way of finding the values.