What is a Linear Congruential Random Number Generator?

What I want is this: A series of 16 numbers in [0,1) that behave like I would expect a series of random numbers to behave.

And there it is, sitting on my desk - a linear congruential random number generator. Well, I don't know just how random it is, but we'll look at it anyway. As I look at it, I definitely notice the linear part --

ax_i + c

y = ax_i + c is simply the equation for a straight line with slope a and y intercept c.

The general form of a linear congruential random number generator ( lcrng ) is:

x_(i+1) = ( ax_i + c ) mod m , i = 0,...,m - 1; where x_0 is the seed (initial value).

If you aren't familiar with the mod, consider this.

12 mod 10 ~ 2. The answer is the remainder 2 of the division 12 divided by 10.

My own lcrng on my desk looks like the following:

x_0 = 5 , where 5 is the seed ( the starting value ).

x_(i+1) = ( 4x_i + 3 ) mod 16

x_1 = ( 4*5 + 3 ) mod 16 = 23 mod 16 ~ 7

x_2 = ( 4*7 + 3 ) mod 16 = 31 mod 16 ~ 15

x_3 = ( 4*15 + 3 ) mod 16 = 63 mod 16 ~ 15

We will start repeating now because we have repeated remainders.

And so our sequence is :

5, 7, 15, 15, 15,.....on and on and on.......the same way......

and we have our generation of numbers.

m -- is the modulus ------- m > 0
a -- is the multiplier ------- 0 <= a < m
c -- is the increment ------ 0 <= c < m
x_0 -- is the seed ---------- 0 <= x_0 , m

Ok, how can we make x_(i+1) = ( 4x_i + 3 ) mod 16 a better lcrng?

Well, first of all, it would be nice if we could get it to generate all the numbers from 0 to 15 instead of just 7, 15, 15, 15, ........on and on.... well, don't forget the seed, 5.

Here's how. We have to meet 3 conditions.

condition 1:

c must be relatively prime to 16. This condition is met. 3 is relatively prime to 16.

b= a - 1 is a multiple of p, for every prime p that divides m.
Well, there is only one prime number that divides 16. It is 2. So b must be a multiple of 2. Also, 0 <= b <= 14 depending on what a is. So b must be 2, 4, 6, 8, 10, 12, or 14..

b is a multiple of 4 if m is a multiple of 4. m = 16 is a multiple of 4; so b must be a multiple of 4. Well, our choices from condition 2 that are multiples of 4 are 4, 8, and 12.

Let's arbitrarily choose 4 for b. Then a = 5 and we have our multiplier.

a = 5; c = 3; and m = 16

So we have x_(i + 1) = ( 5x_i + 3 ) mod 16

We should be able to use any seed x_0 such that 0 <= x_0 < 16.

Let's try x_0 = 3 and see what happens.

x_0 = 3

x_1 = ( 5*3 + 3 ) mod 16 = 18 mod 16 ~ 2

x_2 = ( 5*2 + 3 ) mod 16 = 13 mod 16 ~ 13

x_3 = ( 5*13 + 3) mod 16 = 68 mod 16 ~ 4

x_4 = ( 5*4 + 3 ) mod 16 = 23 mod 16 ~ 7

x_5 = ( 5*7 + 3 ) mod 16 = 38 mod 16 ~ 6

x_6 = ( 5*6 + 3 ) mod 16 = 33 mod 16 ~ 1

x_7 = ( 5*1 + 3 ) mod 16 = 8 mod 16 ~ 8

x_8 = ( 5*8 + 3 ) mod 16 = 43 mod 16 ~ 11

x_9 = ( 5*11 + 3) mod 16 = 58 mod 16 ~10

x_10 = ( 5*10 + 3) mod 16 = 53 mod 16 ~ 5

x_11 = ( 5*5 + 3 ) mod 16 = 28 mod 16 ~ 12

x_12 = ( 5*12 + 3) mod 16 = 63 mod 16 ~ 15

x_13 = ( 5*15 + 3) mod 16 = 78 mod 16 ~ 14

x_14 = ( 5*14 + 3) mod 16 = 73 mod 16 ~ 9

x_15 = ( 5*9 + 3 ) mod 16 = 48 mod 16 ~ 0

x_16 = ( 5*0 + 3 ) mod 16 = 3 mod 16 ~ 3

And we see that our remainder of 3 is a repeat remainder (our seed) which means our sequence will repeat itself from this point on. But we have our full generation.

Now divide each number by 16 so that we will have all our numbers in [0,1).

.1875 .1250, .8125, .2500, .4375, .3750, .0625, .5000, .6875, .6250, .3125, .7500, .9375, .8750, .5625, 0 is our sequence in [0,1).

But now, suppose I want a binary sequence of length 16.

Consider the 1st digit to the right of the decimal point.

If it's odd, let it be 1.

If it's even, let it be 0.

We get 1,1,0,0,0,1,0,1,0,0,1,1,1,0,1,0.

Warning: Don't use other digits than the 1st one after the decimal point. Results may not be good.

Is it really a random sequence or at least a pseudo random sequence? I think most of us would say it's a bit short to really know.

What is a good lcrng? According to Knuth,

(3141592653 * x_1 + (2718281829) mod 2^35 x_0 = seed = 0

Back to Random Number Generators, Statistics, and Probability.