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

### 7 Responses to “Two Random Exercises”

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

```import Control.Applicative
import Data.List
import System.Random

rand3, rand5 :: IO Int
rand3 = randomRIO (1,3)
rand5 = randomRIO (1,5)

dist :: (Eq a, Ord a) => [a] -> [(a, Int)]
dist = map (\x -> (head x, length x)) . group . sort

rand9 :: (Applicative f, Num a, Enum a) => f a -> f a
rand9 src = (+) . (*3) . pred <\$> src <*> src

rand7 :: (Applicative m, Monad m, Integral a) => m a -> m a
rand7 src = (+) . (*5) . pred <\$> src <*> src >>= \n ->
if n > 21 then rand7 src else return (mod n 7 + 1)

rand7approx :: (Functor f, Monad f, Integral a) => f a -> f a
rand7approx src = succ . (`mod` 7) . sum <\$> replicateM 7 src

main :: IO ()
main = do print \$ dist (rand9 [1..3]) == zip [1..9] [1,1..]
print . dist =<< replicateM 100000 (rand9 rand3)
print . dist =<< replicateM 100000 (rand7 rand5)
print \$ dist (rand7approx [1..5])
print . dist =<< replicateM 100000 (rand7approx rand5)
```
3. […] Pages: 1 2 […]

4. Jan Van lent said

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.

```
import random
import itertools

def rand3():
return random.randint(1, 3)

def rand5():
return random.randint(1, 5)

def rand9():
return (rand3()-1)*3+rand3()

# idea:
# use rand5 to generate a base 5 number with 7 digits
# convert this to a 5 digit base 7 number
# all of the information in the rand5 numbers is used
def rand7_5digits():
a = sum((rand5()-1)*5**i for i in range(7))
for i in range(5):
d = a % 7
yield d
a = a // 7

def rand7gen():
while 1:
for d in rand7_5digits():
yield d+1

rand7 = rand7gen().next

def hist(g):
return sorted([ (k, len(list(v)))
for (k, v) in itertools.groupby(sorted(g)) ])

def test_rand(r, n):
return hist([ r() for i in range(n) ])

n = 9*5*7*100
print test_rand(rand3, n)
print test_rand(rand5, n)
print test_rand(rand9, n)
print test_rand(rand7, n)
```
5. […] Another exercise from Programming Praxis. […]

6. JP said

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.

7. […] in order to make all letters equally likely to be chosen, which is similar to the calculation of a previous exercise. Given those two things, it is easy to generate random letters and build a pad of any desired […]