## 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

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

```import Control.Applicative
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. [...] Pages: 1 2 [...]

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

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