Question 5 at UTSC and UTM

Let x,b be natural numbers such that x≥1 and b≥2.
The integer logarithm of x base b is the unique natural number n such that bn ≤ x < bn+1. Notice that this quantity is floor(logb x).

Prove that the program IntLog(x,b) below is correct with respect to the given specification.

Precondition: x,bN, x≥1, b≥2.

Postcondition: IntLog(x,b) returns the integer logarithm of x base b. 

IntLog(x,b)
i:=0
t:=1
while b*t ≤ x do
    i := i+1
    t := t*b
end while
return i

solution in postscript or PDF (don't look until you've worked on it!)

[main course page]