#include "MusimatChapter9.h"Go to the source code of this file.
Functions | |
| MusimatChapter9Section (C090703) | |
| Integer | lcRandom () |
| Static Void | para1 () |
Variables | |
| Const Integer | lc_a = 16807 |
| Const Integer | lc_b = 0 |
| Const Integer | lc_c = 2147483647 |
| Integer | lc_x = 1 |
| Integer lcRandom | ( | ) |
| MusimatChapter9Section | ( | C090703 | ) |
Definition at line 2 of file C090703.cpp.
References para1().
{
Print("*** 9.7.3 Linear Congruential Method ***");
/*****************************************************************************
9.7.3 Linear Congruential Method
Equation (9.1) shows the linear congruential method for generating random numbers,
introduced by D. H. Lehmer in 1948 (Knuth 1973, vol. 2):
x[n+1] = ((ax[n]+b))c, n>=0. (9.1)
The notation ((x))n means "x is reduced modulo n." The result is the remainder
after integer division of x by n (see appendix A).
Equation (9.1) is a recurrence relation because the result of the previous step
(x[n]) is used to calculate a subsequent step (x[n+1]). It is linear because the
ax + b part of the equation describes a straight line that intersects the y-axis
at offset b with slope a. Congruence is a condition of equivalence between two
integers modulo some other integer, and refers here simply to the fact that
modulo arithmetic is being used.
For successive computations of x, the output will grow until it reaches the value c.
When c is exceeded, the new value of x is effectively reset to x - c by the modulus operation.
A new slope will grow from this point, and this process repeats endlessly.
The result can be quite predictable depending upon the values of a, b, c, and x[0],
the initial value of x.
For instance, if a = b = x[0] = 1, and c = infinity, an ascending straight line at a 45 degree
slope is produced. However, for other values, the numbers generated can appear random.
In practice, the modulus c should be as large as possible in order to produce long
random sequences. On a computer, the ultimate limit of c is the arithmetic precision
of that machine. For example, if the computer uses 16-bit arithmetic, random numbers
generated by this method can have at most a period of 2^16 = 65,536 values before
the pattern repeats.
The quality of randomness within a period varies depending on the values chosen
for a, x, and b. Much heavy-duty mathematics has been expended choosing good
values (Knuth 1973, vol. 2). For 32-bit arithmetic, Park and Miller (1988) recommend
a = 16,807, b = 0, and c = 2,147,483,647.
The linear congruential method is appealing because once a good set of the parameters is
found, it is very easy to program on a computer. The lcRandom() method shown below returns a random
number by the linear congruential method each time it is called. lcRandom() is a
copy of the Musimat LCRandom() routine in Random.cpp reproduced here for
didactic reasons (to keep things simple).
*****************************************************************************/
para1(); // Step into this function to continue.
}
| Static Void para1 | ( | ) |
Definition at line 64 of file C090703.cpp.
References lcRandom().
{
/*****************************************************************************
The parameters a, b, and c are constant (time-invariant) system parameters.
Parameter x is initialized in this example to 1, but it can be initialized
to any other integer. The value of a * x + b is calculated, the remainder
is found modulo c, and the result is reassigned to x.
While the value of x is less than c, x grows linearly. When the expression
a * x + b eventually produces a value beyond the range of c, then x is reduced
modulo c. The random effect of this method comes from the surprisingly unpredictable
sequence of remainders generated by the modulus operation, depending upon careful
choice of parameters.
The calculation of x ranges over all possible positive and negative integers
smaller than the value of ąc. But it is generally preferable to constrain its
choices to a range. To make this conversion easier, we force the result to be a
positive integer.
Below is a sample invocation of LCRandom().
*****************************************************************************/
Print("*** Ten invocations of LCRandom() ***");
IntegerList x;
For (Integer i = 0; i < 10; i++ ) {
x[i] = lcRandom();
}
Print( x );
}
| Const Integer lc_a = 16807 |
Definition at line 50 of file C090703.cpp.
| Const Integer lc_b = 0 |
Definition at line 51 of file C090703.cpp.
| Const Integer lc_c = 2147483647 |
Definition at line 52 of file C090703.cpp.
| Integer lc_x = 1 |
Definition at line 53 of file C090703.cpp.
1.7.2