next up previous contents index Search
Next: Analysis Up: 0.5 Miscellaneous Algorithms Previous: References

0.5.12 A Pseudo-Random Number Generator

The below given rand function returns a pseudo-random integer in the range 0 to 999999999 inclusive. It works by creating an array of one-hundred integers from an initial key (or "seed") and then then partitioning the range into two subranges. The first fifty-five entries are integers to be used in pairs to generate a random result. The next forty-two entries are random results already generated but "on hold" until selected in order to disturb any pattern in output caused by a poor key and to shuffle the order of random integers on output. The final two elements in the structure simply contain internal pointers which always reference elements in the 1 to 55 range. The values referenced by these internal pointers are subtracted and then adjusted to be greater than zero if needed to form a result.

This table-subtraction method produces a good degree of randomness alone, but another technique is also used to augment its operation. The result stored at position 100 in the array is used to select one of the 42 entries in locations 56 to 97 in the table for replacement. The number which is being replaced at this location is both promoted up to location 100 and tagged to be returned from the function as it's return value. The number generated by subtraction in the 1 to 55 range replaces this newly promoted number at its old position where it will wait as a possible random return value until a subtraction selects it. This additional "shuffling" serves to negate any subtle patterns that the sequence of values generated with rotating table subtractions might produce.

The init_rand function takes a seed key in the form of an arbitrary length ASCII string. This key is used to seed the random table used, later, by rand to produce random numbers. You will notice that the algorithm adds the string "aEbFcGdHeI " the the beginning of the key before initializing the table. This is to ensure there are both characters with even and odd ASCII values in the seed string. Once the (adjusted) ASCII values of the key are put into the table, the init_rand algorithm cycles through the table shuffling values to form an even, random initial numeric distribution in the table. It then initializes the pointers in positions 98, 99 and 100. At this point everything is ready for the first call to rand.

Scott Gasch