## Two Random Exercises

### August 17, 2012

These exercises are trickier than they look.

There are at least two obvious solutions to the first exercise that turn out to be wrong. The product rand3 * rand3 doesn’t work because the numbers 5, 7 and 8 cannot be produced and the numbers 2, 3 and 6 are produced twice. The sum rand3 + rand3 + rand3 also doesn’t work because there is no way to produce the numbers 1 and 2. The solution is the formula 3 * (rand3 – 1) + rand3; the first rand3 produces either 1, 2 or 3, subtracting 1 produces 0, 1 or 2, multiplying by 3 produces 0, 3 or 6, and adding rand3 produces one instance each of all the numbers 1 through 9:

`(define (rand3) (randint 1 4))`

`(define (rand9)`

(+ (* (- (rand3) 1) 3) (rand3)))

The second exercise builds from the first. Since 5 and 7 are coprime, there is no way to produce a number of values that is an exact multiply of 7, so the solution builds 25 possibilities, using a formula similar to rand9 above, discards the top four, and takes the remainder modulo 7:

`(define (rand5) (randint 1 6))`

`(define (rand7)`

(let ((x (+ (* (- (rand5) 1) 5) (rand5) -1)))

(if (< x 21) (+ (modulo x 7) 1) (rand7))))

Here, *x* is bound to a random number in the range 0 to 24, a new random number is generated if the random number is greater than 20, otherwise modulo and add 1 translates the random number in the range 0 to 24 to a random number in the range 1 to 7.

We demonstrate that both functions generate random numbers with equal frequency by building a histogram of the generated numbers:

`(define (histogram n f)`

(map cdr (uniq-c = (sort < (list-of (f) (x range n))))))

The result shows that both random number generators are fair; both produce remarkably even distributions:

`> (histogram 100000 rand9)`

(11163 11009 11011 11096 11114 11041 11146 11200 11220)

> (histogram 100000 rand7)

(14255 14305 14195 14175 14416 14237 14417)

We used `randint`

, `uniq-c`

and list comprehensions from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/Fu7Ps7LN.

Pages: 1 2

[…] today’s Programming Praxis exercise, our goal is to use convert two random number generators to a different […]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/08/17/programming-praxis-two-random-exercises/ for a version with comments):

[…] Pages: 1 2 […]

Below a solution for rand7 that does not discard any random numbers (implemented in Python using a generator).

The number of calls to rand5 per bit of randomness is optimal.

[…] Another exercise from Programming Praxis. […]

Here are my solutions in Scheme. I have to say if there’s anything worth doing, it’s worth over doing. It’s not the most efficient way of doing the problem, but it did amuse me to write.