8.1 If we take the linear congruential algorithm with an additive component of 0

Question

8.1 If we take the linear congruential algorithm with an additive component of 0,

Xn+1 = (aXn) mod m

Then it can be shown that if m is prime and if a given value of a produces the maximum period of m - 1, then ak will also produce the maximum period, provided that k is less than m and that k and m - 1 are relatively prime. Demonstrate this by using X0 = 1 and m = 31 and producing the sequences for ak = 3, 32, 33, and 34.

8.2
a. What is the maximum period obtainable from the following generator?

Xn+1 = (aXn) mod 24

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

Explanation / Answer

Linear congruential algorithm with additive component of 0:

Xn+1 = aXnmodm

We give result for ak = 3 when x0 = 1, m =31

X0 = 1

X1 = 3 * 1 mod 31 = 3

X2 = 3 * 3 mod 31 = 9

X3 = 27 mod 31 = 27

ð 81 mod31 = 19         

ð 57 mod31 = 26

ð 78 mod31 = 16

ð 48 mod31 = 17

ð 51 mod31 = 20

ð 60 mod31 = 29

ð 87 mod31 = 25

ð 75 mod31 = 13

ð 39 mod31 = 8

ð 24 mod31 = 24

ð 72 mod31 = 10

ð 30 mod31 = 30

ð 90 mod31 = 28

ð 84 mod31 = 22

ð 66 mod31 = 4

ð 12 mod31 = 12

ð 36 mod31 = 5

ð 15 mod31 = 15

ð 45 mod31 = 14

ð 42 mod31 = 11

ð 33 mod31 = 2

ð 6 mod31 = 6

ð 18 mod31 = 18

ð 54 mod31 = 23

ð 69 mod31 = 7

ð 21 mod31 = 21

ð 63 mod31 = 1

NOTE: The longest period (the number of integers before the sequence repeats) P is 30.

When ak =32

X0 = 1

X1 = 32 * 1 mod 31 = 1

Longest period = 1

When ak = 33

X0 = 1

X1 = 33 * 1 mod31 = 2

X2 = 66 mod31 = 4

X3 = 132 mod31 = 8

ð 264 mod31 = 16

ð 528 mod31 = 1

Longest period = 16

When ak = 34

X0 = 1

X1 = 34 * 1 mod31 = 3

X2 = 102 mod31 = 9

X3 = 306 mod31 = 27

ð 918 mod31 = 19

ð 646 mod31 = 26

ð 884 mod31 = 16

ð 544 mod31 = 17

ð 578 mod31 = 20

ð 680 mod31 = 29

ð 986 mod31 = 25

ð 850 mod31 = 13

ð 442 mod31 = 8

ð 272 mod31 = 24

ð 816 mod31 = 10

ð 340 mod31 = 30

ð 1020 mod31 = 28

ð 952 mod31 = 22

ð 748 mod31 = 4

ð 136 mod31 = 12

ð 408 mod31 = 5

ð 170 mod31 = 15

ð 510 mod31 = 14

ð 476 mod31 = 11

ð 374 mod31 = 2

ð 68 mod31 = 6

ð 204 mod31 = 18

ð 612 mod31 = 23

ð 782 mod31 = 7

ð 238 mod31 = 21

ð 714 mod31 = 1

Longest period = 29

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.