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