Random numbers without the random package

Why the random package is not here

A random number is not a pure function of its arguments: the same call gives a different answer every time, so it needs an effect or an explicit seed. The random package solves that with a generator type and a state thread, and it is not installed in this container, so this lesson writes the generator instead. That is not a loss for teaching: a linear congruential generator is four lines and shows where the state goes.

next seed = (seed * 1664525 + 1013904223) `mod` 4294967296

The constants are the ones of Numerical Recipes, and the modulus is 2^32. A pure function takes a seed and returns the next number, so a sequence is an iterate and the caller decides how many numbers it wants. No global state, no IO, and the same seed always gives the same sequence, which is exactly what a test needs.

A linear congruential generator

module Main (main) where next :: Int -> Int next seed = (seed * 1664525 + 1013904223) `mod` 4294967296 between :: Int -> Int -> Int -> Int between low high value = low + value `mod` (high - low + 1) roll :: Int -> Int roll = between 1 6 main :: IO () main = do print (take 3 (iterate next 42)) print (take 5 (map roll (iterate next 42))) print (take 5 (map roll (iterate next 7))) print (between 10 20 12345)

ghc -Wall -O1 -o lcg lcg.hs
./lcg

[42,1083814273,378494188]
[1,2,5,6,1]
[2,1,4,5,2]
13

The first line is the raw sequence starting with the seed 42 itself; the next two are the same sequence mapped into 1 to 6, and the last line maps 12345 into 10 to 20. The seed is part of the input, so a test that needs a repeatable shuffle passes a fixed one, and a program that wants a different sequence each run takes the seed from the clock or from getStdRandom in the real package.

A number in a range

mod maps a number into 0 .. n-1, and adding the low bound shifts the range. Two properties matter:

A generator with a 32-bit state repeats after at most 2^32 values, and the low bits of an LCG are worse than the high ones: the lowest bit alternates. That is why the program takes mod 6 of a large number and why nobody should use this generator for anything that has to be unpredictable.

Dice and a histogram

Six thousand rolls and a map of counts is the shape of every simulation:

module Main (main) where import qualified Data.Map.Strict as Map next :: Int -> Int next seed = (seed * 1664525 + 1013904223) `mod` 4294967296 roll :: Int -> Int roll value = value `mod` 6 + 1 tally :: [Int] -> Map.Map Int Int tally values = Map.fromListWith (+) [(value, 1) | value <- values] main :: IO () main = do let seeds = take 6000 (iterate next 2026) faces = map roll seeds print (Map.toList (tally faces)) print (Map.size (tally faces))

ghc -Wall -O1 -o rolls rolls.hs
./rolls

[(1,1022),(2,966),(3,998),(4,984),(5,980),(6,1050)]
6

Six thousand rolls give about a thousand of each face, and the spread of about a hundred is what a fair die does with that sample. The exact counts are the same on every run, because the seed is fixed: a simulation with a fixed seed is reproducible, and that is the property to keep when a bug is reported. A real test would compare this histogram with the expected one and allow a tolerance, which is the property-based idea of the testing section of the course.

What this generator is not

For a lesson and a deterministic test, the four lines above are enough and show the idea. For a program that ships, use the package: the interface is randomR (low, high) gen and the state is the generator value, so the shape of the pure code is the same as here. The next lesson formats the numbers such a program prints.

Exercises

  1. Take a different seed and list the first five dice rolls.
  2. Map the generator into 0 to 99 and count how many values fall below 50.
  3. Explain why the period cannot be longer than 2^32.
  4. Write shuffle :: [a] -> Int -> [a] with the generator and a fixed seed.
  5. Compare the histogram of ten thousand rolls with the one of six thousand and say which is flatter.
  6. Explain what a test would need to check that the die is fair.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why must a random number generator carry a seed?

    Answer

    The next value is a function of the current state

    A generator is a pure function from a state to the next value, so the state has to be passed explicitly.

  2. What does mod 6 map a number into?

    Answer

    0 to 5

    The remainder of a division by 6 is 0 to 5; adding 1 gives the faces of a die.

  3. What is the period of a generator with a 32-bit state at most?

    Answer

    2^32

    A state of 32 bits has at most 2^32 values before it repeats.

  4. What does this program print? ``module Main (main) where next :: Int -> Int next seed = (seed * 1664525 + 1013904223) mod 4294967296 main :: IO () main = print (next 42)``

    Answer

    1083814273

    The first next of the seed 42 is the value the program prints.

  5. Why is the low bit of an LCG a poor random bit?

    Answer

    It alternates in a short cycle, so the low bits are less random than the high ones

    The low bits of a linear congruential generator have short periods, which is why the modulo trick uses a large value.

  6. What does this program print? ``module Main (main) where between :: Int -> Int -> Int -> Int between low high value = low + value mod (high - low + 1) main :: IO () main = print (between 1 6 13)``

    Answer

    2

    13 mod 6 is 1, and adding the low bound 1 gives 2.

  7. Why is a fixed seed useful in a test?

    Answer

    The sequence is the same on every run, so a failure can be reproduced

    Reproducibility is what a test needs, and a seed gives it.

  8. What does Map.fromListWith (+) build in the dice program?

    Answer

    A histogram from each face to the number of rolls

    The pairs are (face, 1) and the duplicate faces are added, which counts them.

  9. Is this generator suitable for a password reset token?

    Answer

    No, it is predictable from a few outputs and has a short state

    Cryptographic use needs an unpredictable generator with a much larger state.

  10. Which module has the generator type of the random package?

    Answer

    System.Random, which is not installed here

    The package is random and its main module is System.Random; this container has neither.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev