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.

About these ads

Pages: 1 2

6 Responses to “Two Random Exercises”

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

  2. 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)
    
  3. 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)
    
  4. [...] Another exercise from Programming Praxis. [...]

  5. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: