Pseudorandom numbers

This article page is a stub, please help by expanding it.

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 or a lens capped digital webcam).

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 $\scriptstyle {\frac {n}{1000}}$ with $\scriptstyle 0\,\leq \,n\,<\,1000$ (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	RandomInteger[n]	RandomReal[]	RandomPrime[n]
PARI/GP	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

${\begin{aligned}a(0)&:=s,\\a(n)&:=Z\cdot a(n-1)+I{\pmod {M}},\quad n\geq 1,\\\end{aligned}}$

where

• $\scriptstyle M$ is a positive integer (the "modulus"),
• $\scriptstyle Z,\,0\,<\,Z\,<\,M,$ is a positive integer (the "multiplier"),
• $\scriptstyle I,\,0\,\leq \,I\,<\,M,$ is a nonnegative integer (the "increment"), and
• $\scriptstyle s,\,0\,\leq \,s\,<\,M,$ 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" $\scriptstyle M$ must be a power of a prime number (ideally a prime number), the multiplier $\scriptstyle Z$ an element of high multiplicative order modulo $\scriptstyle M$ (ideally a primitive root modulo $\scriptstyle M$) and the "seed" must be coprime to the "modulus" $\scriptstyle M$, and thus nonzero.

This algorithm will obviously produce a cycle with length at most $\scriptstyle M$. 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

External links

• Linear congruential generator—Wikipedia.org.
• Lehmer random number generator—Wikipedia.org.