Functions | Variables

/Users/garethloy/Musimathics/Musimat1.2/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 lc_a = 16807
Const Integer lc_b = 0
Const Integer lc_c = 2147483647
Integer lc_x = 1

Function Documentation

Integer lcRandom (  )

Definition at line 55 of file C090703.cpp.

References lc_a, lc_b, lc_c, and lc_x.

                  {
        lc_x = Mod(lc_a * lc_x + lc_b, lc_c);   // update x based on its previous value
        Integer r = lc_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 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 );
}

Variable Documentation

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.