Random number generator (included)

Random number generator (included)
You are encouraged to solve this task according to the task description, using any language you may know.

The task is to:

State the type of random number generator algorithm used in a languages built-in random number generator, or omit the language if no random number generator is given as part of the language or its immediate libraries.

If possible, a link to a wider explanation of the algorithm used should be given.

Note: the task is not to create an RNG, but to report on the languages in-built RNG that would be the most likely RNG used.

The main types of pseudo-random number generator, (PRNG), that are in use are the Linear Congruential Generator, (LCG), and the Generalized Feedback Shift Register, (GFSR), (of which the Mersenne twister generator is a subclass). The last main type is where the output of one of the previous ones (typically a Mersenne twister) is fed through a cryptographic hash function to maximize unpredictability of individual bits.

LCGs have the advantage of not requiring much state and being very fast to calculate, but produce random numbers with spectral problems. This makes them unsuitable for both Monte Carlo simulation and cryptography. By contrast, GFSRs (of which the Mersenne Twister is is particularly high quality version) require a lot more internal state and are considerably more expensive to compute and initialize (so much so that it is normal to use a LCG or simpler GFSR to drive the initialization); GFSRs tend to have much higher quality spectral properties than LCGs, and are suitable for use in Monte Carlo simulation. Neither LCGs nor GFSRs should be used for the most demanding applications (cryptography) without additional steps.

Factor

The default RNG used when the random vocabulary is used, is the Mersenne twister algorithm [1]. But there are other RNGs available, including SFMT, the system RNG (/dev/random on Unix) and Blum Blum Shub. It's also very easy to implement your own RNG and integrate it into the system. [2]

J

By default J's ? primitive (Roll/Deal) uses the Mersenne twister algorithm, but can be set to use a number of other algorithms as detailed on the J Dictionary page for Roll/Deal.

Java

Java's Random class uses a Linear congruential formula, as described in its documentation. The commonly used Math.random() uses a Random object under the hood.

OCaml

OCaml provides a module called Random in its standard library which is a "Linear feedback shift register" pseudo-random number generator (References: Robert Sedgewick, "Algorithms", Addison-Wesley). It is seeded by a MD5-based PRNG.

PHP

PHP has two random number generators: rand, which uses the underlying C library's rand function; and mt_rand, which uses the Mersenne twister algorithm.

Python

Python uses the Mersenne twister algorithm accessed via the built-in random module.

Ruby

Ruby's rand function currently uses the Mersenne twister algorithm, as described in its documentation.

Tcl

Tcl uses a linear congruential generator in it's built-in rand() function. This is seeded by default from the system time, and kept per-interpreter so different security contexts and different threads can't affect each other's generators (avoiding key deployment issues with the rand function from C's math library).

Citations (from Tcl source code):

• S.K. Park & K.W. Miller, “Random number generators: good ones are hard to find,” Comm ACM 31(10):1192-1201, Oct 1988
• W.H. Press & S.A. Teukolsky, “Portable random number generators,” Computers in Physics 6(5):522-524, Sep/Oct 1992.