

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 8bit, which produces a full period loop (2^81=255) of pseudorandom numbers in just few machine cycles [Xorshift
RNGs, Journal of Statistical Software, Vol.8, Issue.14, 2003].
This
pseudorandom 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 pseudorandom 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 pseudorandom 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 8bit version of the Marsaglia’s algorithm.
The
one I liked more was the (3;1;5) combination, choosen to be implemented on APOLLO181.



DISCLAIMER & CREDIT:
All data here reproduced are for educational and noncommercial purpose, following fairuse 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 thirdparty 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 adsupported: 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 popup windows are not Author's property. They can change and the Author is nonresponsible
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 noncommercial usage and ONLY if you give a clear reference to its source and project name, without 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



