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.

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

Given sequences for ak = 3, 32, 33, and 34.

We give the result for a = 3: 1, 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15, 14, 11, 2, 6, 18,23, 7, 21, 1.

1)maximum period obtainable for Xn+1 = (aXn) mod 24 is

Maximum period is

24–2 = 4

2) the value of a must be 5 or 11

3). The seed must be odd

Thank you hope this will helps you have a great day.....

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

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