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.

Note that LCGs nor GFSRs should be used for the most demanding applications (cryptography) without additional steps.

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.[1][2] 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.[3]

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."

95 RM - A.5.2 Random Number Generation 2005 RM - A.5.2 Random Number Generation

ALGOL 68

Details of the random number generator are in the Revised Reports sections: 10.2.1. and 10.5.1.

• 10.2. The standard prelude - 10.2.1. Environment enquiries
• 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 := ¢ 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 ¢);

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>

AutoHotkey

The built-in command Random generates a pseudo-random number using Mersenne Twister "MT19937" (see documentation).

BASIC

The RND function generates a pseudo random number greater than or equal to zero, but less than one. The implementation is machine specific based on contents of the ROM and there is no fixed algorithm.

Batch File

Windows batch files can use the %RANDOM% 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 rand() function which uses an LCG in this case:

$X_{n+1}=X_{n}\cdot 214013+2531011{\pmod {2^{15}}}$

BBC BASIC

The RND function uses a 33-bit maximal-length Linear Feedback Shift Register (LFSR), with 32-bits being used to provide the result. Hence the sequence length is 2^33-1, during which the value zero is returned once and all non-zero 32-bit values are each returned twice.

C

Standard C has rand(). Some implementations of C have other sources of random numbers, along with rand().

C rand()

The C standard specifies the interface to the rand() and srand() functions in <stdlib.h>.

• void srand(unsigned int seed) begins a new sequence of pseudorandom integers.
• int rand(void) returns a pseudorandom integer in the range from 0 to RAND_MAX.
  • RAND_MAX must be at least 32767.

The same seed to srand() reproduces the same sequence. The default seed is 1, when a program calls rand() without calling srand(); so srand(1) reproduces the default sequence. (n1124.pdf)

There are no requirements as to the algorithm to be used for generating the random numbers. All versions of rand() return integers that are uniformly distributed in the interval from 0 to RAND_MAX, but some algorithms have problems in their randomness. For example, the cycle might be too short, or the probabilities might not be independent.

Many popular C libraries implement rand() 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. These rand() functions should not be used where a good quality random number generator is required.

BSD rand()

Among current systems, BSD might have the worst algorithm for rand(). BSD rand() sets RAND_MAX to $2^{31}-1$ and uses this linear congruential formula:

• $state_{n+1}=1103515245\times state_{n}+12345{\pmod {2^{31}}}$
• $rand_{n}=state_{n}$

FreeBSD switched to a different formula, but NetBSD and OpenBSD stayed with this formula. (NetBSD rand.c, OpenBSD rand.c)

BSD rand() produces a cycling sequence of only $2^{31}$ possible states; this is already too short to produce good random numbers. The big problem with BSD rand() is that the low $n$ bits' cycle sequence length is only $2^{n}$. (This problem happens because the modulus $2^{31}$ is a power of two.) The worst case, when $n=1$, becomes obvious if one uses the low bit to flip a coin.

<lang c>#include <stdio.h>

1. include <stdlib.h>

/* Flip a coin, 10 times. */ int main() { int i; srand(time(NULL)); for (i = 0; i < 10; i++) puts((rand() % 2) ? "heads" : "tails"); return 0; }</lang>

If the C compiler uses BSD rand(), then this program has only two possible outputs.

• At even seconds: heads, tails, heads, tails, heads, tails, heads, tails, heads, tails.
• At odd seconds: tails, heads, tails, heads, tails, heads, tails, heads, tails, heads.

The low bit manages a uniform distribution between heads and tails, but it has a period length of only 2: it can only flip a coin 2 times before it must repeat itself. Therefore it must alternate heads and tails. This is not a real coin, and these are not truly random flips.

In general, the low bits from BSD rand() are much less random than the high bits. This defect of BSD rand() is so famous that some programs ignore the low bits from rand().

Microsoft rand()

Microsoft sets RAND_MAX to 32767 and uses this linear congruential formula:

• $state_{n+1}=214013\times state_{n}+2531011{\pmod {2^{31}}}$
• $rand_{n}=seed_{n}\div 2^{16}$

POSIX drand48()

POSIX adds the drand48() family to <stdlib.h>.

• void srand48(long seed) begins a new sequence.
• double drand48(void) returns a random double in [0.0, 1.0).
• long lrand48(void) returns a random long in [0, 2**31).
• long mrand48(void) returns a random long in [-2**31, 2**31).

This family uses a 48-bit linear congruential generator with this formula:

• $r_{n+1}=25214903917\times r_{n}+11{\pmod {2^{48}}}$

C#

The .NET Random class says that it uses Knuth's subtractive random number generator algorithm.[4]

Clojure

See Java.

CMake

CMake has a random string generator.

<lang cmake># Show random integer from 0 to 9999. string(RANDOM LENGTH 4 ALPHABET 0123456789 number) math(EXPR number "${number} + 0") # Remove extra leading 0s. message(STATUS ${number})</lang>

The current implementation (in cmStringCommand.cxx and cmSystemTools.cxx) calls rand() and srand() from C. It picks random letters from the alphabet. The probability of each letter is near 1 ÷ length, but the implementation uses floating-point arithmetic to map RAND_MAX + 1 values onto length letters, so there is a small modulo bias when RAND_MAX + 1 is not a multiple of length.

CMake 2.6.x has bug #9851; two random strings might be equal because they use the same seed. CMake 2.8.0 fixes this bug by seeding the random generator only once, during the first call to string(RANDOM ...).

CMake 2.8.5 tries a secure seed (CryptGenRandom or /dev/urandom) or falls back to high-resolution system time. Older versions seed the random generator with time(NULL), the current time in seconds.

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 "Mersenne Twister with a period of 2 to the power of 19937". In memory-constrained situations, 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.

Déjà Vu

The standard implementation, vu, currently uses the rand() from C.

<lang dejavu>print rand 0 1 # prints a pseudo-random floating-point number between 0 and 1</lang>

Delphi

According to Wikipedia, Delphi uses a Linear Congruential Generator.

DWScript

DWScript currently uses a 64bit XorShift PRNG, which is a fast and light form of GFSR.

Erlang

Random number generator. The method is attributed to B.A. Wichmann and I.D.Hill, in 'An efficient and portable pseudo-random number generator', Journal of Applied Statistics. AS183. 1982. Also Byte March 1987.

The current algorithm is a modification of the version attributed to Richard A O'Keefe in the standard Prolog library.

Every time a random number is requested, a state is used to calculate it, and a new state produced. The state can either be implicit (kept in the process dictionary) or be an explicit argument and return value. In this implementation, the state (the type ran()) consists of a tuple of three integers.

It should be noted that this random number generator is not cryptographically strong. If a strong cryptographic random number generator is needed for example crypto:rand_bytes/1 could be used instead.

Seed with a fixed known value triplet A1, A2, A3: <lang Erlang> random:seed(A1, A2, A3) </lang> Example with the running time: <lang Erlang> ... {A1,A2,A3} = now(), random:seed(A1, A2, A3), ...sequence of randoms used random:seed(A1, A2, A3), ...same sequence of randoms used </lang> Get a random float value between 0.0 and 1.0: <lang Erlang> Rfloat = uniform(), </lang> Get a random integer value between 1 and N (N is an integer >= 1): <lang Erlang> Rint = uniform(N), </lang>

Factor

The default RNG used when the random vocabulary is used, is the Mersenne twister algorithm [5]. 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. [6]

GAP

GAP may use two algorithms : MersenneTwister, or algorithm A in section 3.2.2 of TAOCP (which is the default). One 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);

1. Generate a random number between 1 and 10

Random(rs, 1, 10);

1. 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]);

1. Random permutation of 1..200

Random(SymmetricGroup(200));

1. Random element of Z/23Z :

Random(Integers mod 23);</lang>

Go

Go has two packages providing random numbers.

1. 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.")
2. 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.

Golfscript

Golfscript uses Ruby's Mersenne Twister algorithm

~rand produces a random integer between 0 and n-1, where n is a positive integer piped into the program

Groovy

Same as Java.

Haskell

The 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.

Icon and 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 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

Library: Icon Programming Library

random provides related procedures including a parametrized LCRNG that defaults to the built-in values.

Inform 7

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

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.

JavaScript

The only built-in random number generation facility is Math.random(), which returns a floating-point number greater than or equal to 0 and less than 1, with approximately uniform distribution. The standard (ECMA-262) does not specify what algorithm is to be used.

Lua

Lua's math.random() is an interface to the C rand() function provided by the OS libc; its implementation varies by platform.

Mathematica

Mathematica 7, by default, uses an Extended Cellular Automaton method ("ExtendedCA") to generate random numbers. The main PRNG functions are RandomReal[] and RandomInteger[] 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 Mathematica.

MATLAB

MATLAB uses the Mersenne Twister as its default random number generator. Information about how the "rand()" function is utilized is given at MathWorks.

Maxima

Maxima uses a Lisp implementation of the Mersenne Twister. See ? random for help, or file share/maxima/5.28.0-2/src/rand-mt19937.lisp for the source code.

There are also random generators for several distributions in package distrib :

• random_bernoulli
• random_beta
• random_binomial
• random_cauchy
• random_chi2
• random_continuous_uniform
• random_discrete_uniform
• random_exp
• random_f
• random_gamma
• random_general_finite_discrete
• random_geometric
• random_gumbel
• random_hypergeometric
• random_laplace
• random_logistic
• random_lognormal
• random_negative_binomial
• random_noncentral_chi2
• random_noncentral_student_t
• random_normal
• random_pareto
• random_poisson
• random_rayleigh
• random_student_t
• random_weibull

Note: the package distrib also has functions starting with pdf, cdf, quantile, mean, var, std, skewness or kurtosis instead of random, except the Cauchy distribution, which does not have moments.

Modula-3

The Random interface in Modula-3 states that it uses "an additive generator based on Knuth's Algorithm 3.2.2A".

Nemerle

Uses .Net Random class; so, as mentioned under C#, above, implements Knuth's subtractive random number generator algorithm. Random class documentation at MSDN.

OCaml

OCaml provides a module called 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.

Octave

As explained here (see rand function), Octave uses the "Mersenne Twister with a period of 2^19937-1".

Oz

Oz provides a binding to the C rand function as OS.rand.

PARI/GP

random uses Richard Brent's xorgens. It's a member of the xorshift class of PRNGs and provides good, fast pseudorandomness (passing the BigCrush test, unlike the Mersenne twister), but it is not cryptographically strong. As implemented in PARI, its period is "at least $2^{4096}-1$".

<lang parigp>setrand(3) random(6)+1 \\ chosen by fair dice roll. \\ guaranteed to the random.</lang>

Pascal

FreePascal's function random uses the MersenneTwister (for further details, see the file rtl/inc/system.inc)

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>

PL/SQL

Oracle Database has two packages that can be used for random numbers generation.

DBMS_RANDOM

The DBMS_RANDOM package provides a built-in random number generator. This package is not intended for cryptography. It will automatically initialize with the date, user ID, and process ID if no explicit initialization is performed. If this package is seeded twice with the same seed, then accessed in the same way, it will produce the same results in both cases. <lang PL/SQL>DBMS_RANDOM.RANDOM --produces integers in [-2^^31, 2^^31). DBMS_RANDOM.VALUE --produces numbers in [0,1) with 38 digits of precision.</lang>

DBMS_CRYPTO

The DBMS_CRYPTO package contains basic cryptographic functions and procedures. The DBMS_CRYPTO.RANDOMBYTES function returns a RAW value containing a cryptographically secure pseudo-random sequence of bytes, which can be used to generate random material for encryption keys. This function is based on the RSA X9.31 PRNG (Pseudo-Random Number Generator). <lang PL/SQL>DBMS_CRYPTO.RANDOMBYTES --returns RAW value DBMS_CRYPTO.RANDOMINTEGER --produces integers in the BINARY_INTEGER datatype DBMS_CRYPTO.RANDOMNUMBER --produces integer in the NUMBER datatype in the range of [0..2**128-1]</lang>

PowerShell

The Get-Random cmdlet (part of PowerShell 2) uses the .NET-supplied pseudo-random number generator which uses Knuth's subtractive method; see C#.

PureBasic

PureBasic has two random number generators, Random() and CryptRandom(). Random() uses a RANROT type W generator [7]. CryptRandom() 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 CryptRandom() is uncertain.

Python

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

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.

1. Beta
2. Binomial
3. Cauchy
4. Chi-Squared
5. Exponential
6. F
7. Gamma
8. Geometric
9. Hypergeometric
10. Logistic
11. Log Normal
12. Multinomial
13. Negative Binomial
14. Normal
15. Poisson
16. Student t
17. Uniform
18. Weibull

See R help on Random number generation, or in the R system type <lang R>?RNG help.search("Distribution", package="stats")</lang>

Rascal

Rascal does not have its own arbitrary number generator, but uses the Java generator. Nonetheless, you can redefine the arbitrary number generator if needed. Rascal has the following functions connected to the random number generator: <lang rascal>import util::Math; arbInt(int limit); // generates an arbitrary integer below limit arbRat(int limit, int limit); // generates an arbitrary rational number between the limits arbReal(); // generates an arbitrary real value in the interval [0.0, 1.0] arbSeed(int seed);</lang> The last function can be used to redefine the arbitrary number generator. This function is also used in the getOneFrom() functions. <lang rascal>rascal>import List; ok rascal>getOneFrom(["zebra", "elephant", "snake", "owl"]); str: "owl" </lang>

Ruby

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

Seed7

Seed7 uses a linear congruential generator to compute pseudorandom numbers. Usually random number generators deliver a random value in a fixed range, The Seed7 function rand(low, high) delivers a random number in the requested range [low, high]. Seed7 overloads the rand functions for the types char, boolean, bigInteger, float and others.

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.

TXR

TXR 50 has a PRNG API, and uses a re-implementation of WELL 512 (avoiding contagion by the "contact authors for commercial uses" virus present in the reference implementation, which attacks BSD licenses). Mersenne Twister was a runner up. There is an object of type random-state, and a global variable *random-state* which holds the default random state. Programs can create random states which are snapshots of existing ones, or which are seeded using an integer value (which can be a bignum). The random function produces a random number modulo some integer value, which can have arbitrary precision. The random-fixnum function produces a non-heap-allocated positive integer with random bits.

UNIX Shell

The Bourne shell does not have an inbuilt random number generator, but calls other programs to generate random numbers, so the algorithm is dependent on the called program. Here is an example of awk being used:

<lang sh>number=`awk 'BEGIN{print int(rand()*10+1)}'` # Get a random number</lang>

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.

XPL0

A 31-bit linear congruential generator is used based on an algorithm by Donald Knuth in his book "Art of Computer Programming" Vol 2, 3rd ed. p. 185. It passes all tests in the Diehard suite. The seed is initialized with the system timer count (at 046C) whenever a program starts. The seed can also be set within a program to give a repeatable sequence of (pseudo) random numbers. Calls to the random number intrinsic return values modulo the argument.

<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations int I; [RanSeed(12345); \set random number generator seed to 12345 for I:= 1 to 5 do

       [IntOut(0, Ran(1_000_000));  CrLf(0)];

]</lang>

Output:

905495
181227
755989
244883
213142

ZX Spectrum Basic

The ZX Spectrum uses a pseudorandom number generator that derives its numbers from a set of values stored in the system ROM. The random numbers produced will repeat after 65535 iterations.