Previous | Table of Contents | Next |
xn = (25,173xn-1 + 13,849)mod 216
TABLE 26.3 Random Numbers Generated by the LCG: xn = 25,173xn-1 + 13,849 mod 216 | ||
---|---|---|
xn | ||
n | Decimal | Binary |
1 | 25,173 | 01100010 01010101 |
2 | 12,345 | 00110000 00111001 |
3 | 54,509 | 11010100 11101101 |
4 | 27,825 | 01101100 10110001 |
5 | 55,493 | 11011000 11000101 |
6 | 25,449 | 01100011 01101001 |
7 | 13,277 | 00110011 11011101 |
8 | 53,857 | 11010010 01100001 |
9 | 64,565 | 11111100 00110101 |
10 | 1,945 | 00000111 10011001 |
11 | 6,093 | 00010111 11001101 |
12 | 24,849 | 01100001 00010001 |
13 | 48,425 | 11001100 11001001 |
14 | 52,425 | 11001100 11001001 |
15 | 61,629 | 11110000 10111101 |
16 | 18,625 | 01001000 11000001 |
17 | 2,581 | 00001010 00010101 |
18 | 25,337 | 01100010 11111001 |
19 | 11,949 | 00101110 10101101 |
20 | 47,473 | 10111001 01110001 |
Notice the following:
In general, the lth bit follows a cycle of length 2l-2 for l ≠ 2
The cyclic behavior of low-order bits illustrated in Example 26.7 is typical of all LCGs with modulus m = 2k. This is true for both mixed as well as multiplicative LCGs.
For all multiplicative LCGs of the form xn = axn-1 mod 2k, the least significant bit is either always 0 or always 1. The lth bit has a period at most 2l. Here, bits are numbered such that l = 1 is the least significant bit. Similarly, for all mixed LCGs of the form xn = (axn-1 + c)mod 2k, the lth bit has a period at most 2l.
In general, the high-order bits are more randomly distributed than the low-order bits. Thus, if one wants an l-bit sequence, where l is less than the word width of the machine, it is better to take the high-order l bits than the low-order l bits.
xn = axn-1 mod 24
What should be the value of a? What restrictions are required on the seed?
xn = 13xn-1 mod 2311
xn = 40,014xn-1 mod 2,147,483,563
Using a seed of x0 = 1, determine x10,000.
xn = 11xn-1 mod 31
Are the sequences generated the same? If not, explain what is the problem.
xn = 24xn-1 mod 31
Write programs to implement the generator with and without Schrages method and justify your answer.
x6 + x + 1
xn = (40xn-1 + 3641) mod 729
xn = (61xn-1 + 2323) mod 500
xn = 13xn-1 + 11 mod 216
Find the period of the lth bit from the right for l = 1,2,...,5.
Previous | Table of Contents | Next |