|
|
|
|
pseudorandom numbers
|
(Definition)
|
|
|
Generated in a digital computer by a numerical algorithm, pseudorandom numbers are not random, but should appear to be random when used in Monte Carlo calculations.
The most widely used and best understood pseudorandom generator is the Lehmer multiplicative congruential generator, in which each number  is calculated as a function of the preceding number in the sequence
or
where  and  are carefully chosen constants, and  is usually a power of two,  . All quantities appearing in the formula (except  ) are integers of  bits. The expression in brackets is an integer of length  bits, and the effect of the modulo  is to mask off the most significant part of the result of the multiplication.  is the seed of a generation sequence; many generators allow one to start with a different seed for each run of a program, to avoid re-generating the same sequence, or to preserve the seed at the end of one run for the beginning of a subsequent one. Before being used in calculations, the  are usually transformed to floating point numbers normalized into the range ![$ [0,1]$](http://images.planetmath.org:8080/cache/objects/1274/l2h/img14.png "$ [0,1]$") . Generators of this type can be found which attain the maximum possible period of  ,
and whose sequences pass all reasonable tests of “randomness”, provided one does not exhaust more than a few percent of the full period.
Multiplicative random number generators have serious limitations as random number generators for many tasks, especially those that involve looking at spectra. A number of other fast random number generators exist (such as the Mersenne Twister) all with various proven good qualities.
For many scientific projects, analysis techniques are used that are extremely sensitive to patterns in the input, so when generating fake input using pseudorandom number generators, it is often necessary to use extremely good quality pseudorandom numbers. For some projects it is in fact appropriate to use a hardware device which generates truly random numbers, although even this must be scoured clean of
patterns. Some computers now have hardware random number generators built in.
However, there is a completely separate category of pseudorandom number generators, namely those used in cryptography. Here the goal is to make it computationally infeasible to deduce the next “random” bit in spite of knowing all preceding (and possibly many future) bits. Such pseudorandom number generators can in fact serve as cryptosystems themselves: the requirements for such a random number generator are exactly the same as those for a stream cipher. They are generally more expensive to run but produce much higher quality random numbers. To be used in a cryptographic application, they should
also have a sophisticated reseeding schedule and a source of genuine randomness to provide recovery from exposure of their internal state.
|
"pseudorandom numbers" is owned by akrowne. [ full author list (2) ]
|
|
(view preamble)
Cross-references: source, application, stream, cryptography, category, even, truly random numbers, generates, necessary, generating, projects, random number, percent, period, type, range, point, preserve, multiplication, length, expression, integers, power of two, sequence, function, number, generator, multiplicative, pseudorandom generator, Monte Carlo, algorithm
There are 3 references to this entry.
This is version 4 of pseudorandom numbers, born on 2002-01-04, modified 2004-03-26.
Object id is 1274, canonical name is PseudorandomNumbers.
Accessed 6074 times total.
Classification:
| AMS MSC: | 11K45 (Number theory :: Probabilistic theory: distribution modulo $1$; metric theory of algorithms :: Pseudo-random numbers; Monte Carlo methods) | | | 65C10 (Numerical analysis :: Probabilistic methods, simulation and stochastic differential equations :: Random number generation) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
