C:/Musimathics_local/Musimat/MusimatChapter9/C090703.cpp File Reference

#include "MusimatChapter9.h"

Go to the source code of this file.

Functions
	MusimatChapter9Section (C090703)
Integer	LCRandom ()
Static Void	para1 ()
Variables
Const Integer	a = 16807
Const Integer	b = 0
Const Integer	c = 2147483647
Integer	x = 1

---

Function Documentation

Integer LCRandom

(

)

Definition at line 53 of file C090703.cpp.

References a, b, c, and x.

                  {
        x = Mod(a * x + b, c);                  // update x based on its previous value
        Integer r = x;                                  // x may be positive or negative
        If (r < 0)                                              // force the result to be positive
                r = -r;
        Return(r);
}

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 returns a random 
number by the linear congruential method each time it is called:
*****************************************************************************/
        para1(); // Step into this function to continue.
}

Static Void para1

(

)

Definition at line 62 of file C090703.cpp.

References LCRandom(), and x.

                    {
/*****************************************************************************
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 );
}}

---

Variable Documentation

Const Integer a = 16807

Definition at line 48 of file C090703.cpp.

Const Integer b = 0

Definition at line 49 of file C090703.cpp.

Const Integer c = 2147483647

Definition at line 50 of file C090703.cpp.

Integer x = 1

Definition at line 51 of file C090703.cpp.

---