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.

7 Responses to “Two Random Exercises”

Programming Praxis – Two Random Exercises « Bonsai Code said
August 17, 2012 at 11:24 AM
[…] today’s Programming Praxis exercise, our goal is to use convert two random number generators to a different […]

Remco Niemeijer said

August 17, 2012 at 11:24 AM

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

import Control.Applicative
import Control.Monad
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)

Two Random Exercises | On scalable, RPC-based network emulators said
August 17, 2012 at 10:20 PM
[…] Pages: 1 2 […]

Jan Van lent said

August 20, 2012 at 8:11 PM

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)

Two Random Exercises | jverkamp.com said
August 22, 2012 at 1:24 PM
[…] Another exercise from Programming Praxis. […]
JP said
August 23, 2012 at 2:03 PM
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.
One-Time Pad | Programming Praxis said
January 9, 2015 at 9:00 AM
[…] 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 […]

Programming Praxis