The Gateway to Computer Science Excellence
+16 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$
in Algorithms by Veteran (52.2k points)
edited by | 2k views

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.

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$
by Veteran (431k points)
edited by
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.

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


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

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


@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 ?


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
by (437 points)
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 ??

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

It is wrong.

For k=3,

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


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

0 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^{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.




by Active (4.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,386 users