This site is supported by donations to The OEIS Foundation.
Pseudorandom numbers
Pseudorandom numbers are numbers that appear (for practical purposes) to be random numbers but are actually deterministic, since they are generated algorithmically, starting from a seed which is either
- deterministic (for repeatability),
- pseudorandom (suitable for most purposes),
- truly random (for cryptography) (e.g. from a lava lamp[1] or a lens capped digital webcam[2]).
Contents
Pseudorandom number generators (PRNGs)
Many computer programming languages have built-in pseudorandom number generating functions that depend on the computer's clock to "seed" the generator. Since a typical clock has many cycles per second, the likelihood of repetition during normal use is reduced.
Some scientific calculators have a ran or rnd key that gives a [discrete] uniformly distributed pseudorandom rational number of the form with (resulting from a modulo 1000 operation), e.g., 0.352. The [discrete] distribution being uniform, it means that each of the 1000 rational numbers in the [0..1) interval are equiprobable.
Similarly, some computer algebra systems have built-in commands for pseudorandom numbers.
System integer in [0..n] real in
[0, 1) or [0, 1]? (Mathematica)
[0, 1) (PARI/GP)prime in [2..n] Wolfram Mathematica[3] RandomInteger[n]
RandomReal[]
RandomPrime[n]
PARI/GP[4] random(n+1)
random(1.)
randomprime(n)
Scaling and offsetting
These can be applied to another range of numbers easily enough (beware of preserving equiprobability though) by "scaling" (multiplication) and "offsetting" (addition). For example, if we wanted a pseudorandom integer in the range [10..548], we could compute 539 × 0.352 + 10 = 199.728 (unfortunately not in the [10..549) interval, but in the [10..548.461) interval, since we have only 3 significant digits... not good!) and use the floor function; although the map won't give results with satisfying equiprobability, since e.g.
- 539 × 0.999 + 10 = 548.461 yielding 548,
- 539 × 0.998 + 10 = 547.922 yielding 547,
- 539 × 0.997 + 10 = 547.383 yielding 547,
- 539 × 0.996 + 10 = 546.844 yielding 546,
- 539 × 0.995 + 10 = 546.305 yielding 546,
- 539 × 0.994 + 10 = 545.766 yielding 545,
- (...) = (...) ,
where we have 1000 distinct pigeons (or balls) fitted into 539 distinct holes (or boxes) , with an average of 1.855 pigeons per hole (a majority of holes with two pigeons, a minority of holes with only one pigeon: equiprobability has been lost) for each of the 539 resulting values. To preserve equiprobability, the number of balls must be an [integer] multiple of the number of boxes.
Linear congruential generators (LCGs)
The linear congruential method for generating a sequence of pseudorandom numbers uses the recurrence
where
- is a positive integer (the "modulus"),
- is a positive integer (the "multiplier"),
- is a nonnegative integer (the "increment"), and
- is a nonnegative integer (the "seed").
If the "increment" is positive, the method is called a mixed congruential generator. If the "increment" is 0, the generator is often called a multiplicative congruential generator (MCG), or Lehmer random number generator (Lehmer RNG), in which case the "modulus" must be a power of a prime number (ideally a prime number), the multiplier an element of high multiplicative order modulo (ideally a primitive root modulo ) and the "seed" must be coprime to the "modulus" , and thus nonzero.
This algorithm will obviously produce a cycle with length at most . It is most convenient to implement this algorithm via object-oriented programming, since this allows for many independently seeded instances of PRNGs with their own internal states, and thus many independant streams of pseudorandom numbers.
See also
- Quasirandom numbers and quasirandom sequences
- Pseudorandom numbers and pseudorandom sequences
- Random numbers and random sequences