[racket] a small programming exercise

From: Joe Marshall (jmarshall at alum.mit.edu)
Date: Thu Oct 14 18:42:13 EDT 2010

On Thu, Oct 14, 2010 at 3:19 PM, Justin Zamora <justin at zamora.com> wrote:
> On Thu, Oct 14, 2010 at 2:26 PM, Joe Marshall <jmarshall at alum.mit.edu> wrote:
>> Here's a fast way to get the leftmost digit of a number:
>> ...
>> 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)))))
> I tried a comparison of your method to the string-conversion method
> and was surprised that the string-comparison version ran 3 times
> faster!  I think I implemented your method correctly (at least it
> appears to produce correct results).  Any insights?

Interesting.  Here is the thread that it appeared on first:

One person there reported:
``Joe's iterative solution was 26x faster than my string-based
version and allocates no memory.  ''

So here are some possible explanations:
  1) number->string might be written in C.
  2) generic arithmetic might be causing too much overhead
  3) Something that ought to be compiled is not being compiled.


Posted on the users mailing list.