Random number generator (included): Difference between revisions
→{{header|PL/I}}: correct lang tag usage |
|||
Line 52:
=={{header|PL/I}}==
Values produced by IBM Visualage PL/I compiler
built-in random number generator are uniformly distributed
between 0 and 1 [0
It uses a multiplicative congruential method:
<lang PL/I>seed(x) = mod(950706376 * seed(x-1), 2147483647)
random(x) = seed(x) / 2147483647</lang>
=={{header|Python}}==
|
Revision as of 18:02, 22 February 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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 a 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.
C
The C standard specifies that there be a pseudorandom number generator in the standard library <stdlib.h> There are no requirements as to the algorithm to be used for generating the random numbers. The standard specifies the interface, and how the rand() function reacts in a multithreaded environment. The rand() function will return an integer in the range 0-RAND_MAX. RAND_MAX must be at least 32767. The returned integers are to be uniformly distributed in this interval.[[1]]
The libraries of many popular C versions implement the rand() function with a linear congruential generator. The specific multiplier and constant varies by implementation, as does which subset of bits within the result is returned as the random number.
As mentioned above, linear congruential generators have problems in their 'randomness' and should not be used where a good quality random number generator is required.
C#
The .NET Random class says that it uses Knuth's subtractive random number generator algorithm.[2]
Factor
The default RNG used when the random
vocabulary is used, is the Mersenne twister algorithm [3]. 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. [4]
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.
Lua
Lua's math.random()
is an interface to the C rand()
function provided by the OS libc; its implementation varies by platform.
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.
Oz
Oz provides a binding to the C rand
function as OS.rand
.
Perl
Perl's rand
function will try and call drand48
, random
or rand
from the C library stdlib.h
in that order.
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.
PicoLisp
PicoLisp uses a linear congruential generator in the built-in (rand) function, with a multiplier suggested in Knuth's "Seminumerical Algorithms". See the documentation.
PL/I
Values produced by IBM Visualage PL/I compiler built-in random number generator are uniformly distributed between 0 and 1 [0 <= random < 1]
It uses a multiplicative congruential method: <lang PL/I>seed(x) = mod(950706376 * seed(x-1), 2147483647) random(x) = seed(x) / 2147483647</lang>
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.
Ursala
Ursala uses the Mersenne twister algorithm as implemented by the Avram run time system for most purposes, except for arbitrary precision floating point random numbers, which are generated by the urandomb
function from the
mpfr library.
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.