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.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to use convert two random number generators to a different […]
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)[…] Pages: 1 2 […]
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)[…] Another exercise from Programming Praxis. […]
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.
[…] 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 […]