Friday, October 24, 2008

pow(n, m) would never terminate for m > 0

The following code was shown in today's lecture as one of the alternatives to single-call recursion on pow(n, m):

0. def pow(n, m)
1. if m == 0: return 1
2. else: return pow(n, Floor(m / 2)) * pow(n, Ceiling(m / 2))


Since we used floors and ceilings, I take it that m is an integer. Then for an m > 0, a call to pow(n, m) would execute line 2. But Ceiling(m / 2) will never be 0 for an integer m > 0, so line 2 would get executed indefinitely on pow(n, Ceiling(m / 2)'s recursive call, causing the program to never terminate.

I think that adding "else if m == 1: return n" before the last else branch would fix this problem.

PS3 - G(n) induction step

I got my third problem set back today, and I noticed that the marker made a note on my induction step. Here is the beginning of my proof by complete induction:

      Let P(n): G(n) = S(i from 0 to n) 3^i
Claim: for any natural number n, P(n)

Base case n=0: G(0) = 1 (by definition of G)
S(i from 0 to 0) 3^i = 3^0 = 1
Then P(0) holds.

Induction Step: Let n be part of N\{0} and assume P(0) /\ ... /\ P(n-1)


The marker asked why can't n=0 be in the induction step? They mentioned that I need this, but then wouldn't P(n-1) = P(-1) for n=0? The claim was only about P being true for natural numbers, so I am a little confused. Indeed I needed n=0, but I specifically handled that in the base case.