Integer Logarithm
August 26, 2014
Joe first explains the leftmost-digit function:
The idea is this: if we have a one digit number, we just return it, otherwise we recursively call leftmost-digit with the square of the base. Squaring the base will mean gobbling up pairs of digits in the recursive call, so we’ll get back either a one or two digit answer from the recursion. If it is one digit, we return it, otherwise it’s two digits and we divide by the base to get the left one.
For example, if our number is 12345678 and the base is 10, we’ll make a recursive call with base 100. The recursive call will deal with number as if it were written 12 34 56 78 in base 100 and return the answer 12. Then we’ll divide that by 10 to get the 1.
Since we’re squaring the base, we’re doubling the number of digits we’re dealing with on each recursive call. This leads to the solution in O(log log n) time.
Joe then gives an example of finding the leftmost digit of a 63-digit base-10 number. There are five recursive calls to leftmost-digit; the first recursive call divides by 10 × 10 = 100, the second recursive call divides by 100 × 100 = 10000 = 104, the third recursive call divides by 104 × 104 = 108, the fourth recursive call divides by 108 × 108 = 1016, and the fifth recursive call divides by 1016 × 1016 = 1032.
Thus, Joe solves his puzzle with the following code that adds a counter to the original function:
(define (leftmost-digit+ base n)
(if (< n base)
(values n 0)
(call-with-values (lambda () (leftmost-digit+ (* base base) n))
(lambda (leftmost-pair count)
(if (< leftmost-pair base)
(values leftmost-pair (* count 2))
(values (quotient leftmost-pair base) (+ (* count 2) 1)))))))
The function returns two values, the leftmost digit and the number of digits that are discarded. For instance:
> (leftmost-digit 10 816305093398751331727331379663195459013258742431006753294691576)
8
> (leftmost-digit+ 10 46729885)
4
7
The number of discarded digits is, of course, the integer logarithm. You can run the program at http://programmingpraxis.codepad.org/sAbq3Qw0. The new code will be added to the Standard Prelude the next time the Standard Prelude is revised. And please click through to Joe’s puzzle and solution.
Programming Praxis 
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]