Random number generator (included): Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Delphi}}: Use interwiki link style)
(added D)
Line 1: Line 1:
{{Task}}
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.<br>
: If possible, a link to a wider [[wp:List of random number generators|explanation]] of the algorithm used should be given.

<small>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.</small>

The main types of pseudo-random number generator, ([[wp:PRNG|PRNG]]), that are in use are the Linear Congruential Generator, ([[wp:Linear congruential generator|LCG]]), and the Generalized Feedback Shift Register, ([[wp:Generalised_feedback_shift_register#Non-binary_Galois_LFSR|GFSR]]), (of which the [[wp:Mersenne twister|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 [[wp:Cryptographic hash function|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 [[wp:Monte Carlo method|Monte Carlo simulation]] and [[wp:Cryptography|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.

=={{header|ActionScript}}==
In both Actionscript 2 and 3, the type of pseudorandom number generator is implementation-defined. This number generator is accessed through the Math.random() function, which returns a double greater than or equal to 0 and less than 1.[http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/Math.html#random%28%29][http://flash-reference.icod.de/Math.html#random%28%29] In Actionscript 2, the global random() function returns an integer greater than or equal to 0 and less than the given argument, but it is deprecated and not recommended.[http://flash-reference.icod.de/global_functions.html#random()]

=={{header|Ada}}==
The Ada standard defines Random Number Generation in Annex A.5.2. There are two kinds of RNGs, Ada.Numerics.Float_Random for floating point values from 0.0 to 1.0, and Ada.Numerics.Discrete_Random for pseudo-random values of enumeration types (including integer types). It provides facilities to initialize the generator and to save it's state.

The standard requires the implementation to uniformly distribute over the range of the result type.

The used algorithm is implementation defined. The standard says: "To enable the user to determine the suitability of the random number generators for the intended application, the implementation shall describe the algorithm used and shall give its period, if known exactly, or a lower bound on the period, if the exact period is unknown."

[http://www.adahome.com/rm95/rm9x-A-05-02.html|Ada 95 RM - A.5.2 Random Number Generation]
[http://www.adaic.com/standards/05rm/html/RM-A-5-2.html|Ada 2005 RM - A.5.2 Random Number Generation]

=={{header|ALGOL 68}}==
Details of the random number generator are in the Revised Reports sections: 10.2.1. and 10.5.1.
* [http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rrA2.html 10.2. The standard prelude - 10.2.1. Environment enquiries]
* [http://vestein.arb-phys.uni-dortmund.de/~wb/RR/rrA5.html 10.5. The particular preludes and postlude - 10.5.1. The particular preludes]
<lang algol68>PROC ℒ next random = (REF ℒ INT a)ℒ REAL: ( a :=
¢ the next pseudo-random ℒ integral value after 'a' from a
uniformly distributed sequence on the interval [ℒ 0,ℒ maxint] ¢;

¢ the real value corresponding to 'a' according to some mapping of
integral values [ℒ 0, ℒ max int] into real values [ℒ 0, ℒ 1)
i.e. such that -0 <= x < 1 such that the sequence of real
values so produced preserves the properties of pseudo-randomness
and uniform distribution of the sequence of integral values ¢);

INT ℒ last random := # some initial random number #;
PROC ℒ random = ℒ REAL: ℒ next random(ℒ last random);</lang>

Note the suitable "next random number" is suggested to be: ( a := &cent; the next pseudo-random ℒ integral value after 'a' from a uniformly distributed sequence on the interval [ℒ 0,ℒ maxint] &cent;; &cent; the real value corresponding to 'a' according to some mapping of integral values [ℒ 0, ℒ max int] into real values [ℒ 0, ℒ 1) i.e., such that -0 <= x < 1 such that the sequence of real values so produced preserves the properties of pseudo-randomness and uniform distribution of the sequence of integral values &cent;);

Algol68 supports random number generation for all precisions available for the specific implementation. The prefix '''ℒ real''' indicates all the available precisions. eg '''short short real''', '''short real''', '''real''', '''long real''', '''long long real''' etc

For an ASCII implementation and for '''long real''' precision these routines would appears as:
<lang algol68>PROC long next random = (REF LONG INT a)LONG REAL: # some suitable next random number #;
INT long last random := # some initial random number #;
PROC long random = LONG REAL: long next random(long last random);</lang>

=={{header|AutoHotkey}}==
The built-in command [http://www.autohotkey.com/docs/commands/Random.htm Random] generates a pseudo-random number using Mersenne Twister "MT19937" (see documentation).

=={{header|Batch File}}==
Windows batch files can use the <code>%RANDOM%</code> pseudo-variable which returns a pseudo-random number between 0 and 32767. Behind the scenes this is just a call to the C runtime's <code>rand()</code> function which uses an LCG in this case:
:<math>X_{n+1}=X_n\cdot 214013 + 2531011 \pmod {2^{15}}</math>

=={{header|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.[[http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf]]

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.

=={{header|C sharp|C#}}==
The .NET Random class says that it uses Knuth's subtractive random number generator algorithm.[http://msdn.microsoft.com/en-us/library/system.random.aspx#remarksToggle]

=={{header|Clojure}}==
=={{header|Clojure}}==
See Java.
See Java.


=={{header|Delphi}}==
=={{header|D}}==
From std.random:
According to [[wp:Linear_congruential_generator#Parameters_in_common_use|Wikipedia]], Delphi uses a Linear Congruential Generator.

=={{header|Factor}}==
The default RNG used when the <code>random</code> vocabulary is used, is the [[wp:Mersenne twister|Mersenne twister]] algorithm [http://docs.factorcode.org/content/article-random.html]. But there are other RNGs available, including [[wp:SFMT|SFMT]], the system RNG ([[wp:/dev/random|/dev/random]] on Unix) and [[wp:Blum Blum Shub|Blum Blum Shub]]. It's also very easy to implement your own RNG and integrate it into the system. [http://docs.factorcode.org/content/article-random-protocol.html]

=={{header|GAP}}==
GAP may uses two algorithms : MersenneTwister, or algorithm A in section 3.2.2 of TAOCP (which is the default). On may create several ''random sources'' in parallel, or a global one (based on the TAOCP algorithm).
<lang gap># Creating a random source
rs := RandomSource(IsMersenneTwister);

# Generate a random number between 1 and 10
Random(rs, 1, 10);

# Same with default random source
Random(1, 10);</lang>
One can get random elements from many objects, including lists
<lang gap>
Random([1, 10, 100]);

# Random permutation of 1..200
Random(SymmetricGroup(200));

# Random element of Z/23Z :
Random(Integers mod 23);</lang>
=={{header|Go}}==
Go has two packages providing random numbers.
# Rand has general purpose random number support. The code attributes the algorithm to DP Mitchell and JA Reeds, and with what little I know, I would guess it's an GFSR. (It uses a large array commented "feeback register" and has variables named "tap" and "feed.")
# Crypto/rand says it "implements a cryptographically secure pseudorandom number generator." I think though it should say that it ''accesses'' a cryptographically secure pseudorandom number generator. It uses /dev/urandom on Linix and similar systems and the CryptGenRandom API on Windows.

=={{header|Haskell}}==
The [http://www.haskell.org/onlinereport/random.html Haskell 98 report] specifies an interface for pseudorandom number generation and requires that implementations be minimally statistically robust. It is silent, however, on the choice of algorithm.

=={{header|Icon}} and {{header|Unicon}} ==
Icon and Unicon both use the same linear congruential random number generator x := (x * 1103515245 + 453816694) mod 2^31. Icon uses an initial seed value of 0 and Unicon randomizes the initial seed.

This LCRNG has a number of well documented quirks (see [http://www.cs.arizona.edu/icon/analyst/ia.htm The Icon Analyst issues #26, 28, 38]) relating to the choices of an even additive and a power of two modulus. This LCRNG produces two independent sequences of length 2^30 one of even numbers the other odd.

Additionally, the {{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/src/procs/random.icn random] provides related procedures including a parametrized LCRNG that defaults to the built-in values.

=={{header|Inform 7}}==
Inform's random functions are built on the random number generator exposed at runtime by the virtual machine, which is implementation-defined.

=={{header|J}}==
By default J's <code>?</code> primitive (Roll/Deal) uses the Mersenne twister algorithm, but can be set to use a number of other algorithms as detailed on the [http://www.jsoftware.com/help/dictionary/d640.htm J Dictionary page for Roll/Deal].

=={{header|Java}}==
Java's <code>Random</code> class uses a [[wp:Linear congruential generator|Linear congruential formula]], as described in [http://java.sun.com/javase/6/docs/api/java/util/Random.html its documentation]. The commonly used <code>Math.random()</code> uses a <code>Random</code> object under the hood.

=={{header|Lua}}==
Lua's <code>math.random()</code> is an interface to the C <code>rand()</code> function provided by the OS libc; its implementation varies by platform.

=={{header|Mathematica}}==
Mathematica 7, by default, uses an Extended Cellular Automaton method ("ExtendedCA") to generate random numbers. The main PRNG functions are <code>RandomReal[]</code> and <code>RandomInteger[]</code> You can specify alternative generation methods including the Mersenne Twister and a Linear Congruential Generator (the default earlier versions). Information about random number generation is provided at [http://reference.wolfram.com/mathematica/tutorial/RandomNumberGeneration.html#185956823 Mathematica].

=={{header|MATLAB}}==
MATLAB uses the Mersenne Twister as its default random number generator. Information about how the "rand()" function is utilized is given at [http://www.mathworks.com/help/techdoc/ref/rand.html MathWorks].

=={{header|OCaml}}==
OCaml provides a module called [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Random.html Random] in its standard library. It used to be a "Linear feedback shift register" pseudo-random number generator (References: Robert Sedgewick, "Algorithms", Addison-Wesley). It is now (as of version 3.12.0) a "lagged-Fibonacci F(55, 24, +) with a modified addition function to enhance the mixing of bits." It passes the Diehard test suite.

=={{header|Oz}}==
Oz provides a binding to the C <code>[http://www.opengroup.org/onlinepubs/000095399/functions/rand.html rand]</code> function as <code>[http://www.mozart-oz.org/home/doc/system/node56.html#label719 OS.rand]</code>.

=={{header|PARI/GP}}==
<code>random</code> uses Richard Brent's [http://wwwmaths.anu.edu.au/~brent/random.html xorgens]. It's a member of the xorshift class of PRNGs and provides good, fast pseudorandomness (passing the big crush test, unlike the Mersenne twister), but it is not cryptographically strong. As implemented in Pari, its period is "at least <math>2^{4096}-1.</math>

=={{header|Perl}}==
Perl's <code>[http://perldoc.perl.org/functions/rand.html rand]</code> function will try and call <code>[http://www.opengroup.org/onlinepubs/007908775/xsh/drand48.html drand48]</code>, <code>[http://www.opengroup.org/onlinepubs/000095399/functions/random.html random]</code> or <code>[http://www.opengroup.org/onlinepubs/000095399/functions/rand.html rand]</code> from the C library <code>[http://www.opengroup.org/onlinepubs/000095399/basedefs/stdlib.h.html stdlib.h]</code> in that order.

=={{header|PHP}}==
PHP has two random number generators: <code>[http://us3.php.net/manual/en/function.rand.php rand]</code>, which uses the underlying C library's <code>rand</code> function; and <code>[http://us3.php.net/manual/en/function.mt-rand.php mt_rand]</code>, which uses the [[wp:Mersenne twister|Mersenne twister]] algorithm.

=={{header|PicoLisp}}==
PicoLisp uses a linear congruential generator in the built-in (rand) function,
with a multiplier suggested in Knuth's "Seminumerical Algorithms". See the
[http://software-lab.de/doc/refR.html#rand documentation].

=={{header|PL/I}}==
Values produced by IBM Visualage PL/I compiler
built-in random number generator are uniformly distributed
between 0 and 1 [0 &lt;= random &lt; 1]

It uses a multiplicative congruential method:
<lang PL/I>seed(x) = mod(950706376 * seed(x-1), 2147483647)
random(x) = seed(x) / 2147483647</lang>

=={{header|PowerShell}}==
The [http://technet.microsoft.com/en-us/library/dd315402.aspx <code>Get-Random</code>] cmdlet (part of PowerShell 2) uses the .NET-supplied pseudo-random number generator which uses Knuth's subtractive method; see [[#C#|C#]].

=={{header|PureBasic}}==
PureBasic has two random number generators, <tt>Random()</tt> and <tt>CryptRandom()</tt>. <tt>Random()</tt> uses a RANROT type W generator [http://www.agner.org/random/theory/chaosran.pdf]. <tt>CryptRandom()</tt> uses a very strong PRNG that makes use of a cryptographic safe random number generator for its 'seed', and refreshes the seed if such data is available. The exact method used for <tt>CryptRandom()</tt> is uncertain.

=={{header|Python}}==
Python uses the [[wp:Mersenne twister|Mersenne twister]] algorithm accessed via the built-in [http://docs.python.org/library/random.html random module].

=={{header|Ruby}}==
Ruby's <code>rand</code> function currently uses the [[wp:Mersenne twister|Mersenne twister]] algorithm, as described in [http://www.ruby-doc.org/core/classes/Kernel.html#M005974 its documentation].

=={{header|R}}==
For uniform random numbers, R may use Wichmann-Hill, Marsaglia-multicarry, Super-Duper, Mersenne-Twister, or Knuth-TAOCP
(both 1997 and 2002 versions), or a user-defined method. The default is Mersenne Twister.

R is able to generate random numbers from a variety of distributions, e.g.

# Beta
# Binomial
# Cauchy
# Chi-Squared
# Exponential
# F
# Gamma
# Geometric
# Hypergeometric
# Logistic
# Log Normal
# Multinomial
# Negative Binomial
# Normal
# Poisson
# Student t
# Uniform
# Weibull

See R help on [http://pbil.univ-lyon1.fr/library/base/html/Random.html Random number generation], or in the R system type
<lang R>?RNG
help.search("Distribution", package="stats")</lang>

=={{header|Tcl}}==
Tcl uses a [[wp:Linear congruential generator|linear congruential generator]] in it's built-in <code>rand()</code> 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 <tt>rand</tt> 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.

=={{header|Ursala}}==
Ursala uses the [[wp:Mersenne twister|Mersenne twister]] algorithm as implemented by the [http://www.basis.uklinux.net/avram Avram] run time system for most purposes, except for arbitrary precision floating point random numbers, which are generated by the <code>urandomb</code> function from the
[http://www.mpfr.org mpfr] library.

{{omit from|bc|No RNG.}}
{{omit from|dc|No RNG.}}
{{omit from|sed|This language has no numbers!}}
{{omit from|Unlambda}}

=={{header|ZX Spectrum Basic}}==

The ZX Spectrum uses a pseudorandom number generator that utilizes values stored in the sytem ROM. The random numbers produced will repeat after 65535 iterations.



The generators feature a number of well-known and well-documented methods of generating random numbers. An overall fast and reliable means to generate random numbers is the Mt19937 generator, which derives its name from "[http://en.wikipedia.org/wiki/Mersenne_twister|Mersenne Twister] with a period of 2 to the power of 19937". In memory-constrained situations, [http://en.wikipedia.org/wiki/Linear_congruential_generator|linear congruential] generators such as MinstdRand0 and MinstdRand might be useful. The standard library provides an alias Random for whichever generator it considers the most fit for the target environment.
[[Category:Randomness]]

Revision as of 10:55, 5 June 2011

Clojure

See Java.

D

From std.random:

The generators feature a number of well-known and well-documented methods of generating random numbers. An overall fast and reliable means to generate random numbers is the Mt19937 generator, which derives its name from "Twister with a period of 2 to the power of 19937". In memory-constrained situations, congruential generators such as MinstdRand0 and MinstdRand might be useful. The standard library provides an alias Random for whichever generator it considers the most fit for the target environment.

Retrieved from "https://rosettacode.org/wiki/Random_number_generator_(included)?oldid=136560"