User's Guide:Details:Generators

Generators

1. Combined Multiple Recursive Generator

This generator is defined by the following relation:

z(n) = x(n) + y(n)*2³² (Mod 2⁶⁴)

where x(n) is the sequence generated by the 64 bit Linear Congruential Generator and y(n) is the sequence generated by the following prime modulus Multiple Recursive Generator:

y(n) = 107374182*y(n-1) + 104480*y(n-5) (mod 2147483647)

The same prime modulus generator is used for all the streams. Streams differ due to differences in the 64 bit LCG.

The period of this generator is around 2²¹⁹. The number of distinct streams available is over 10⁸.

The multiplier a for the 64 bit LCG is a parameter to this generator and can be set during initialization.

When a call to isprng is made, the 31 high order bits of z(n) are returned. When a call to sprng is made, the result obtained is z(n)/2⁶⁴.

2. 48 Bit Linear Congruential Generator with Prime Addend

The recurrence relation for the sequence of random numbers produced by this generator is given by the following recurrence:

x(n) = a x(n-1) + p (Mod M)

where x(n) is the n th term in the sequence, p is a prime number and a is the multiplier. The value of M for this generator is 2⁴⁸.

Different random number streams are obtained by choosing different prime numbers as the addend p. There are theoretical results by Percus and Kalos which suggest that such a choice will yield reasonably independent streams. We have tested this generator empirically too.

The period of this generator is 2⁴⁸. The number of distinct streams available is of the order of 2¹⁹. However, it is possible to exhaust the set of distinct streams quite fast if the user spawns streams too often. The distinct streams provided are more independent, as per the theoretical analysis mentioned above, if the addends are large prime numbers. Thus we provide streams with primes taken from the the high end of the range during initialization.

The multiplier a is a parameter to this generator and can be set during initialization.

When a call to isprng is made, the 31 high order bits of x(n) are returned. When a call to sprng is made, the result obtained is x(n)/M.

Initialization with different seeds starts the generator at different points in the sequence.

Note: The low order bits of this sequence have a small period. Therefore, if users utilizes certain bits of the sequence in order to take certain decisions in their algorithm, they should avoid using the low order bits.

This generator also has correlations between elements of the sequence separated by powers of two. So users should avoid using numbers n at a time where n is a power of two (such as 1024).

3. 64 Bit Linear Congruential Generator with Prime Addend

The features of this generator are similar to the 48 bit Linear Congruential Generator, except that the arithmetic is modulo 2⁶⁴. The multipliers and prime addends p for this generator are different from those for the 48 bit generator.

The period of this generator is 2⁶⁴. The number of distinct streams available is over 10⁸.

4. Modified Lagged Fibonacci Generator

The recurrence relation for this sequence of random numbers is given by the following equation:

z(n) = x(n) XOR y(n)

where XOR is the exclusive-or operator, x and y are sequences obtained from Lagged Fibonacci sequences X and Y of the following form:

X(n) = X(n-k) + X(n-l) (mod M)
Y(n) = Y(n-k) + Y(n-l) (mod M)

l and k are called the lags of the generator, and we use the convention that l > k. M is chosen to be 2³². X(n) and Y(n) are 32 bit integers. x is obtained from X by setting the Least Significant Bit of the latter to 0. y is obtained from Y by shifting the latter right by one bit. This modification of the Lagged Fibonacci Generator is performed in order to avoid certain correlations that are observed in the unmodified generator.

When a call to isprng is made, the 31 high order bits of z(n) are returned. When a call to sprng is made, the result obtained is z(n)/M.

The period of this generator is 2³¹(2^l-1) where l is the lag. For the default generator with lag l = 1279, the period is approximately 2¹³¹⁰. The number of distinct streams available is 2^[31(l-1)-1]. For the default generator this gives 2³⁹⁶⁴⁸ distinct streams. However, users should still be cautious while spawning new streams, since it is possible to exhaust the set of distinct streams even without using all of them if they spawn often from only a few of the original streams.

The sequence obtained is determined by the l initial values of the sequences X and Y. The seed used during initialization for this generator does not move one to a different point in the sequence. Rather, it returns a different sequence. The seeding algorithms ensures that if the same seed is used for all the streams, then the streams obtained are independent. If a user initializes different streams with different seeds, then it is possible that the same sequence may be assigned to two different streams and hence we may no longer have independent streams. Thus it is important to use the same seed while initializing all the streams with this generator. Test results for this generator's quality are also available.

The parameters to this generator are the values of the lags. More details on this generator and the seeding algorithms can be found papers by Mascagni, et al.

5. Multiplicative Lagged Fibonacci Generator

The recurrence relation for this sequence of random numbers is given by the following equation:

x(n) = x(n-k) * x(n-l) (mod M)

l and k are called the lags of the generator, and we use the convention that l > k. M is chosen to be 2⁶⁴.

When a call to isprng is made, the 31 high order bits of x(n) are returned. When a call to sprng is made, the result obtained is x(n)/M.

The period of this generator is 2⁶¹(2^l-1) where l is the lag. For the default generator with lag l = 17, the period is approximately 2⁸¹. The number of distinct streams available is 2^[63(l-1)-1]. For the default generator this gives around 2¹⁰⁰⁸ distinct streams. However, users should still be cautious while spawning new streams, since it is possible to exhaust the set of distinct streams even without using all of them if they spawn often from only a few of the original streams.

The sequence obtained is determined by the l initial values of the sequence x. The seed used during initialization for this generator does not move one to a different point in the sequence. Rather, it returns a different sequence. The seeding algorithms ensures that if the same seed is used for all the streams, then the streams obtained are independent. If a user initializes different streams with different seeds, then it is possible that the same sequence may be assigned to two different streams and hence we may no longer have independent streams. Thus it is important to use the same seed while initializing all the streams with this generator. Test results for this generator's quality are also available.

The parameters to this generator are the values of the lags. More details on this generator and the seeding algorithm will be given shortly.

6. Prime Modulus Linear Congruential Generator

This generator is defined by the following relation:

x(n) = a*x(n-1) (mod 2⁶¹-1)

where the multiplier a differs for each stream. The mulitpler is chosen to be certain powers of 37 that give maximal period cycles of acceptable quality. The only acceptable parameter to this generator during initialization is the value SPRNG_DEFAULT.

The period of this generator is 2⁶¹-2. The number of distinct streams available is roughly 2⁵⁸.