Additive number generator. More...

#include <Random.h>

Inheritance diagram for casa::ACG:

Public Member Functions
	ACG (uInt seed=0, Int size=55)
	The constructor allows you to specify seeds.
virtual	~ACG ()
	The destructor cleans up memory allocated by this class.
virtual void	reset ()
	Resets the random number generator.
virtual uInt	asuInt ()
	Return the 32-random bits as an unsigned integer.
Private Attributes
uInt	itsInitSeed
Int	itsInitTblEntry
uInt *	itsStatePtr
uInt *	itsAuxStatePtr
Short	itsStateSize
Short	itsAuxSize
uInt	lcgRecurr
Short	itsJ
Short	itsK

Detailed Description

Additive number generator.

Intended use:

Public interface

Review Status

Reviewed By:: UNKNOWN
Date Reviewed:: before2004/08/25

Prerequisite

A knowledge of C++, in particular inheritance
College level mathematics

Etymology

ACG stands for "Additive Congruential Generator"

Synopsis

This class implements the additive number generator as presented in Volume II of The Art of Computer Programming by Knuth. I have coded the algorithm and have added the extensions by Andres Nowatzyk of CMU to randomize the result of algorithm M a bit by using an LCG & a spatial permutation table.

The version presented uses the same constants for the LCG that Andres uses (chosen by trial & error). The spatial permutation table is the same size (it is based on word size). This is for 32-bit words.

The auxillary table used by the LCG table varies in size, and is chosen to be the the smallest power of two which is larger than twice the size of the state table.

Class ACG is a variant of a Linear Congruential Generator (Algorithm M) described in Knuth, "Art of Computer Programming, Vol III". This result is permuted with a Fibonacci Additive Congruential Generator to get good independence between samples. This is a very high quality random number generator, although it requires a fair amount of memory for each instance of the generator.

The constructor takes two parameters: the seed and the size. The seed can be any number. The performance of the generator depends on having a distribution of bits through the seed. If you choose a number in the range of 0 to 31, a seed with more bits is chosen. Other values are deterministically modified to give a better distribution of bits. This provides a good random number generator while still allowing a sequence to be repeated given the same initial seed.

The size parameter determines the size of two tables used in the generator. The first table is used in the Additive Generator; see the algorithm in Knuth for more information. In general, this table contains size integers. The default value, used in the algorithm in Knuth, gives a table of 55 integers (220 bytes). The table size affects the period of the generators; smaller values give shorter periods and larger tables give longer periods. The smallest table size is 7 integers, and the longest is 98. The size parameter also determines the size of the table used for the Linear Congruential Generator. This value is chosen implicitly based on the size of the Additive Congruential Generator table. It is two powers of two larger than the power of two that is larger than size. For example, if size is 7, the ACG table contains 7 integers and the LCG table contains 128 integers. Thus, the default size (55) requires 55 + 256 integers, or 1244 bytes. The largest table requires 2440 bytes and the smallest table requires 100 bytes. Applications that require a large number of generators or applications that are not so fussy about the quality of the generator may elect to use the MLCG generator.

Warning: This class assumes that the integer and unsigned integer type is exactly 32 bits long;