Integer Logarithms
May 7, 2010
The integer logarithm of a number n to a base b is the number of times b can be multiplied by itself without exceeding n.
The implementation of the ilog function in the Standard Prelude recently changed. The old version looked like this:
(define (ilog b n)
(if (zero? n) -1
(+ (ilog b (quotient n b)) 1)))
That takes time O(n) as it repeatedly divides by b. A better version takes time O(log n) as it brackets the logarithm between two possible values then uses bisection to calculate the solution.
Your task is to write a program that calculates the integer logarithm of a number to a given base in time O(log n). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
