[racket] a small programming exercise

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?

(define (first-digit-string n)
  (- (char->integer (string-ref (number->string n) 0))
     (char->integer #\0)))

(define (first-digit-fast n)
  (if (> 10 n)
      n
      (let loop ([i 10]
                 [next 100])
        (if (> next n)
            (first-digit-fast (floor (/ n i)))
            (loop next (* i i))))))

(define *the-list* (filter positive? (build-list 10000000 (lambda (i)
(random (+ i 1))))))

> (time (for-each first-digit-string *the-list*))
cpu time: 3969 real time: 4016 gc time: 718
> (time (for-each first-digit-fast *the-list*))
cpu time: 11875 real time: 11907 gc time: 391

Justin