Integer Logarithm

August 26, 2014

The integer logarithm function in the Standard Prelude looks like this:

(define (ilog b n)
  (let loop1 ((lo 0) (b^lo 1) (hi 1) (b^hi b))
    (if (< b^hi n) (loop1 hi b^hi (* hi 2) (* b^hi b^hi))
      (let loop2 ((lo lo) (b^lo b^lo) (hi hi) (b^hi b^hi))
        (if (<= (- hi lo) 1) (if (= b^hi n) hi lo)
          (let* ((mid (quotient (+ lo hi) 2))
                 (b^mid (* b^lo (expt b (- mid lo)))))
            (cond ((< n b^mid) (loop2 lo b^lo mid b^mid))
                  ((< b^mid n) (loop2 mid b^mid hi b^hi))
                  (else mid))))))))

It performs binary search in loop1 until n is bracketed between b^lo and b^hi, doubling at each step, then refines the binayr search in loop2, halving the bracket at each step.

Inspired by that function, Joe Marshall posed this puzzle at his Abstract Heresies web site:

You can get the most significant digit (the leftmost) of a number pretty quickly this way:

(define (leftmost-digit base n)
  (if (< n base)
      n
      (let ((leftmost-pair (leftmost-digit (* base base) n)))
        (if (< leftmost-pair base)
            leftmost-pair
            (quotient leftmost-pair base)))))

The puzzle is to adapt this code to return the position of the leftmost digit.

Your task is to write Joe’s puzzle function; you might also click through to his website to spike his stats. 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

One Response to “Integer Logarithm”

  1. Mike said
    def leftmost(n, base=10, count=1):
        if n < base:
            return n, 1
    
        else:
            leftmost_pair, digits = leftmost(n, base*base, 2*count)
            
            if leftmost_pair < base:
                return leftmost_pair, digits
    
            else:
                return leftmost_pair // base, count + digits
    
    def leftmost_digit(n, base=10):
    	return leftmost(n, base)[0]
    
    def number_of_digits(n, base=10):
    	return leftmost(n, base)[1]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: