[racket] a small programming exercise
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