Programming Praxis

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