Previous Table of Contents Next


Example 26.7 Consider the generator

xn = (25,173xn-1 + 13,849)mod 216

Starting with a seed of x0 = 1, the first 20 numbers and their binary representations are listed in Table 26.3.
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:

(a)  Bit 1 (the least significant bit) is always 1.
(b)  Bit 2 is always 0.
(c)  Bit 3 alternates between 1 and 0; thus, it has a cycle of length 2.
(d)  Bit 4 follows a cycle (0110) of length 4.
(e)  Bit 5 follows a cycle (11010010) of length 8.

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.

EXERCISES

26.1  What is the maximum period obtainable from the following generator:

xn = axn-1 mod 24

What should be the value of a? What restrictions are required on the seed?

26.2  Determine 24n mod 31 for n = 1,...,30. Find the smallest n for which the mod operation’s result is 1. Is 24 a primitive root of 31?
26.3  Determine all primitive roots of 11.
26.4  Compute the period of the following generator:

xn = 13xn-1 mod 2311

26.5  Implement the following LCG using Schrage’s method to avoid overflow:

xn = 40,014xn-1 mod 2,147,483,563

Using a seed of x0 = 1, determine x10,000.

26.6  Implement the following LCG with and without the Schrage’s method:

xn = 11xn-1 mod 31

Are the sequences generated the same? If not, explain what is the problem.

26.7  Can you implement the following LCG using Schrage’s method?

xn = 24xn-1 mod 31

Write programs to implement the generator with and without Schrage’s method and justify your answer.

26.8  Determine which of the following polynomials is a primitive polynomial:
a. x2 + x + 1
b. x3 + x2 + 1
c. x4 + x2 + 1
d. x5 + x2 + 1
26.9  Determine the period of the Tausworthe sequence generated using each of the following characteristic polynomials:
a. x5 + x + 1
b. x6 + x3 + 1
c. x8 + x + 1
d. x30 + x15 + 1
26.10  Generate five 6-bit numbers using the Tausworthe method for the following characteristic polynomial starting with a seed of x0 = 0.1111112:

x6 + x + 1

26.11  What is wrong with the parameters of the following two generators?

xn = (40xn-1 + 3641) mod 729

xn = (61xn-1 + 2323) mod 500

26.12  Generate 48 random numbers using a seed of x0= 1 in the following mixed LCG:

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

Copyright © John Wiley & Sons, Inc.