[racket] a small programming exercise

From: Joe Marshall (jmarshall at alum.mit.edu)
Date: Thu Oct 14 14:26:59 EDT 2010

Here's a fast way to get the leftmost digit of a number:

(defun leftmost-digit (n base)
  (do* ((i 1 next)
        (next base (* i base)))
       ((> next n) (floor n i))))

(This is in Common Lisp.  DO* is to DO as LET* is to LET.  Floor takes two
integer arguments and returns the floor of the left divided by the right.)

You'll find this much faster than using `number->string'
One reason you want to avoid strings is that the algorithm that
renders numbers to strings assumes that you are interested in *all*
the digits.  Since you only want the leftmost one, you can save a
lot of time by just not generating the others.

This version is slightly slower for small numbers, but much much better
for large ones:
(defun leftmost-digit (n base)
  (if (> base n)
      n
      (do* ((i base next)
            (next (* base base) (* i i)))
        ((> next n) (leftmost-digit (floor n i) base)))))

(Brainteaser:  What is big-O for this?)


-- 
~jrm


Posted on the users mailing list.