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

Posted by programmingpraxis
Filed in Exercises
7 Comments »

7 Responses to “Two Random Exercises”

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

  2. 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)
  4. 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)
  5. Two Random Exercises | jverkamp.com said
    August 22, 2012 at 1:24 PM

    […] Another exercise from Programming Praxis. […]

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

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

Leave a comment