Make your own free website on Tripod.com

headerdef.jpg

H O M E - APOLLO181 INTRODUCTION
Binary Clock Algorithm
Shift-and-Add Multiplication
Prime Numbers Benchmark
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.

 

xorshift.jpg

DISCLAIMER & CREDIT: All data here reproduced are for educational and non-commercial purpose, following fair-use guidelines.

This is an INDIPENDENT AND UNOFFICIAL hobby site. Either Dr. Peter R. Rony or the Blacksburg group or Computer History Museum (Mountain View, CA) or other third-party DO NOT HAVE ANY ASSOTIATION with this work.

Author G.G. DOESN'T EARN ANYTHING FROM ADVERTISEMENT. This site is not in the business of making money. This site is visible thanks to the Free Web Hosting Tripod Service, so it is ad-supported: advertisement contents, costs and revenues are full managed by the service itself. Author does not have any involvement in them. The advertising links in the Site pages and in the pop-up windows are not Author's property. They can change and the Author is non-responsible about their contents and working. The Author is not responsible about the linked sites.
The information presented here is just that: INFORMATION. Use it at your own risk and for only non commercial purpose. The information here presented is believed to be technically correct and everything presented on this site is done so in good faith. Anyhow you (the reader) are responsible for anything that you might do as a result of reading this article. You assume complete and total responsibility for your actions! Author is not responsible for any misuse or damage coming from the reading and using this information.

Text and images from original typewritten Bugbooks I and II in 1974 are permission courtesy of Dr. Peter R. Rony, the original author and sole copyright owner of the Bugbooks I, II, IIA, III, V, and VI.

The background image on the header of each page of the site is "Sunset over western South America" photographed on 12 April 2011 by an Expedition 27 crew member on the International Space Station. (Image credit: NASA). On it I have merged titles and a my photo of TIL302 displays.

Texas Instruments data are Texas Instruments Copyright and reported by Courtesy of Texas Instruments.

 

TERM OF USE: With clear exception for texts and images which are not author's property, Gianluca G. freely authorizes you the downloading, printing and reproducing of APOLLO181 data, texts and images ONLY for non-commercial usage and ONLY if you give a clear reference to its source and project namewithout any right to resell or redistribute them or to compile or create derivative works.

Any rights not expressly granted herein are reserved.

 

Copyright (c) 2012 by Gianluca G. Italy