❖ Random Numbers |
How can a computer generate a random number?
Software can only produce pseudo random numbers.
❖ ... Random Numbers |
Ideally, we want a function random()
int freq[10] = {0,0,0,0,0,0,0,0,0,0}; for (i = 0; i < 100000; i++) { int n = random() % 10; freq[n]++; }
... after which each freq[i] should contain the same value (10000)
❖ Linear Conguential Generators |
The most widely-used pseudo random number technique:
LCG uses a recurrence relation:
❖ ... Linear Conguential Generators |
Typical implementation of an LCG
#define a ??? #define c ??? #define m ??? unsigned int random() { static unsigned int X; X = (a * X + c) % m; return X; }
It is possible to omit m
a
mod 232
❖ ... Linear Conguential Generators |
Clearly, we need to be careful in choice of a
c
m
Consider the case where a
m
c
X0=1
An LCG would produce the sequence:
11, 28, 29, 9, 6, 4, 13, 19, 23, 5, 24, 16, 21, 14, 30, 20, 3, 2, 22, 25, 27, 18, 12, 8, 26, 7, 15, 10, 17, 1, 11, 28, 29, 9, 6, 4, 13, 19, 23, 5, 24, 16, 21, 14, 30, 20, 3, 2, 22, 25, 27, 18, 12, 8, 26, 7, 15, 10, 17, 1, 11, 28, 29, 9, 6, 4, 13, ...
Observations:
❖ ... Linear Conguential Generators |
Now consider the case where a
m
c
X0=1
AN LCG would produce the sequence:
12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6, 12, 24, 18, 6, ...
Does not produce all values in the range 1..30, and repeats with short period
To avoid scenarios like this ...
a
m
c
X0
❖ ... Linear Conguential Generators |
It is a complex task to pick good numbers
Lewis, Goodman and Miller (1969) suggested
Most systems use more complex LCG-based algorithms
❖ Random Number Library |
Two functions are required:
srandom(int seed) // sets its argument as the seed (X0) random() // uses a LCG technique to generate random // numbers in the range 0 .. RAND_MAX
where the constant RAND_MAX
stdlib.h
Typically, RAND_MAX
The period (before repetition) is long, approximately 16·((231)-1)
❖ ... Random Number Library |
A problem:
But how to use srandom()
man 2 getpid
man 3 time
srandom()
❖ ... Random Number Library |
Random numbers are typically generated in a specific range:
int randomRange(int lo, int hi) { int n = random() % (hi-lo+1); return n + lo; }
LCG is not good for applications that need very high-quality random numbers
However, LCG good enough for day-to-day use.
Produced: 14 Jun 2020