Go to the first, previous, next, last section, table of contents.

CNLCG -- Linear Congruence RNG

SYNOPSIS

#include <CNCL/LCG.h>

TYPE

CN_LCG

BASE CLASSES

CNRNG

DERIVED CLASSES

None

RELATED CLASSES

CNRandom

DESCRIPTION

CNLCG is a linear congruence random number generator class. The linear congruential generator is based on the formula

X_n = a * X_n-1 mode m

with multiplier a and modulus m [1]. This generator was first introduced by Lehmer [8]. Up to version 1.7 of the CNCL an LCG with multiplier 65,539=2^16+3 and modulus 2^31=2,147,483,647 was provided. This generator is known as RANDU. It does not have the full possible period of 2^31-2 and it has been shown to be flawed in many respects. Also it does not have good randomness properties [1]. Furthermore the implementation in the CNCL was not correct. The formula was implemented straight forward with unsigned longs, neglecting that the product of two unsigned longs may lead to an overflow. In version 1.8 of the CNCL the RANDU was replaced by a linear congruential generator with a = 16807 and m = 2^31-1 = 2,147,483,647.

This generator provides the full possible period and was highly recommended by Park and Miller [2]. They called it a minimal standard. But be careful, also this generator is not perfect, but it may be used when performance is more important than perfect randomness. The possibility of overflow was taken into account. The algorithm of Schrage [3] was used, which allows the correct implementation of the formula on 32bit-machines. Due to the recommendation of Lewis and Orav [4] there are another five values based on the work of Fishmann and Moore [5] for the multiplier a: 950,706,376; 742,938,285; 1,226,874,159; 62,089,911 and 1,343,714,438. This values were not used in the CNCL, because it is not possible to apply the algorithm of Schrage [3] to them to avoid overflow. Their implementation needs the use of double precision floating points which impairs performance.

Seed selection

Zero is not suitable as a seed for the LCG. So if the user persists to select zero, his choice is mapped to a more useful seed. According to Knuth[1], the seed and the modulus m of an LCG should be relative prime.

Constructors:

CNLCG(unsigned long seed = 929);
CNLCG(CNParam *param);
Initializes CNLCG with initial seed.

In addition to the member functions required by CNCL, CNLCG provides:

virtual unsigned long as_long32();
Draws a random number. The result is an unsigned integer in the range 0 ... 2^31-1.
virtual bool has_long32();
Returns FALSE because LCG produces only 31bit integer values.
virtual void reset();
Resets the CNLCG to its initial state.
void seed(unsigned long);
Sets the CNLCG seed value.

Go to the first, previous, next, last section, table of contents.