## Generators

## 1. Combined Multiple Recursive Generator

This generator is defined by the following relation:

z(n) = x(n) + y(n)*2^{32}(Mod 2^{64})

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

periodof this generator is around2. The^{219}number of distinct streamsavailable is over10.^{8}The multiplier

afor the 64 bit LCG is a parameter to this generator and can be set duringinitialization.When a call to

isprngis made, the 31 high order bits ofz(n)are returned. When a call tosprngis made, the result obtained isz(n)/2.^{64}## 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 thenth term in the sequence,pis a prime number andais the multiplier. The value ofMfor this generator is 2^{48}.Different random number

streamsare obtained by choosing different prime numbers as the addendp. There are theoretical results by Percus and Kalos which suggest that such a choice will yield reasonablyindependentstreams. We have tested this generator empirically too.The

periodof this generator is2. The^{48}number of distinct streamsavailable is of the order of2. 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.^{19}The multiplier

ais a parameter to this generator and can be set duringinitialization.When a call to

isprngis made, the 31 high order bits ofx(n)are returned. When a call tosprngis made, the result obtained isx(n)/M.Initialization with different

seedsstarts 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

^{64}. The multipliers and prime addendspfor this generator are different from those for the 48 bit generator.The

periodof this generator is2. The^{64}number of distinct streamsavailable is over10.^{8}## 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

XORis theexclusive-oroperator,xandyare sequences obtained from Lagged Fibonacci sequencesXandYof the following form:

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

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

landkare called the lags of the generator, and we use the convention thatl > k. M is chosen to be 2^{32}.X(n)andY(n)are 32 bit integers.xis obtained fromXby setting the Least Significant Bit of the latter to0.yis obtained fromYby 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

isprngis made, the 31 high order bits ofz(n)are returned. When a call tosprngis made, the result obtained isz(n)/M.The

periodof this generator is2where^{31}(2^{l}-1)lis the lag. For the default generator with lagl = 1279, the period is approximately2. The^{1310}number of distinct streamsavailable is2. For the default generator this gives^{[31(l-1)-1]}2distinct 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.^{39617}The sequence obtained is determined by the

linitial values of the sequencesXandY. Theseedused duringinitializationfor 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 thestreams, then the streams obtained areindependent. 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'squalityare 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)

landkare called the lags of the generator, and we use the convention thatl > k. M is chosen to be 2^{64}.When a call to

isprngis made, the 31 high order bits ofx(n)are returned. When a call tosprngis made, the result obtained isx(n)/M.The

periodof this generator is2where^{61}(2^{l}-1)lis the lag. For the default generator with lagl = 17, the period is approximately2. The^{81}number of distinct streamsavailable is2. For the default generator this gives around^{[63(l-1)-1]}2distinct 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.^{1008}The sequence obtained is determined by the

linitial values of the sequencex. Theseedused duringinitializationfor 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 thestreams, then the streams obtained areindependent. 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'squalityare 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^{61}-1)

where the multiplieradiffers 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 duringinitializationis the valueSPRNG_DEFAULT.The

periodof this generator is2. The^{61}-2number of distinct streamsavailable is roughly 2^{58}.This generator is not installed automatically while installing SPRNG. In order to install it, please first install the GNU multiprecision arithmetic library

libgmp.ain the same location as other SPRNG libraries. Then please change directory tosprng/SRC/pmlcgand typemake.