2.16.6 Recommended usage patterns

Unless the functionality defined in this SRFI is sufficient, an application has to implement more procedures to construct other random deviates. This section contains some recommendation on how to do this technically by presenting examples of increasing difficulty with respect to the interface. Note that the code below is not part of the specification, it is merely meant to illustrate the spirit

Generating Random Permutations

The following code defines procedures to generate random permutations of the set {0, ..., n-1}. Such a permutation is represented by a vector of length n for the images of the points.

Observe that the implementation first defines the procedure random-source-make-permutations to turn a random source s into a procedure to generate permutations of given degree n. In a second step, this is applied to the default source to define a ready–to–use procedure for permutations: (random-permutation n) constructs a random permutation of degree n.

(define (random-source-make-permutations s)
  (let ([rand (random-source-make-integers s)])
    (lambda (n)
      (let ([x (make-vector n 0)])
        (do ([i 0 (+ i 1)])
            ([= i n])
          (vector-set! x i i))
        (do ([k n (- k 1)])
            ([= k 1] x)
          (let* ([i (- k 1)]
                 [j (rand k)]
                 [xi (vector-ref x i)]
                 [xj (vector-ref x j)])
            (vector-set! x i xj)
            (vector-set! x j xi)))))))

(define random-permutation
  (random-source-make-permutations default-random-source))

For the algorithm refer to Knuth’s “The Art of Computer Programming”, Vol. II, 2nd ed., Algorithm P of Section 3.4.2.

Generating Exponentially-Distributed Random Numbers

The following code defines procedures to generate exponentially Exp(mu)–distributed random numbers. The technical difficulty of the interface addressed here is how to pass optional arguments to random-source-make-reals.

(define (random-source-make-exponentials s . unit)
  (let ((rand (apply random-source-make-reals s unit)))
    (lambda (mu)
      (- (* mu (log (rand)))))))

(define random-exponential
  (random-source-make-exponentials default-random-source))

The algorithm is folklore. Refer to Knuth’s “The Art of Computer Programming”, Vol. II, 2nd ed., Section 3.4.1.D.

Generating Normally-Distributed Random Numbers

The following code defines procedures to generate normal N(mu, sigma)–distributed real numbers using the polar method.

The technical difficulty of the interface addressed here is that the polar method generates two results per computation. We return one of the result and store the second one to be returned by the next call to the procedure. Note that this implies that random-source-state-set! (and the other procedures modifying the state) does not necessarily affect the output of random-normal immediately!

(define (random-source-make-normals s . unit)
  (let ([rand (apply random-source-make-reals s unit)]
        [next #f])
    (lambda (mu sigma)
      (if next
          (let ([result next])
            (set! next #f)
            (+ mu (* sigma result)))
        (let loop ()
          (let* ([v1 (- (* 2 (rand)) 1)]
                 [v2 (- (* 2 (rand)) 1)]
                 [s (+ (* v1 v1) (* v2 v2))])
            (if (>= s 1)
                (loop)
              (let ([scale (sqrt (/ (* -2 (log s)) s))])
                (set! next (* scale v2))
                (+ mu (* sigma scale v1))))))))))

(define random-normal
  (random-source-make-normals default-random-source))

For the algorithm refer to Knuth’s “The Art of Computer Programming”, Vol. II, 2nd ed., Algorithm P of Section 3.4.1.C.