Skiena’s TADM Problem 7-19

From Skiena’s Algorithm Design Manual
Problem 7-19

Use a random number generator (rng04) that generates numbers from {0, 1, 2, 3, 4} with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability. What are expected number of calls to rng04 per call of rng07?

Solution
(no guarantee that the solution is good or even correct)

The basic idea is to represent the numbers 0..7 with three bits, where each bit is set randomly. To this end the rng04() is wrapped into a method rng03(), which trims its output to 0..3. Then, rng07() uses this output to set each of the three bits and return the random number in 0..7.

The code uses rng03() from the AlgoWiki.

Here is a Python 3 solution. Please leave comments if you find a mistake or an improvement.

#!/usr/bin/env python

import sys, random

# used for counting method calls. taken from
# http://stackoverflow.com/questions/1301735/counting-python-method-calls-within-another-method
def counted(fn):
    def wrapper(*args, **kwargs):
        wrapper.called+= 1
        return fn(*args, **kwargs)
    wrapper.called= 0
    wrapper.__name__= fn.__name__
    return wrapper

# RNG 0..4 (given)
@counted
def rng04():
    return random.randint(0,4)

# filtered call to rng04
# return 0..3
@counted
def rng03():
    while True:
        i = rng04()
        if i < 4:
            return i

# generate uniform numbers in 0..7
# use rng03 to generate representations of the 3 bits for
# numbers in the range 0..7
def rng07():
    b3 = rng03() % 2
    b2 = rng03() % 2
    b1 = rng03() % 2
    n = b3*4 + b2*2 + b1
    return n

if __name__ == "__main__":
    rands = []
    n = 100000
    for i in range(n):
        rands.append(rng07())
    for i in range(8):
        print (str(i) + "'s: " + str(rands.count(i)))

    print ("Called rng04() " + str(rng04.called) + " times")
    print ("rng04()/rng03() call ratio: " + str(rng04.called/rng03.called))
    print ("rng04()/rng07() call ratio: " + str(rng04.called/n))

    sys.exit()

Each call to rng07() calls rng03() to set each of the three bits, which in turn calls rng04() 5/4 times to obtain a number in 0..3. Hence, rng04() is called 5/4*3 = 3.75 times in average on each call to rng07(). The solution on the AlgoWiki requires about one call less, the solution on panictank requires more.

Leave a Reply