Short Sequence Random Number Generator
Random number generators typically have periods over 2^30. One generator
described in these pages has a period of 2^32; another a period of almost 2^128.
Yet another is so large that its exact value is without meaning. One may ask why would anybody want a short sequence generator.
It is easy to shuffle a list of numbers. Assume that your list represents a deck
of cards. The cards are numbered 1 to 52. Point at card number 1 and generate a
random number in the range of 1 to 52. Assume you generated 12. Swap cards 1 and
12. Card 12 has been selected with probability 1/52. Point at card 2 (actually
position 2) and generate a random number from 2 to 52. Swap. Repeat as needed.
The above process works well for short lists. But if the list has 40000 entries
the list requires 80K bytes. The charm of a short sequence random number
generator is that a few lines of code can generate the entire shuffled sequence,
one entry at a time.
A simple and very good short sequence generator is given by
Seed[i] = (seed[i-1]*A) mod 0x10001
Where seed is in the range of 1 to 0x10000 and A is one of 2^15 acceptable
values. Notice that the above has the form of a standard Linear Congrential
Generator but with C=0. For what it is worth, this generator works well because
(2^16)+1 is a prime. Unfortunately neither (2^32)+1 nor (2^64)+1 are primes.
A=3 (the lowest acceptable value) works surprisingly well. A=0x1234 is
easy to remember as are 0x0BAD and 0xC0DE. The last two are easy to
remember because they say "no bad code."
As implemented this generator is
Seed[i] = ((seed[i-1]+1)*A) mod 0x10001) -1
I.e. subtract one from the real seed before storing and add one after we
fetch it before we use the real seed.
In this form, all seed values fit into 16 bits.
Short Sequence Variations
The short sequence generator has a period of 2^16. To
make shorter sequences simply ignore any return value outside the desired range
discard the value and fetch the next one. Repeat until the value is in the
desired range.
By selecting different values of A one can generate over 32,000 possible sequences.
One should study the multiplier validation code given in Knuth's TAOCP. The number of available
sequences can be expanded by any number of programming “tricks”. The tricks are
performed by a special f2. One trick I used was an xor followed by a bit permutation. A better form is the same xor followed by a
multiply by an odd number mod 2^16. Both the xor value and the odd multiplier
are chosen randomly. Using the better form, the number of possible sequences
goes from about 2^15 with just the choice of the multiplier to 2^(15+16+15) -- perhaps
enough for casino gambling.
Longer Short Sequences
The short sequence generator has a period of only
2^16. To make longer sequences one has to use a different process.
We can accomplish that by scrambling the result of a longer generator with
the proper period in its low bits. In
nearly C pseudo code the process is
temp = seed++ & 0x3FFFF; // ++ is a good enough
for(p=0; p<3; p++)
{
temp ^= temp>>16;
temp = ss(temp, m[p]); // use & replace only the low 16 bits of temp
temp *= d[p];
temp ^= x[p];
temp ^= 0x3FFFF;
}
return temp;
Both x[] and d[] values are chosen randomly except that the d[] array is forced
odd.
The ss(temp, m) function is a modification of our basic short sequence
generator. In this modification the first parameter, temp in the above code, is
the 16 bit seed and the second parameter is the multiplier. The m[] array is
hard coded to 3 values that make the ss() function work. My personal favorite
values are 0x1234, 0x0BAD and 0xC0DE. (The last to values spell zero bad code.)
All operations operate on 16 bit words.
Next Topic (Random Numbers in Cryptography)
Previous Topic
Return to Index