- Random number generation
A

**random number generator**(often abbreviated as RNG) is a computational or physical device designed to generate a sequence ofnumber s or symbols that lack any pattern, i.e. appearrandom . Computer-based systems for random number generation are widely used, but often fall short of this goal, though they may meet some statistical tests for randomness intended to ensure that they do not have any easily discernible patterns. Methods for generating random results have existed since ancient times, includingdice ,coin flipping , theshuffling ofplaying card s, the use ofyarrow stalks in theI Ching , and many other techniques.The many

applications of randomness have led to many different methods for generating random data. These methods may vary as to how unpredictable or statistically random they are, and how quickly they can generate random numbers.Before the advent of computational random number generators, generating large amount of sufficiently random numbers (important in statistics) required a lot of work. Results would sometimes be collected and distributed as

random number table s.**Physical methods**The earliest methods for generating random numbers —

dice ,coin flipping ,roulette wheels — are still used today, mainly in games and gambling as they tend to be too slow for applications in statistics and cryptography.Some physical phenomena, such as thermal noise in

Zener diode s appear to be truly random and can be used as the basis forhardware random number generator s. However, many mechanical phenomena feature asymmetries andsystematic bias es that make their outcomes not truly random. The many successful attempts to exploit such phenomena bygambler s, especially inroulette andblackjack are testimony to these effects. [*http://www.cs.sunysb.edu/~skiena/jaialai/excerpts/node5.html*]There are several imaginative sources of random numbers online. A common technique is to run a

hash function against a frame of a video stream from an unpredictable source. This technique was used byLavarand who used images of a number oflava lamp s.Lithium Technologies uses a camera pointed at the sky on a windy and cloudy day. Random.org has a more obvious approach of listening to atmospheric noise. Details about how they turn their input into random numbers can be found on their respective sites.Completely randomized design falls within the category of true random number generation. The generation of true random numbers outside the computer environment is based on the theory of entropy. Sources of entropy include nuclear decay and atmospheric conditions. [*http://www.fourmilab.ch/hotbits/ HotBits*] uses radioactive decay, while [*http://www.Random.org Random.org*] uses radio noise to generate randomness.**Computational methods**Pseudo-random number generator s (PRNGs) arealgorithm s that can automatically create long runs (for example, millions of numbers long) with good random properties but eventually the sequence repeats exactly (or the memory usage grows without bound). One of the most common PRNG is thelinear congruential generator , which uses the recurrence:$X\_\{n+1\}\; =\; (a\; X\_n\; +\; b),\; extrm\{mod\},\; m$

to generate numbers. The maximum number of numbers the formula can produce is the

modulus , "m". To avoid certain non-random properties of a singlelinear congruential generator , several such random number generators with slightly different values of the multiplier coeffient "a" are typically used in parallel, with a "master" random number generator that selects from among the several different generators.A simple pen-and-paper method for generating random numbers is the so-called

middle square method suggested byJohn Von Neumann . While simple to implement, its output is of poor quality.Most computer programming languages include functions or library routines that purport to be random number generators. They are often designed to provide a random byte or word, or a

floating point number uniformly distributed between 0 and 1.Such library functions often have poor statistical properties and some will repeat patterns after only tens of thousands of trials. They are often initialized using a computer's

real time clock as the seed. These functions may provide enough randomness for certain tasks (for example video games) but are unsuitable where high-quality randomness is required, such as in cryptographic applications, statistics or numerical analysis. Much higher quality random number sources are available on most operating systems; for example/dev/random on various BSD flavors, Linux, Mac OS X, IRIX, and Solaris, orCryptGenRandom for Microsoft Windows.**Practical applications and uses of random numbers**Random number generators have applications in

gambling ,statistical sampling ,computer simulation ,cryptography , and other areas where a random number is useful in producing an unpredictable result.Note that, in general, where unpredictability is paramount--such as in security applications-- hardware generators are generally preferred, where feasible, over pseudo-random algorithms.

Random number generators are very useful in developing

Monte Carlo method simulations asdebugging is facilitated by the ability to run the same sequence of random numbers again by starting from the same "random seed ". They are also used incryptography so long as the "seed" is secret. Sender and receiver can generate the same set of numbers automatically to use as keys.The generation of

pseudo-random number s is an important and common task in computer programming. While cryptography and certain numerical algorithms require a very high degree of "apparent" randomness, many other operations only need a modest amount of unpredictability. Some simple examples might be presenting a user with a "Random Quote of the Day", or determining which way a computer-controlled adversary might move in a computer game. Weaker forms of "randomness" are also closely associated withhash algorithm s and in creating amortized searching andsorting algorithm s.Some applications which appear at first sight to be suitable for randomization are in fact not quite so simple. For instance, a system that 'randomly' selects music tracks for a background music system must only "appear" to be random; a true random system would have no restriction on the same item appearing two or three times in succession.Fact|date=June 2008

**Activities and demonstrations**The

SOCR resource pages contain a number of [*http://wiki.stat.ucla.edu/socr/index.php/SOCR_EduMaterials_Activities_RNG hands-on interactive activities and demonstrations*] of random number generation using Java applets.**"True" random numbers vs. pseudorandom numbers**There are two principal methods used to generate random numbers. One measures some physical phenomenon that is expected to be random and then compensates for possible biases in the measurement process. The other uses computational

algorithm s that produce long sequences of apparently random results, which are in fact completely determined by a shorter initial value, known as a seed or key. The latter type are often calledpseudorandom number generator s.A "random number generator" based solely on deterministic computation "cannot" be regarded as a "true" random number generator, since its output is inherently predictable.

John von Neumann famously said "Anyone who uses arithmetic methods to produce random numbers is in a state of sin." How to distinguish a "true" random number from the output of a pseudo-random number generator is a very difficult problem. However, carefully chosen pseudo-random number generators can be used instead of true random numbers in many applications. Rigorous statistical analysis of the output is often needed to have confidence in the algorithm.**Generating random numbers from physical processes**There is general agreement that, if there are such things as "true" random numbers, they are most likely to be found by looking at physical processes which are, as far as is known, unpredictable.

A physical random number generator can be based on an essentially random atomic or subatomic physical phenomenon whose unpredictability can be traced to the laws of

quantum mechanics . An example of this are the Atari 8-bit computers, which usedelectronic noise from an analog circuit to generate true random numbers. [*http://www.atarimagazines.com/v7n11/randomatari.html*] Other examples includeradioactive decay , thermal noise,shot noise and clock drift. Evenlava lamp s have been used by theLavarand generator.To provide a degree of randomness intermediate between specialized hardware on the one hand and algorithmic generation on the other, some security related computer software requires the user to input a lengthy string of mouse movements, or keyboard input.

**Post-processing and statistical checks**Even given a source of plausible random numbers (perhaps from a quantum mechanically based hardware generator), obtaining numbers which are completely unbiased takes care. In addition, behavior of these generators often changes with temperature, power supply voltage, the age of the device, or other outside interference. And a software bug in a pseudo-random number routine, or a hardware bug in the hardware it runs on, may be similarly difficult to detect.

Generated random numbers are sometimes subjected to statistical tests before use to ensure that the underlying source is still working, and then post-processed to improve their statistical properties.

:"See also:

Statistical randomness "**Other considerations**Random numbers uniformly distributed between 0 and 1 can be used to generate random numbers of any desired distribution by passing them through the inverse

cumulative distribution function (CDF) of the desired distribution. Inverse CDFs are also called quantile functions. To generate a pair of statistically independent standard normally distributed random numbers ("x", "y"), one may first generate thepolar coordinates ("r", "θ"), where "r"~χ_{2}^{2}and "θ"~UNIFORM(0,2π) (seeBox-Muller transform ).Some 0 to 1 RNGs include 0 but exclude 1, while others include or exclude both.

The outputs of multiple independent RNGs can be combined (for example, using a bit-wise

XOR operation) to provide a combined RNG at least as good as the best RNG used. This is referred to as software whitening.Computational and hardware random number generators are sometimes combined to reflect the benefits of both kinds. Computational random number generators can typically generate pseudo-random numbers much faster than physical generators can generate true randomness.

**Low-discrepancy sequences as an alternative**Some computations making use of a random number generator can be summarized as the computation of a total or average value, such as the computation of integrals by the

Monte Carlo method . For such problems, it may be possible to find a more accurate solution by the use of so-calledlow-discrepancy sequence s, also calledquasirandom numbers. Such sequences have a definite pattern that fills in gaps evenly, qualitatively speaking; a truly random sequence may, and usually does, leave larger gaps.**Generation from a probability distribution**There are a couple of methods to generate a random number based on a

probability density function . These methods involve transforming a uniform random number in some way. Because of this, these methods work equally well in generating both pseudo-random and true random numbers. One method, called the inversion method, involves integrating up to an area greater than or equal to the random number (which should be generated between 0 and 1 for proper distributions). A second method, called the acceptance-rejection method, involves choosing an x and y value and testing whether the function of x is greater than the y value. If it is, the x value is accepted. Otherwise, the x value is rejected and the algorithm tries again. [*http://www.mathworks.com/access/helpdesk/help/toolbox/stats/index.html*]**ee also***

Randomization

*Randomized algorithm

*Hardware random number generator

*List of random number generators

*Random number generator attack

*Random password generator

*Randomness

*Procedural generation **External links**"Random numbers available over the internet and from parties not specifically known to and trusted by the user should not be used cryptographically."

* [

*http://www.numberator.com Numberator.com*] (Generates millions of numbers and codes sequentially or randomly online in seconds. Free version available.)

* http://www.randomizer.org

* [*http://gotentropy.artofinfosec.com Got Entropy ?*] (Cryptographic quality seeds/random numbers generated from RF noise)

* [*http://Yuzoz.com/ Yuzoz.com*] (random numbers generated from live space events)

* [*http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx Cryptographically Secure Random number on Windows without using CryptoAPI*] from MSDN

* [*http://www.random.org Random.org - generate random bitmaps, flip virtual coins etc.*] (random numbers generated fromatmospheric noise from aradio )

* [*http://www.fourmilab.ch/hotbits/ HotBits: Genuine Random Numbers*] (random numbers generated fromradioactive decay s)

* [*http://www.lavarnd.org/demo/index.html LavaRnd demonstration*] (random numbers generated from a webcam CCD chip)

* [*http://www.randomnumbers.info/ RandomNumbers.info*] (random numbers generated by exploiting elementary quantum optics process)

* [*http://www.kenotracker.com/keno/Random.asp KenoRND()*] (random numbers generated from results of live keno at real casinos)

* [*http://www.true-random.com/ www.true-random.com*] (random numbers generated from digital noise and based on the central limit theorem)

* [*http://www.westphal-electronic.com/ True (physical) random number generators (e.g. with USB interface)*]

* http://www.idquantique.com/products/quantis.htm - True random number generators based on quantum physics

* http://random.mat.sbg.ac.at - uniform random number generators

* [*http://www.embedded.com/showArticle.jhtml?articleID=20900500 Generating random numbers*] Generating random numbers inEmbedded Systems

* [*http://www.saccenti.com/randomnumber/randomnumber.htm Free Random Number Generator*] Open-source code for creating random numbers using Visual Basic

* [*http://rqube.seifseit.de RQube*] Free software for generating random sequences for experimental purpose inbehavioural sciences andsocial sciences .

* [*http://www.westphal-electronic.com/zgloss_e.htm Glossary of words concerning true random number generation*]

*Wikimedia Foundation.
2010.*