The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

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

- $\log_2 n$
- $\sqrt n$
- $n-1$
- $n$

+22 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$

$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$

$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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users