H O M E - APOLLO181 INTRODUCTION PWM LED Dimmer Step Motor Controller Sound Generator: Part 1 Sound Generator: Part 2 Random Number Generator

Generating Random Numbers

UNDER CONSTRUCTION

Techniques for generating random numbers (RNGs) are useful when we need to simulate undetermined events, such as in games, in security applications or in computational science for simulation and prediction scopes.

Algorithms based on repeated bit shifting and XOR operations provide a basic means for generating non sequential lists of numbers in a quick and easy way on any computer.

In Apollo181 it has been implemented a modified version of George Marsaglia's XORShift generator, limited to only 8-bit, which produces a full period loop (2^8-1=255) of pseudo-random numbers in just few machine cycles [Xorshift RNGs, Journal of Statistical Software, Vol.8, Issue.14, 2003].

This pseudo-random number generator requires an initial seed to properly work and it is based on selected combinations of sequences of Shift Left, Exclusive OR and Shift Right bitwise operations. An important detail is that shifts are "open" or "unsigned", where zeros fills from the left and the right.

Using a (x;y,z) combination and an initial seed of K, the algorithm, which returns a pseudo-random number K3, is shown in the following diagram. The output, K3, will be also the new seed for the next cycle.

 K(seed) / \ K Shift Left K for x times \ / XOR | K1 / \ K1 Shift Right K1 for y times \ / XOR | K2 / \ K2 Shift Left K2 for z times \ / XOR | K3(new seed)

As an example, using a (3;1,5) combination and an initial seed of 70 (i.e. 01000110), the algorithm, returning the pseudo-random number 237 (i.e. 11101101), is shown in the following diagram:

 01000110(seed) / \ 01000110 00110000 (Shift Left 3 times) \ / XOR | 01110110 / \ 01110110 00111011  (Shift Right 1 time) \ / XOR | 01001101 / \ 01001101 10100000  (Shift Left 5 times) \ / XOR | 11101101(new seed)

The 74181 ALU can shift left on a single command, but it needs a special routine in APOLLO181 to shift right, which makes a shift right operation four times slower than a shift left. Thus, I have tested the sequences of XORShift iterations among the ones that required the minimum number of shift right operations.

The sequences I tested are: (1;1;3) which requires one shift left, one shift right and three shift left operations; (3;1;1) which requires three shift left, one shift right and one shift left operations;(3;1;5) that requires three shift left, one shift right and five shift left;(5;1;3) that requires five shift left, one shift right and three shift left.

In the picture you can see the four different distributions of the numbers generated in two complete loops of the different combinations in the 8-bit version of the Marsaglia’s algorithm.

The one I liked more was the (3;1;5) combination, choosen to be implemented on APOLLO181.