Random Number Generation Formulas?

True or false (justify your answer):

For all values of A, M, and X_i in the formula
                  X_{i+1} = A ∗ X_i mod M,
      the value of X_{i+1} is always in the range (−M, M)

This is a practice question for a computer science test I have today and I am unsure about the answer? I remember we talked about using this formula in randNumGeneration...? If someone could please help m开发者_JAVA百科e understand, that would be great. Thanks!

(I think X_{i} is read: X sub i)

X_{i+1} = A ∗ X_i mod M

This means that (i+1)-th value of sequence X is equal to the value of A multiplied by the i-th (previous) value of the X sequence and then fed to modulus operator, which places the result in the [0, M) interval.

So the answer is true.

Example:

let A = 3, M = 5 and X0 = 4.
X1 = A * X0 mod 5 = 3 * 4 mod 5 = 2 mod 5
X2 = A * X1 mod 5 = 3 * 2 mod 5 = 1 mod 5
X3 = A * X2 mod 5 = 3 * 1 mod 5 = 3 mod 5
X4 = A * X3 mod 5 = 3 * 3 mod 5 = 4 mod 5

let A = -3, M = 5 and X0 = 1.
X1 = A * X0 mod 5 = -3 * 1 mod 5 = 2 mod 5
X2 = A * X1 mod 5 = -3 * 2 mod 5 = 4 mod 5
X3 = A * X2 mod 5 = -3 * 4 mod 5 = 3 mod 5
X4 = A * X3 mod 5 = -3 * 3 mod 5 = 1 mod 5

I believe that X_{0} is the first of the X sequence and that it's already between -M and M.

The modulo is the remainder of an euclidian division. (See Wikipedia) The sign of the remainder is not clearly defined for this operation.

Let's say the euclidian division of d by q yields n remains r.

In computer science, those numbers sastistfy :

1. q in Z
2. d = n * q + r
3. abs(r) < abs(n)

This definition leads to the possibility of having quotient and remainder of both signs. In theory, positive remainders are always chosen, but depending of the algorithm in computer science, it can also be negative.

Nevertheless, it's always : -M < r < M And we can say : 0 <= abs(r) < M

So, assuming the hypothesis I made, the answer is clearly true.