Random Number Generators

Random number generators are useful in a variety of computer programs, but the code may be difficult to debug because results are not always easy to repeat. Most programmers use "pseudo-random" number generators instead instead of truely random values, since these algorithms produce a sequence of numbers that appear to be random, but the pattern can be repeated if started with the same initialization conditions. There are many interesting algorithms for pseudo-random numbers.

Pseudo-random number generators usually have several potential difficulties including:

  1. The algorithm may become cyclic, repeating the same sequence that that was given before.
  2. The sequence can decay eventually into a pattern that does not appear random at all.
  3. The numbers are not uniformly distributed.
A good pseudo-random number generator is one that has a relatively uniform distribution, and a very long cycle before repeating a sequence or decaying altogether. Such algorithms are usually initialized with a "seed" number so that when one wishes to repeat a sequence, all that is required is to repeat the initial seed. To create random sequences, the seed can be initialized with values that are unpredictable, such as numbers grabbed from the computer's internal clock or other similar values.

A Pseudo-Random Number Generator
Using the XOR Operation and Bit Shifting

The following algorithm uses the "exclusive OR" (XOR) operation to take a bit pattern of some seed number, and generate a pseudo-random number that can be used as the next seed. This bit manipulation process modeled after the Tausworth Algorithm, is known to have a a relatively good distribution and a long cycle before repeating. The example illustrated here uses an eight bit entity to demonstrate how the algorithm works, but ideally would be based on a datatype that contains a very long string of binary digits.


The general concept is that the bits from the high order position in the original seed are shifted into the low order positions. The XOR operation between those two values "flips" some of the bits. Then the low order bits are shifted into the high order position to do the same thing. Once both shifts and flips are done, the resulting number becomes the new seed.

Notice that the sum of bits used in the two shifts adds up to be the total length of the data type, in this case 8 bits. If a 32-bit integer were used as the data type, the sum of the left and right shift operations should equal 32. Another important detail is that shifts are "open" or "unsigned", where zeros fill from the left and the right.

      10111001       Initial Seed
      00010111       Shift Right N=3
      10101110       XOR Values

      10101110       Temporary Value
      110 00000       Shift Left M=5
      01101110       XOR for New Seed

            Note: N + M = 8


Now Apply the Algorithm!



Donald W. Hyatt:     dhyatt@tjhsst.edu

Phyllis T. Rittman:     prittman@tjhsst.edu