how can i prove the following algorithm?

Question

Exp(n)
  If n = 0
    Return 1
  End If
  
  If n%2==0
    temp = Exp(n/2)
    Return temp × temp
  Else //n is odd
    temp = Exp((n−1)/2)
    Return temp × temp × 2
  End if

how can i prove by strong induction in n that for all n ≥ 1, the number of multiplications made by Exp (n) is ≤ 2 log2 n.

ps: Exp(n) = 2^n

I would have taken this question on [cs.stackexchange.com](https://cs.stackexchange.com/). — Giorgi Tsiklauri, Sep 23 '20 at 13:43

score 0 · Answer 1 · answered Sep 23 '20 at 13:44

A simple way is to use strong induction.

First, prove that Exp(0) terminates and returns 2^0.
Let N be some arbitrary even nonnegative number.
Assume the function Exp correctly calculates and returns 2^n for every n in [0, N].
Under this assumption, prove that Exp(N+1) and Exp(N+2) both terminate and correctly return 2^(N+1) and 2^(N+2).

You're done! By induction it follows that for any nonnegative N, Exp(N) correctly returns 2^N.

PS: Note that in this post, 2^N means "two to the power of N" and not "bitwise xor of the binary representations of 2 and N".

score 0 · Answer 2 · answered Sep 23 '20 at 13:45

The program exactly applies the following recurrence:

P[0] = 1
n even -> P[n] -> P[n/2]²
n odd  -> P[n] -> P[(n-1)/2]².2

the program always terminates, because for n>0, n/2 and (n-1)/2 < n and the argument of the recursive calls always decreases.

P[n] = 2^n is the solution of the recurrence. Indeed,

n = 0 -> 2^0 = 1
n = 2m -> 2^n = (2^m)²
n = 2m+1 -> 2^n = 2.(2^n)²

and this covers all cases.

As every call decreases the number of significant bits of n by one and performs one or two multiplications, the total number does not exceed two times the number of significant bits.

how can i prove the following algorithm?

2 Answers2