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.

Pages: 1 2

Follow

Get every new post delivered to your Inbox.

Join 574 other followers