August 26, 2014
(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))
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)
(let ((leftmost-pair (leftmost-digit (* base base) n)))
(if (< leftmost-pair base)
(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