Potency:

As discussed in last section, a long period is of course necessary for a sequence to look random, but it's not sufficient. As an easy example, we let a = 1, c = 1, m = 2³¹ , X₀ = 0, then we get the sequence 0, 1, 2, 3,... . It has a very long period, but nobody would ever think it random. So there are more to consider. In this section, we will introduce some concept called Potency, which will take care of situations like this.

When the multiplier satisfies the conditions of Theorem A, such s always exists since b is a multiple of every prime dividing m. For example, if b = 2²*3*5, m = 2⁹*3²*5, then the potency is 5.

Now that we always assume the conditions of Theorem A is satisfied, we may analyze the randomness of the sequence by taking X₀ = 0, since 0 occurs somewhere in the sequence. With this assumption, we have X_n = ((aⁿ - 1)c/b) mod m. If we expand aⁿ - 1 = (b+1) ⁿ - 1 by the binomial theorem, we find that

X_n = c(n + (n!/(2!(n-2)!))*b + ... + (n!/(s!(n-s)!))*b^s-1) mod m.

All terms in b^s, b^s+1, etc., may be igored, since they are multiples of m.

Let's consider some special cases. If a = 1, the potency is 1; and X_n = cn mod m, this sequence can be observed to be not random. The case we discussed at the beginning is a =1, c = 1. If the potency is 2, we have X_n = cn + cbn(n-1)/2, and again the sequence is not very random; indeed,

X_n+1 - X_n = c + cbn mod m.

so the differences between one generated number and the next are very simply related from one value of n to the next.

The situation gets better when the potency becomes bigger. A potency of at least 5 would seem to be required for sufficiently random values.

At the beginning , people didn't realise the importance of big potency. In history, the following form of generators:

have been widely discussed in the literature and recommended by many authors. It satisfies the condition in Theorem A if k ≥ 2, so has period as long as 2^e. However, some five years of experimentation with this method show that this kind of generators should be avoided. Potency is one of the most important factors.

Other Methods:

Besides the simple linear congruential method mentioned above, there are many other kinds of generators. Many of them are based on this simple method or are modification of this method. We give a brief introduction to some of them in the following:

Multiple Recursive Generators:

A simple extension of simple linear congruential method is to use multiples of previous k values to generate the next one:

The number of previous number used, k, is called the "order" of the generator.

One advantage of this method is the the period can be much longer than the simple linear conguential method. For m a prime, Knuth has shown that the maximum period is m^k - 1 with properly chosen a_i's.

Lagged Fibonacci congruential generator:

This is a special case of the multiple recursive generators.

A simple Fibonacci sequence has X_i+2 = X_i+1 + X_i. Reducing the numbers mod m produces a sequence that looks somewhat random but actually does not have satisfactory randomness properties.

Instead of combining successive terms, we combine terms at some greater distance apart, so the lagged Fibonacci congruential generator is

If j, k, and m are chosen properly, the lagged Fibonacci generator can perform well.

Inversive Congrutial Generators:

All the generators mentioned before are linear generators, i.e. any number in the sequence is linear function of its predecessors. Many nonlinear generators have been proposed. But since the output of nonlinear generators are more complicated, more study about their properties is still needed. Following is one of them:

where X^- denotes the multiplicative inverse of X modulo m, if it exists, or else it denotes 0.

The multiplicative inverse, X^-, of X modulo m is defined for all nonzero x relatively prime to m by

X*X^- = 1 mod m.

Get random integers in any interval:

Using linear congruential generator, we get random number sequence of integers in [0, m-1]. Devide the sequence by m, we get random number sequence in [0,1). Denote the sequence in [0,1) by U_n. To get a random integer sequence Y_n between 0 and k - 1, we can multiply U_n by k, and let Y_n = [kU_n], where [U] denotes the biggest integer that is no larger than U. If U_n is uniformly distributed in [0,1), then Y_n is uniformly distributed in the set {0, 1, 2,..., k-1}.