Two Random Exercises

August 17, 2012

We have two exercises related to random numbers today. I’m not sure of the source, but they look to me like homework exercises.

First, given a function rand3 that returns a number from 1 to 3 inclusive chosen at random, write a function that returns a number from 1 to 9, inclusive.

Second, given a function rand5 that returns a number from 1 to 5 inclusive chosen at random, write a function that returns a number from 1 to 7, inclusive.

In both cases all possible output numbers should be generated with equal frequency. You should demonstrate that your functions behave properly.

Your task is to write the rand9 and rand7 functions and demonstrate that they work properly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 […]

  2. My Haskell solution (see 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.

  6. […] 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 […]

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 708 other followers

%d bloggers like this: