[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
delete
s
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
delete
s
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
delete
s
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
delete
s
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
delete
s
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