# [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