- #1

- 8

- 0

This is my first question here. I tried my best to work out it by myself but it didn't work.

I'm reading

I don't know how to deduce Eq.(7-2) on page 299 of this book. There are some paragraphs on this page as below.

Eq.(7-1) is Xn+1 = (a×Xn+c) mod m

It will be appreciated if you can offer some reference books that explain it clearly or give your descriptions here.

Thank you very much!

I'm so sorry I failed to upload the picture of my book. I will try some more times.

Some previous charpters are as follows

Xn+1 = (a×Xn + c) mod m ------------------ (7-1)

where the modulus, m, is a positive integer. The multiplier a and increment c are also positive integers but their values must be less than m. To start off the sequence of random integers X0, X1, X2,…, we need to input an integer m, generally referred to as the seed of the random sequence.

The spirit of Eq.(7-1) is very similar to that behind the system-clock and middle-square methods discussed above. Instead of taking the square, the seed is multiplied by an integer a, and to prevent a bad sequence from developing, an increment c is added to the product. Similar to the system-clock approach, only the least significant part of the sum (less than m) is retained through the modulus operation.

The quality of random integers generated by the linear congruence method depends critically on the values of m, a, and c selected. Because of the modulus operation, all the random integers produced by this method must be in the range [0,m-1]. For this reason, we want m to be as large as possible. On the other hand, m^2 cannot be larger than the longest integer the computer can store in its memory. It is also clear that the choices of these three quantities are related with each other. For example, in order to have a long period, it is known that

(1) c must be relative prime to m (a and m share no common factors other than 1).

(2) (a - 1) is a multiple of p, if p is a prime factor of m, and

(3) (a - 1) is a multiple of 4, if m is a multiple of 4.

For example, a possible set of values for computers with word length of 32 bits is

m = 714,025 a = 1,366 c = 150,889.

The maximum number of different random numbers that can be generated is 714,205 in this case. Other possible combinations of three integers are given in Press and coauthors[44] and detailed discussions of the considerations that must go into the choices are given in Knuth.[31]

Rn = Xn/m.

…

I'm reading

*Computational Methods in Physics and Engineering*by Samuel S M Wong recently.I don't know how to deduce Eq.(7-2) on page 299 of this book. There are some paragraphs on this page as below.

Because of the wide range of applications of random numbers, computer operating systems and high-level languages are usually equipped with random number generators. A slight variant of Eq.(7-1) is often found on 32-bit machines,

Xn+1=[(a×Xn+c)/d] mod m ------------------------------------ (7-2) //n & n+1 are the subscripts of X

with

m = 32,768 a = 1,103,515,245 c= 12,345 d = 65,536.

The range of random integers generated by this method is 0 < Xn < 2^15. There is, however, a small problem if we wish to implement Eq. (7-2) using a language such as Fortran. Since the integer a is larger than 2^30, there is a high probability that an overflow will take place on a 32-bit word length computer when it is multiplied by a random integer Xn. To avoid the problem this portion of code can be written in a different language such as C in a way that it may be called by a Fortran program.

Xn+1=[(a×Xn+c)/d] mod m ------------------------------------ (7-2) //n & n+1 are the subscripts of X

with

m = 32,768 a = 1,103,515,245 c= 12,345 d = 65,536.

The range of random integers generated by this method is 0 < Xn < 2^15. There is, however, a small problem if we wish to implement Eq. (7-2) using a language such as Fortran. Since the integer a is larger than 2^30, there is a high probability that an overflow will take place on a 32-bit word length computer when it is multiplied by a random integer Xn. To avoid the problem this portion of code can be written in a different language such as C in a way that it may be called by a Fortran program.

Eq.(7-1) is Xn+1 = (a×Xn+c) mod m

It will be appreciated if you can offer some reference books that explain it clearly or give your descriptions here.

Thank you very much!

I'm so sorry I failed to upload the picture of my book. I will try some more times.

Some previous charpters are as follows

**The linear congruence method**The most popular way to generate random integers with a uniform distribution is the linear congruence method. In this approach, a random integer Xn+1 is produced from another one Xn through the operation

Xn+1 = (a×Xn + c) mod m ------------------ (7-1)

where the modulus, m, is a positive integer. The multiplier a and increment c are also positive integers but their values must be less than m. To start off the sequence of random integers X0, X1, X2,…, we need to input an integer m, generally referred to as the seed of the random sequence.

The spirit of Eq.(7-1) is very similar to that behind the system-clock and middle-square methods discussed above. Instead of taking the square, the seed is multiplied by an integer a, and to prevent a bad sequence from developing, an increment c is added to the product. Similar to the system-clock approach, only the least significant part of the sum (less than m) is retained through the modulus operation.

The quality of random integers generated by the linear congruence method depends critically on the values of m, a, and c selected. Because of the modulus operation, all the random integers produced by this method must be in the range [0,m-1]. For this reason, we want m to be as large as possible. On the other hand, m^2 cannot be larger than the longest integer the computer can store in its memory. It is also clear that the choices of these three quantities are related with each other. For example, in order to have a long period, it is known that

(1) c must be relative prime to m (a and m share no common factors other than 1).

(2) (a - 1) is a multiple of p, if p is a prime factor of m, and

(3) (a - 1) is a multiple of 4, if m is a multiple of 4.

For example, a possible set of values for computers with word length of 32 bits is

m = 714,025 a = 1,366 c = 150,889.

The maximum number of different random numbers that can be generated is 714,205 in this case. Other possible combinations of three integers are given in Press and coauthors[44] and detailed discussions of the considerations that must go into the choices are given in Knuth.[31]

**Conversion to random numbers**If instead of random integers we wish to have random (floating) numbers, we can convert an integer Xn in the interval [0, m] to a floating number Rn in interval [a, b]. For most generators, the interval is taken to be [0,1]. If the largest integer produced by the linear congruence method of Eq. (7-1) is m, any random integer Xn may be converted to a random number in the interval [0,1] by dividing Xn with m. To carry out this procedure on a computer, we must first change both Xn and m into floating numbers and then take the quotient

Rn = Xn/m.

…

Last edited: