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:
- The range is inclusive on both ends, which is why the modulus is high - low + 1 and not high - low.
- The mapping has a slight bias when the modulus does not divide 2^32, which is irrelevant for a die and matters for a lottery; a real generator rejects the values in the tail instead.
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
- Not cryptographic: the state is 32 bits and four consecutive outputs reveal it; a password or a token needs the system generator.
- Not long: the period is at most 2^32, which a simulation of a billion steps would exhaust.
- Not uniform in the low bits: the modulo trick is fine for a die and poor for a hash.
- Not the random package: that one has StdGen, randomR, split and a documented algorithm, and the install is one cabal install random on a machine with a network.
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
- Take a different seed and list the first five dice rolls.
- Map the generator into 0 to 99 and count how many values fall below 50.
- Explain why the period cannot be longer than 2^32.
- Write shuffle :: [a] -> Int -> [a] with the generator and a fixed seed.
- Compare the histogram of ten thousand rolls with the one of six thousand and say which is flatter.
- 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.
-
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.
-
What does
mod 6map 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.
-
What is the period of a generator with a 32-bit state at most?
Answer
2^32A state of 32 bits has at most 2^32 values before it repeats.
-
What does this program print? ``
module Main (main) where next :: Int -> Int next seed = (seed * 1664525 + 1013904223)mod4294967296 main :: IO () main = print (next 42)``Answer
1083814273
The first next of the seed 42 is the value the program prints.
-
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.
-
What does this program print? ``
module Main (main) where between :: Int -> Int -> Int -> Int between low high value = low + valuemod(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.
-
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.
-
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.
-
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.
-
Which module has the generator type of the
randompackage?Answer
System.Random, which is not installed hereThe 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