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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: