[ThinAir Home] [Table of Contents] [Abstract Classes] [Generator Instantiations]

7 Concrete Classes

The classes described in this section are the main reason you would wish to use the ThinAir library. These classes represent a significant fraction of the PRNGs described in the literature.

7.1 LinConRandGen

The LinConRandGen class implements the linear congruential pseudo-random number generator with a constant term. This kind of generator was introduced by D. H. Lehmer in 1949. It is derived from CongruentialRandGen and is implemented in the files randlcon.h and randlcon.cpp. The generator is based on the equation

Xn = (a*Xn-1 + c) mod 232.

The constructor for this class has the following prototype.

LinConRandGen( unsigned long mult, unsigned long incr, size_rand seed )

The mult takes the place of a in the formula and incr is the value of c. The seed is the value of X0 and has a default value of 1.

In addition to the public interface, the LinConRandGen class has a protected interface for use by its derived classes:

unsigned long      Multiplier( void ) const;

Returns the multiplier the generator was created with.

unsigned long      Increment( void ) const;

Returns the increment value the generator was created with.

7.2 LinConModRandGen

Like LinConRandGen, this class implements generators based on the equation

Xn = (a*Xn-1 + c) mod m.

It is derived from LinConRandGen and is implemented in the files rndlconm.h and rndlconm.cpp. This kind of generator was introduced by D. H. Lehmer in 1949. Unlike LinConRandGen, LinConModRandGen generators have a modulus other than 232. The price for this extra flexibility is slower operation. The constructor for this class has the following prototype.

LinConModRandGen( unsigned long mult, unsigned long incr, unsigned long mod, size_rand seed )

The mult takes the place of a in the formula and incr is the value of c. The value of m in the formula is supplied by mod. The seed is the value of X0 and has a default value of 1.

In addition to the public interface, the LinConModRandGen class has a protected interface for use by its derived classes:

unsigned long      Modulus( void ) const;

Returns the modulus the generator was created with.

7.3 MultConRandGen

The MultConRandGen class implements the linear congruential without a constant term. The generator is based on the equation

Xn = (a*Xn-1) mod 232.

This kind of generator was introduced by D. H. Lehmer in 1949. It is derived from CongruentialRandGen and is implemented in the files randmcon.h and randmcon.cpp. The constructor for this class has the following prototype:

MultConRandGen( unsigned long mult, size_rand seed )

Requires only the value of a (supplied by mult) and an initial value for X0 (supplied by seed). If no value is given for seed, a 1 is used.

In addition to the public interface, the MultConRandGen class has a protected interface for use by its derived classes:

unsigned long      Multiplier( void ) const;

Returns the multiplier this generator was created with.

An equivalent generator can be constructed from LinConRandGen by setting the incr term to 0. However, this class provides a small increase in speed by removing the overhead of the increment term.

7.4 MultConModRandGen

Like MultConRandGen, this class implements generators based on the equation

Xn = (a*Xn-1) mod m.

This kind of generator was introduced by D. H. Lehmer in 1949. MultConModRandGen is derived from MultConRandGen and is implemented in the files rndmconm.h and rndmconm.cpp. Unlike MultConRandGen, MultConModRandGen generators have a modulus other than 232. The price for this extra flexibility is slower operation. The constructor for this class has the following prototype:

MultConModRandGen( unsigned long mult, unsigned long mod, size_rand seed )

The value of a (supplied by mult), the modulus m (supplied by mod), and an initial value for X0 (supplied by seed). If no value is given for seed, a 1 is used.

In addition to the public interface, the MultConModRandGen class has a protected interface for use by its derived classes:

unsigned long      Modulus( void ) const;

Returns the modulus the generator was created with.

An equivalent generator can be constructed from LinConModRandGen by setting the incr term to 0. However, this class provides a small increase in speed by removing the overhead of the increment term.

7.5 SecConRandGen

The SecConRandGen class implements a second-order congruential generator. It is derived from CongruentialRandGen and is implemented in the files randsec.h and randsec.cpp. This generator is based on the equation

Xn = (a*Xn-1 + b*Xn-2 + c) mod 232.

The constructor for this class has the following prototype:

SecConRandGen( long multLast, long multCurr, unsigned long incr, size_rand seed )

Uses the values of multCurr and multLast to replace the formula coefficients a and b, respectively. The value of c from the formula is supplied by the argument incr. The argument seed supplies the initial value of X0. The value for X-1 is always 0. The default value for seed is 1.

In addition to the public interface, the SecConRandGen class has a protected interface for use by its derived classes:

size_rand      LastSeed( void ) const;

Returns the previous seed value.

unsugned long      MultLast( void ) const;

Returns the last seed multiplier. (The constant b from the formula above.)

unsigned long      MultCurr( void ) const;

Returns the current seed multiplier. (The constant a from the formula above.)

unsigned long      Increment( void ) const;

Returns the increment value the generator was created with. (The constant c from the formula above.)

void      SetLastSeed( size_rand seed );

Sets the last seed value that the generator uses in creating the next random number.

7.6 SecConModRandGen

Like SecConRandGen, this class implements generators based on the equation

Xn = (a*Xn-1 + b*Xn-2 + c) mod m.

It is derived from SecConRandGen and is implemented in the files randsecm.h and randsecm.cpp. Unlike SecConRandGen, SecConModRandGen generators have a modulus other than 232. The price for this extra flexibility is slower operation. The constructor for this class has the following prototype:

SecConModRandGen( long multLast, long multCurr, unsigned long incr, unsigned long mod, size_rand seed )

Uses the values of multCurr and multLast to replace the formula coefficients a and b, respectively. The value of c from the formula is supplied by the argument incr. The argument mod supplies the modulus, m, for the formula above. The argument seed supplies the initial value of X0. The value for X-1 is always 0. The default value for seed is 1.

In addition to the public interface, the SecConModRandGen class has a protected interface for use by its derived classes:

unsigned long      Modulus( void ) const;

Returns the modulus the generator was created with.

7.7 InvConModRandGen

This class implements the Inverse Congruential PRNG described by Andreas Weingartner in his 1994 Masters thesis, [10]. The class implements generators based on the equation

Xn = (a*Xn-1 + b) mod m.

Where X is the inverse of X in the modulus field m. It is derived from CongruentialRandGen and is implemented in the files randicon.h and randicon.cpp. The algorithm works best if this modulus is a prime number. An absolute minimum requirement is that the modulus is not even. The constructor for this class has the following prototype:

InvConModRandGen( unsigned long mult, unsigned long incr, unsigned long mod, size_rand seed )

The mult takes the place of a in the formula and incr is the value of b. The value of m in the formula is supplied by mod. The seed is the value of X0 and has a default value of 1.

In addition to the public interface, the InvConModRandGen class has a protected interface for use by its derived classes:

unsigned long      Multiplier( void ) const;

Returns the multiplier the generator was created with.

unsigned long      Increment( void ) const;

Returns the increment value the generator was created with.

unsigned long      Modulus( void ) const;

Returns the modulus the generator was created with.

unsigned long      InvertSeed( void );

Returns the result of inverting the current seed in the 232-1 modulus field.

7.8 InvConRandGen

This class implements the Inverse Congruential PRNG described by Andreas Weingartner in his 1994 Masters thesis, [10]. It is derived from InvConRandGen and is implemented in the files randicon.h and randicon.cpp. This generator is based on the equation

Xn = (a*Xn-1 + b) mod (232-5).

Where X is the inverse of X in the modulus field 232-5. The modulus chosen is the largest prime number less than 232, according to [4, page 390]. The constructor for this class has the following prototype:

InvConRandGen( unsigned long mult, unsigned long incr, size_rand seed )

The mult takes the place of a in the formula and incr is the value of b. The seed is the value of X0 and has a default value of 1.

7.9 QuadConRandGen

This class implements the Quadratic Congruential PRNG. This generator is really not much better than the LinConRandGen PRNG described above. This PRNG is discussed in [10]. The main reason I included this class was to show how a new generator may be derived from another class in Section 13.5 below. This class is derived from CongruentialRandGen and is implemented in the files randquad.h and randquad.cpp. This generator is based on the equation

Xn = (a*{{X}n-1}2 + b*{X}n-1 + c) mod 232.

The constructor for this class has the following prototype:

QuadConRandGen( unsigned long quad, unsigned long lin, unsigned long incr, size_rand seed )

The quad replaces the place of a in the formula, lin replaces b, and incr is the value of c. The seed is the value of X0 and has a default value of 1.

In addition to the public interface, the QuadConRandGen class has a protected interface for use by its derived classes:

unsigned long      QuadMultiplier( void ) const;

Returns the coefficient for the second-order term the generator was created with.

unsigned long      LinMultiplier( void ) const;

Returns the coefficient for the linear term the generator was created with.

unsigned long      Increment( void ) const;

Returns the increment value the generator was created with.

7.10 NumberTableRandGen

The NumberTableRandGen class reads numbers from a file-based table containing whitespace separated numbers in an ASCII-format. Any source of numbers that can write a file filled with numeric strings can build tables for this class. The table begins after a line containing the phrase Begin Table. The NumberTableRandGen class is derived from TextTableRandGen and is implemented in the files randntbl.h and randntbl.cpp. The constructor for this class has the following prototype:

explicit NumberTableRandGen( const char *szFileName, streampos start )

Calls the constructor for TextTableRandGen with the arguments szFileName and start. The start argument has a default value of 0.

7.11 BinaryTableRandGen

This class defines an interface for generators that read a sequence of numbers from a binary table on disk. It is derived from TableRandGen and is implemented in the files randtabl.h and randtabl.cpp. The BinaryTableRandGen class makes only one assumption about the file. The file is assumed to be a list of 4-byte binary numbers with no formatting. The constructor for this class has the following prototype:

explicit BinaryTableRandGen( const char *szFileName, streampos start )

Calls the constructor for TableRandGen with the arguments szFileName and start. The start argument has a default value of 0.

7.12 DecimalTableRandGen

The DecimalTableRandGen class is derived from ByteTableRandGen. The file it uses must contain a list of ASCII digits. Only the characters `0' - `9' are considered significant in the file. The table begins after a line containing the phrase Begin Table. The DecimalTableRandGen combines the digits into a random number as needed. The DecimalTableRandGen class is implemented in the files randbtbl.h and randbtbl.cpp. The constructor for this class has the following prototype:

explicit DecimalTableRandGen( const char *szFileName, streampos start )

Calls the constructor for ByteTableRandGen with the arguments szFileName and start. The start argument has a default value of 0.

In addition to the public interface, the DecimalTableRandGen class has a protected interface for use by its derived classes:

size_rand      getNumber( unsigned digits );

Reads digits bytes from the table and constructs a number from these bytes.

unsigned      getNumberDigits( size_rand limit );

Returns the number of digits needed to produce a number the size of limit.

7.13 HexTableRandGen

The HexTableRandGen class is derived from ByteTableRandGen. The file it uses must contain a list of hexadecimal digits. Only the characters `0' - `9', `a' - `f', and `A' - `F' are considered significant in the file. The table begins after a line containing the phrase Begin Table. The HexTableRandGen combines the hexadecimal digits into a random number as needed. The HexTableRandGen class is implemented in the files randbtbl.h and randbtbl.cpp. The constructor for this class has the following prototype:

explicit HexTableRandGen( const char *szFileName, streampos start )

Calls the constructor for ByteTableRandGen with the arguments szFileName and start. The start argument has a default value of 0.

In addition to the public interface, the HexTableRandGen class has a protected interface for use by its derived classes:

size_rand      getNumber( unsigned digits );

Reads digits bytes from the table and constructs a number from these bytes.

unsigned      getNumberDigits( size_rand limit );

Returns the number of digits needed to produce a number the size of limit.

7.14 DifferenceRandGen

A DifferenceRandGen object is constructed with pointers to two other PRNG objects. The number sequence generated by the DifferenceRandGen object are formed by subtracting the result of one of the generators (pGenY) from the result of the other (pGenX). The DifferenceRandGen class is derived from CombineRandGen and is implemented in the files randdiff.h and randdiff.cpp. The constructor for this class has the following prototype:

DifferenceRandGen( RandomGenerator *pGenX, RandomGenerator *pGenY )

Requires pointers to two heap-based PRNG objects. The DifferenceRandGen object owns these PRNGs and deletes them when the object is destroyed.

7.15 ShuffledMRandGen

cmt{Verify: probably need to implement algorithm B as an Adaptor.} The ShuffledMRandGen class implements the shuffling algorithm described in Algorithm M, [4, Section 3.2.2]. This generator was prposed by M. D. MacLaren and G. Marsaglia in 1968. One generator (pGenX) is used to fill an array with numbers. A second generator (pGenY) selects which entry is used as output. Then, we use the first generator to reset the array entry to a new value. It is derived from CombineRandGen. The ShuffledMRandGen class is implemented in the files randshuf.h and randshuf.cpp. The constructor for this class has the following prototype:

ShuffledMRandGen( unsigned size, RandomGenerator *pGenX, RandomGenerator *pGenY )

Requires pointers to two heap-based PRNG objects. The ShuffledMRandGen object owns these PRNGs and deletes them when the object is destroyed. The ShuffledMRandGen object also needs a size value used to define the internal array.

7.16 A15BitRandGen

The A15BitRandGen class is derived from AdaptorRandGen. This generator provides a method of converting the output of a 32-bit generator into a 15-bit generator. PRNGs built for 16-bit architectures often limit their output to 15-bits. Two examples of this kind of generator are the BorlandRandGen and StdCRandGen classes. The A15BitRandGen generator is implemented in randadpt.h. The constructor for this class has the following prototype:

A15BitRandGen( RandomGenerator *pGen )

Requires a pointer to a heap-based PRNG object. The A15BitRandGen object owns this PRNG and deletes it when the object is destroyed.

7.17 LaggedFibonacciRandGen

The LaggedFibonacciRandGen implements a class of generators described in [4, page 26] and [6]. These generators implement the equation

Xn = (Xn-u + Xn-l) mod 232.

Research has shown that with proper choices of u and l, the period of the least significant bits of the output of this generator can be 2u-1. (for u > l) This guarantees a period for the generator of at least this long. The only reported problem involves a birthday spacings test for small values of l and u. The LaggedFibonacciRandGen class is derived from RandomGenerator and is implemented in the files randlfib.cpp and randlfib.h. The constructor for this class has the following prototype:

LaggedFibonacciRandGen( unsigned lower, unsigned upper, RandomGenerator *pRng )

Requires a pointer to a heap-based PRNG object. The LaggedFibonacciRandGen object owns this PRNG and deletes it when the object is destroyed. The LaggedFibonacciRandGen object also needs a lower and upper offset into the past data to define which old data contributes to the new value. The upper limit also determines how large a buffer to allocate for past state.

In addition to the public interface, the LaggedFibonacciRandGen class has a protected interface for use by its derived classes:

unsigned      UpperTap() const;

Returns the value of the upper tap into the past data buffer.

unsigned      LowerTap() const;

Returns the value of the lower tap into the past data buffer.

size_rand      LowValue() const;

Returns the value of the current low position in the past data buffer.

size_rand      HighValue() const;

Returns the value of the current high position in the past data buffer.

RandomGenerator      *Initializer() const;

Returns a pointer to the PRNG object used to initialize the past data buffer.

void      SetNewElement( size_rand val );

Sets the new element the past data buffer to val.

void      InitArray( void );

Initialize the past data buffer using the PRNG supplied at constructor time.

void      InitTaps( void );

Initialize the current taps to their initial values.

void      IncrTaps( void );

Move the current taps to their next location.

7.18 LaggedFibonacciModRandGen

The LaggedFibonacciRandGen implements a class of generators described in [4, page 26] and [6]. These generators implement the equation

Xn = (Xn-u + Xn-l) mod m.

The only difference between this class and the LaggedFibonacciRandGen class is the modulus m. This modulus makes the generator more flexible, but also slows it down. The LaggedFibonacciModRandGen class is derived from LaggedFibonacciRandGen and is implemented in the files rndlfibm.cpp and rndlfibm.h. The constructor for this class has the following prototype:

LaggedFibonacciModRandGen( unsigned lower, unsigned upper, unsigned long mod, RandomGenerator *pRng )

Requires a pointer to a heap-based PRNG object. The LaggedFibonacciModRandGen object owns this PRNG and deletes it when the object is destroyed. The LaggedFibonacciModRandGen object also needs a lower and upper offset into the past data to define which old data contributes to the new value. The upper limit also determines how large a buffer to allocate for past state. The mod parameter defines the modulus used in the calculations.

In addition to the public interface, the LaggedFibonacciModRandGen class has a protected interface for use by its derived classes:

unsigned long      Modulus( void ) const;

Returns the modulus the generator was created with.

7.19 LinMultWCarryRandGen

The LinMultWCarryRandGen class implements a special case of Marsaglia's multiply with carry PRNG. The class is derived from CongruentialRandGen and is implemented in the files randlmwc.h and randlmwc.cpp. The generator is based on the equation

Xn = (a*Xn-1 + cn-1) mod 232.

Unlike the linear congruential PRNG, the increment term in this equation changes as the algorithm progresses. This term is generated by the carry or quotient resulting from the dividing a*Xn-1 + cn-1 by the modulus. The constructor for this class has the following prototype.

LinMultWCarryRandGen( unsigned long mult, size_rand carry, size_rand seed )

The mult takes the place of a in the formula. The initial value of c in the formula is supplied by carry and has a default value of 0. The seed is the value of X0 and has a default value of 1.

In addition to the public interface, the LinMultWCarryRandGen class has a protected interface for use by its derived classes:

size_rand      Multiplier( void ) const;

Returns the multiplier the generator was created with.

size_rand      Carry( void ) const;

Returns the carry the generator was created with.

size_rand      CurrCarry( void ) const;

Returns the carry generated by in the last operation.

void      SetCarry( size_rand carry );

Resets the carry the generator was created with.

void      SetCurrCarry( size_rand carry );

Resets the carry value for the generator.


For further information, contact G. Wade Johnson (gwadej@anomaly.org).

© 1997 G. Wade Johnson. All rights reserved.
http://www.anomaly.org/ThinAir/concrete.html