[racket] a small programming exercise

From: Jos Koot (jos.koot at telefonica.net)
Date: Fri Oct 15 04:33:21 EDT 2010

When taking a long list of pseudo random positive integers most of which are
far greater than the base, I expect about the same frequency for each first
digit from 1 to base-1. This seems to hold if the base is a power of 10, but
for other bases, e.g. base 24, I get rather unexpected results. See program
below. Someone has an idea how this can happen?

Thanks, Jos

#lang racket

(require racket/unsafe/ops racket/fixnum)

(define (first-digit n base)
  (if (unsafe-fx< n base) n
      (first-digit (unsafe-fxquotient n base) base)))

(define (first-digit-frequencies lon base)
  (let ((v (make-fxvector (unsafe-fx- base 1) 0)))
    (for ((n lon))
      (let ((d (unsafe-fx- (first-digit n base) 1)))
        (unsafe-vector-set! v d
         (unsafe-fx+ (unsafe-vector-ref v d) 1))))
    v))

(define (test vector-length number-size base)
  (random-seed 1)
  (let*
      ((lon (build-list
             vector-length
             (lambda (x) (add1 (random number-size)))))
       (v (begin
            (collect-garbage)
            (collect-garbage)
            (collect-garbage)
            (time (first-digit-frequencies lon base)))))
    (for/list ((f (in-fxvector v))) f)))

(test 1000000 1000000 10)
; cpu time: 171 real time: 171 gc time: 0
; (110963 111566 111299 111200 111218 110865 110476 111079 111334)
; all frequencies close to 1000000/9 as expected.

(test 1000000 1000000 100)
; cpu time: 124 real time: 125 gc time: 0
; list of frequencies all close to 1000000/99 as expected.

(test 1000000 1000000 24)
; cpu time: 171 real time: 172 gc time: 0
; (346114 346260 19220 remanining numbers close to 14500)
; Surprise! Expected all frequencies to be close to 1000000/23




Posted on the users mailing list.