edited by
9,015 views
30 votes
30 votes

If $n$ is a power of $2$, then the minimum number of multiplications needed to compute $a^n$ is

  1. $\log_2 n$
  2. $\sqrt n$
  3. $n-1$
  4. $n$
edited by

5 Answers

Best answer
45 votes
45 votes

Correct Option: A ($\log_2 n$)

$a^n = (a^2)^{\frac{n}{2}}$.

One multiplication and recurrence on $\frac{n}{2}$. So, we get the recurrence relation for the number of multiplications as

$T(n) = T(n/2) + 1$.

This gives $T(n) = \log_2 n$

For n = 8, we can do

$b = a \times a$

$b = b\times b$

$b = b\times b$ and we get $b = a^8$

edited by
9 votes
9 votes
let n = 2^k

a^n = a^(2^k) = (a^2)^k

total multiplications = k-1 + 1(for a^2) = k = logn
7 votes
7 votes

Let's take $a^{n}$ = $2^{8}$  for simplicity.

now max. no of multiplication required is = 2X2X2X2X2X2X2X2 = 256    5 multiplications or we can say (n-1) multiplications.

min. no of multiplications required = 2X2=4

                                                               =$2^{2}$X$2^{2}$=16

                                                               =$2^{4}$X$2^{4}$=256      Log n  multiplications.


We are multiplying the result of one multiplication to itself and again doing the same, that reduces the no. of multiplications required.

 

 

 

4 votes
4 votes
imagine you need to multiply a with a n times

you are given a prize if you use minimum multiplications

what would you do?

Pairwise multiplications na?

yes

and then repeat

a tree like structure will form

 

Indirectly saying, we are asked to calculate height of such tree

 

answer is logn to the base 2

 

Thanks

Intuition and smart thinking are ways to success
Answer:

Related questions

57 votes
57 votes
6 answers
1
Kathleen asked Sep 23, 2014
19,623 views
Suppose we want to arrange the $n$ numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the w...
41 votes
41 votes
3 answers
2
48 votes
48 votes
2 answers
3
Kathleen asked Sep 23, 2014
22,541 views
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$then the o...
41 votes
41 votes
6 answers
4
Kathleen asked Sep 23, 2014
22,177 views
The number of full and half-adders required to add $16$-bit numbers is$8$ half-adders, $8$ full-adders$1$ half-adder, $15$ full-adders$16$ half-adders, $0$ full-adders$4$...