search
Log In
18 votes
3k views

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$
in Algorithms
edited by
3k views
0
$a^8=a*a*a*a*a*a*a*a$

First compute this pair: $\underbrace{a*a}*a*a*a*a*a*a$

Let the result be $x$.

Re-write the equation: $x*x*x*x$

Repeat what you did above. $\underbrace{x*x}*x*x$

 

Let this result be $y$

Re write: $y*y$

Multiply just this.

 

Total multiplications needed = 3.
0

Notice the way of framing similar question: https://gateoverflow.in/3450/gate2007-it-17

3 Answers

30 votes
 
Best answer
a. $\log 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
26
Using Recurrence:

$a^n = a^{\frac{n}{2}}.a^{\frac{n}{2}}$
(here n is in a power of 2, so we would never have a fraction, each time when we divide n with 2.)

Here once we solve $a^{\frac{n}{2}}$, then we need one more multiplication that is multiplying $a^{\frac{n}{2}}$ to itself.

Hence recurrence:
T(n) = T$(\frac{n}{2})$+1.
Option 1 satisfies this.
2

n is a power of 2 .

So, $a_{n}$ could be $\left (2^{x} \right )^{n}$

Now, if we think $\left (2^{x} \right )^{n}$=$2^{m}$

Now,

$T\left ( 2^{m} \right )=T\left (2 ^{\frac{m}{2}} \right )+1$

Now, applying master 2nd theorem , answer is Option (A)

1

@Sachin Mittal 1 Sir if the question had "If n is a power of 3" then will the recurrence relation be:

T(n)= T(n/3) + 2 ?

0

I think it will work.

5 votes
let n = 2^k

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

total multiplications = k-1 + 1(for a^2) = k = logn
0
Suppose a=2 k=3 ... So $2^{(2^{3})}$ = $2^{8}$ = 256

 and  $(2^{2})^{3}$ = $4^{3}$ = 64 .... is it ok according to ur a^(2^k) = (a^2)^k ??
0

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

It is wrong.

For k=3,

a^(2^k) = a^(2^3) = a^8

and

(a^2)^k = (a^2)^3 = a^6

1 vote

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.

 

 

 

0
Best and Simple Answer !
Answer:

Related questions

35 votes
4 answers
1
6.9k 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 worst case is $n-1$ $n$ $n+1$ None of the above
asked Sep 23, 2014 in Algorithms Kathleen 6.9k views
26 votes
2 answers
2
2.8k views
Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O (1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$-notation. algorithm what (n) begin if n = 1 then call A else begin what (n-1); call B(n) end end.
asked Sep 23, 2014 in Algorithms Kathleen 2.8k views
32 votes
3 answers
3
9.3k 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 order of these elements after second pass of the algorithm is: $8, \ 9, \ 15, \ 20, \ 47, \ 4, \ 12, \ 17, \ 30, \ 40$ ... $4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$
asked Sep 23, 2014 in Algorithms Kathleen 9.3k views
23 votes
3 answers
4
2.2k views
Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $3$rd smallest elements in minimum number of comparisons.
asked Sep 23, 2014 in Algorithms Kathleen 2.2k views
...