SICP Exercise 3.6

2023-04-05

Question

It is useful to be able to reset a random-number generator to produce a sequence starting from a given value. Design a new rand procedure that is called with an argument that is either the symbol generate or the symbol reset and behaves as follows: (rand 'generate) produces a new random number; ((rand 'reset) ⟨new-value⟩) resets the internal state variable to the designated ⟨new-value⟩. Thus, by resetting the state, one can generate repeatable sequences. These are very handy to have when testing and debugging programs that use random numbers.

Answer

First, we need to define some kind of rand-update method. I will follow the suggestion from the book’s footnotes and use something of the format \(ax+b \bmod m\).

(define (rand-update x)
  (remainder (+ (* 173 x) 33) 101))

Note that this is not a good random algorithm at all. It can only generate numbers up to 101 and it probably does not have a uniform distribution. But it will do the job for testing purposes.

Next, our rand implementation. For this, we just add some conditionals to our \(\lambda\) function:

(define rand
  (let ((x 11))
    (λ (m)
      (cond ((eq? m 'generate)
             (set! x (rand-update x)) x)
            ((eq? m 'reset)
             (λ (x-new) (set! x x-new)))
            (else (error "Unknown request: RAND" m))))))

This uses 11 as random-init. We can test the algorithm by generating three numbers, resetting the initialiser to 11, and generating three more numbers. This second set of numbers should be equivalent to the first.

(rand 'generate)
(rand 'generate)
(rand 'generate)

((rand 'reset) 11)
(rand 'generate)
(rand 'generate)
(rand 'generate)

As we see, this is exactly what happens: