[racket] a small programming exercise

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:
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/ed990c2efd24373e/e6ada2b307534225?hl=en&ie=UTF-8&q=group:comp.lang.lisp+first-digit&pli=1

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.



-- 
~jrm