1

I am trying to come up with a recurrence relation for the number of multiplications needed for this algorithm:

EXP(x,e):
if e = 0, return 1  
else  
  r = EXP(x, floor(e/2))  
  if e is even  
    return r*r  
  else  
    return r*r*x

I have calculated the number of multiplications needed for some values of e:

e = 0, 0 multiplications
e = 1, 2 multiplications
e = 2, 5 multiplications
e = 3, 6 multiplications
e = 4, 7 multiplications
e = 5, 12 multiplications
e = 6, 13 multiplications
e = 7, 14 multiplications

I am unable to find a pattern for them. I was trying, for example, to find a recurrence relation starting as $T(n) = 2*T(\frac{n}{2}) + (abc)$ but am unable to find a common (abc).

One thing I have noticed, but don't think leads anywhere, is that if you look at e=2,3,4 you have T(n) = T(n-1) + 1 for those, same thing for e=5,6,7. But obviously that doesn't work for the jump between e=4 and e=5.

Could anyone provide some help/hints?

Thank you.

costrom
  • 443
user281017
  • 11
  • Your counts seem to be wrong -- the only difference between $e=4$ and $e=5$ is a single multiplication by $x$, so the difference between those two counts should be $1$. – joriki Oct 16 '15 at 20:13

1 Answers1

0

A problem of size $e$ can have the subproblem size $e'$ either as $e/2$ or $(e-1)/2$, depending upon the parity of $e$. Also, at the problem level itself, there can be either 1 or 2 multiplications, again depending upon the parity of $e$. I think finding the multiplication count via recurrence-relations may not be simple. But we can try counting them in another way as below.

Consider the binary representation of $e$; say it has $m$ bits. Then, the subproblem size $e'$ is actually the bits of $e$ right-shifted by 1 place (for both even and odd $e$). So, $e'$ must have $m-1$ bits. At the problem level itself, number of multiplications is 1 if the least-significant-bit (LSB) of current $e$ is 0 (even $e$), else it is 2.

In this new perspective of the algorithm, we can count the multiplications as follows. Total subproblem instances are $m$. Each subproblem does 1 or 2 multiplications based on the bit (LSB). So, if initial $e$ has $p$ 1 bits, and $(m-p)$ 0 bits, total multiplications are:

$2 \cdot p + 1 \cdot (m-p) = p + m$

Nitin Verma
  • 204