(Fibonacci Shift-Register Random-Number Generator) A wellknown method of generating a

Chapter 10, Problem 3

(choose chapter or problem)

(Fibonacci Shift-Register Random-Number Generator) A wellknown method of generating a sequence of pseudorandom integers x0, x1, x2, x3,... in the interval from 0 to p 1 is based on the following algorithm: (i) Pick any two integers x0 and x1 from the range 0, 1, 2,...,p 1. (ii) Set xn+1 = (xn + xn1) mod p for n = 1, 2,.... Here x mod p denotes the number in the interval from 0 to p 1 that differs from x by a multiple of p. For example, 35 mod 9 = 8 (because 8 = 35 3 9); 36 mod 9 = 0 (because 0 = 36 4 9); and 3 mod 9 = 6 (because 6 = 3 + 1 9). (a) Generate the sequence of pseudorandom numbers that results from the choices p = 15, x0 = 3, and x1 = 7 until the sequence starts repeating. (b) Show that the following formula is equivalent to step (ii) of the algorithm: xn+1 xn+2 = 1 1 1 2 xn1 xn mod p for n = 1, 2, 3,... (c) Use the formula in part (b) to generate the sequence of vectors for the choices p = 21, x0 = 5, and x1 = 5 until the sequence starts repeating. Remark If we take p = 1 and pick x0 and x1 from the interval [0, 1), then the above random-number generator produces pseudorandom numbers in the interval [0, 1). The resulting scheme is precisely Arnolds ct map. Furthermore, if we eliminate the modular arithmetic in the algorithm and take x0 = x1 = 1, then the resulting sequence of integers is the famous Fibonacci sequence, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,..., in which each number after the first two is the sum of the preceding two numbers.