Programming Praxis – Two Random Exercises

In today’s Programming Praxis exercise, our goal is to use convert two random number generators to a different range. Specifically, we have to convert an rng that produces numbers in the closed interval [1,3] to one that has the interval [1,9] and one with interval [1,5] to [1,7]. In both cases the resulting rngs must maintain an equal distribution across the interval. Let’s get started, shall we?

Some imports:

import Control.Applicative
import Control.Monad
import Data.List
import System.Random

These are the two functions we can use as imports.

rand3, rand5 :: IO Int
rand3 = randomRIO (1,3)
rand5 = randomRIO (1,5)

To test, we use a distribution function to see how many of each element occur in a sequence.

dist :: (Eq a, Ord a) => [a] -> [(a, Int)]
dist = map (\x -> (head x, length x)) . group . sort

Let’s start with the easiest one. Since 9 = 3 * 3, all we need to do scale up one input by a factor of 3 and “interpolate” using a second one. The reason for taking a source parameter is to facilitate testing: you can either feed it an IO Int for a random result, or you can give it a [Int] to see all possible results. We’ll get to why the testing is important in a bit.

rand9 :: (Applicative f, Num a, Enum a) => f a -> f a
rand9 src = (+) . (*3) . pred <$> src <*> src

The second one is more complicated, since 5*5 is not a multiple of 7. The correct solution is to do the same thing as above using a subrange that is a multiple of 7, i.e. 21 of the 25 numbers and rerolling when one of the four values outside the accepted range is chosen. The problem with this approach is that it isn’t guaranteed to terminate, since there is nothing preventing a true random number generator from generating the number 23 a few trillion times in a row. Granted, we’re only using pseudo-random number generators, so it probably will never come up. Here’s the implementation:

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)

Since I didn’t like the chance of a non-terminating algorithm I came up with the following algorithm: sum seven random numbers in the range 1 to 5, and give the result modulo 7. Or in code:

rand7approx :: (Functor f, Monad f, Integral a) => f a -> f a
rand7approx src = succ . (`mod` 7) . sum <$> replicateM 7 src

Printing the distribution looked perfectly fine, with all of them getting a little over 14%. But something felt off to me. The code was shorter than the version with rerolling and didn’t suffer the inifinite loop problem, so there had to be reason it wasn’t the provided solution. I changed all the functions to take a source argument rather than calling rand3 and rand5 directly and printed the theoretical distributions as well (except for rand7, since the distribution for that one is non-terminating). This revealed that there is a 0.3% difference between the most and least common values. In retrospect, this should’ve been obvious, as 5^7 mod 7 isn’t equal to 0, which means it’s impossible for all 7 values to get the same distribution. Some more reading up revealed that there is indeed no solution that both provides an equal distribution and is guaranteed to terminate, since 7 is an infinitely repeating fraction in base 5.

Here are the tests I used:

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)
About these ads

Tags: , , , , , , , , , , , , ,

One Response to “Programming Praxis – Two Random Exercises”

  1. programmingpraxis Says:

    Nicely done. Good explanation of the rand7 situation.

Leave a Reply

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

WordPress.com Logo

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


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: