Unsigned 8-Bit XOR-Shift Pseudo-Random Number Generator Algorithm Test.
by William Donnelly
Compared to the JavaScript built-in PRNG as a 'test group'.
Additional information, description, and explanation, and see found extant routine information below-bottom.
This page was coded for Firefox 3.x+, but should work on any modern browser.
Also see 8bitPRNGcolor.html for visual pattern comparison tests.
Original 32-bit C function: ( http://en.wikipedia.org/wiki/Xorshift )
uint32_t xor128(void) {
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t;
t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
New 8-bit JavaScript function: (theoretical "equivalent")
function Unsigned8BitXorShiftPRNG()
{
if (typeof (Unsigned8BitXorShiftPRNG.xx) == "undefined") {
Unsigned8BitXorShiftPRNG.xx = 21; // 123456789 & 0xFF
Unsigned8BitXorShiftPRNG.yy = 229; // 362436069 & 0xFF
Unsigned8BitXorShiftPRNG.zz = 181; // 521288629 & 0xFF
Unsigned8BitXorShiftPRNG.ww = 51; // 88675123 & 0xFF
}
var tt = Unsigned8BitXorShiftPRNG.xx ^ ((Unsigned8BitXorShiftPRNG.xx << 3) & 0xFF);
Unsigned8BitXorShiftPRNG.xx = Unsigned8BitXorShiftPRNG.yy;
Unsigned8BitXorShiftPRNG.yy = Unsigned8BitXorShiftPRNG.zz;
Unsigned8BitXorShiftPRNG.zz = Unsigned8BitXorShiftPRNG.ww;
Unsigned8BitXorShiftPRNG.ww = Unsigned8BitXorShiftPRNG.ww ^ (Unsigned8BitXorShiftPRNG.ww >> 5) ^ (tt ^ (tt >> 2));
return Unsigned8BitXorShiftPRNG.ww;
} // Unsigned8BitXorShiftPRNG -- Unsigned 8-Bit Pseudo-Random Number Generator using Xor-Shift
Click this link to Execute Test Routines
More information, description and explanation, partly from:
http://groups.yyahoo.com/group/cosmacelf/message/7774
Read below to find out more detailed information, but the final conclusion is that this PRNG should be viable and usable for most situations, but especially games and other programs like that. Note that this routine is not "cryptographically secure", which should be evident.
Below is the algorithm coded for the CDP1802 microprocessor. It will work as long as the whole routine is within the same page boundary, but the routine starting address does not have to start on a page boundary. So you can have the starting address be any relative address within a page boundary (as long as the address is less than ~XXD0) and then you must set the starting address of the X value in the LDI instruction at address 0002 below. The routine as coded here uses the SCRT (Standard Call and Return Technique), the routines and setup for which must be included by the user/programmer. This routine expects P=3 (PC = R3) and alters D, DF, RE, RF.0, X and returns with SEP R5. (call with SEP R4 and the starting address of the routine in the next two bytes)
To see another implementation and executing example program, see the program named "256RandomNumbersHex : Display 256 Random Numbers in Hex on Terminal" for the COSMAC ELF-ish CDP1802 Simulator in JavaScript (SimElf++ / COSMAC Elf^2) at: http://www.donnelly-house.net/programming/cdp1802/simelf/. The first 256 numbers generated by that program and this test program were compared and found to be equivalent, so they generate the same sequence — that is a good enough test to know that the 1802 code is correctly implementing the algorithm.
0000: 93 GHI R3 ; get hi address of current memory page 0001: BE PHI RE ; RE will point to array of data values (X, Y, Z, W) 0002: F8 2A LDI 2A ; get lo address of data array 0004: AE PLO RE ; RE points to X value = start of 'array' / data buffer 0005: EE SEX RE ; RX = RE 0006: 0E LDN RE ; get X 0007: FE SHL ; shift 0008: FE SHL ; left 0009: FE SHL ; 3 times 000A: F3 XOR ; XOR with X 000B: 5E STR RE ; save temp T 000C: F6 SHR ; shift right 000D: F6 SHR ; twice 000E: F3 XOR ; XOR with temp T 000F: AF PLO RF ; save value in RF.0 (modified T) 0010: 1E INC RE ; RE points to Y 0011: 0E LDN RE ; get Y 0012: 2E DEC RE ; point back to X 0013: 5E STR RE ; store Y into X 0014: 1E INC RE ; point to 0015: 1E INC RE ; Z 0016: 0E LDN RE ; get Z 0017: 2E DEC RE ; point back to Y 0018: 5E STR RE ; store Z into Y 0019: 1E INC RE ; point to 001A: 1E INC RE ; W 001B: 0E LDN RE ; get W 001C: 2E DEC RE ; point back to Z 001D: 5E STR RE ; store W into Z 001E: 1E INC RE ; RE = W 001F: F6 SHR ; shift W right 0020: F6 SHR ; . 0021: F6 SHR ; . 0022: F6 SHR ; . 0023: F6 SHR ; 5 times 0024: F3 XOR ; XOR with W 0025: 5E STR RE ; store modified W 0026: 8F GLO RF ; get modified T 0027: F3 XOR ; XOR with modified W 0028: 5E STR RE ; save new W value 0029: D5 SEP R5 ; return with random # in D register 002A: 15 DB 15 ; X = 21d 002B: E5 DB E5 ; Y = 229d 002C: B5 DB B5 ; Z = 181d 002D: 33 DB 33 ; W = 51d Hex dump: 0000: 93 BE F8 2A AE EE 0E FE FE FE F3 5E F6 F6 F3 AF 0010: 1E 0E 2E 5E 1E 1E 0E 2E 5E 1E 1E 0E 2E 5E 1E F6 0020: F6 F6 F6 F6 F3 5E 8F F3 5E D5 15 E5 B5 33
Following is more information about the conversion and testing.
I "converted" the 32-Bit XOR-Shift PRNG to 8-Bit. (using JavaScript) Mostly by dividing the values by 4 and/or truncating them to 8-bit. (see the page for function comparison, and the page source for more info)
I then kind of tried to make a test program to compare the values it gives to the built-in JS PRNG. (random() function)
I just choose 65536 random numbers between 0 and 255 and count the number of times each number is chosen. In an 'ideal / perfect world' that would be 256 times each (65536 / 256). Of course, that's not the way things work with random numbers, so there is some 'natural' skew. (similarly for coin tosses, spins of the roulette wheel, etc.)
I also do some averaging (which should be ~256), which you have to be careful about (like averaging 1 and 1000 and getting 500), and minimum and maximum times chosen, which seems to be about +/- 50, and the 'distance' between a number being chosen successively (which ideally should be between zero and some higher value -- I bet there's a (complex) formula to compute that, more or less), and then some averages of all of those, and a rough plot.
Here are the final results for my 8-bit test function and JavaScript's built-in function, which look quite similar:
Unsigned 8-Bit XOR-Shift Pseudo-Random Number Generator Algorithm:
Min Times a Rand# was Chosen = 208
Max Times a Rand# was Chosen = 301
Average Times a Rand# was Chosen = 256
Average Distance between Rand# Chosen Again = 255.080623828942
Min Average Distance = 215.89036544850498
Max Average Distance = 313.625
Min Distance = 0
Max Distance = 2743
JavaScript PRNG: (these values are a snapshot and may/will change with each run)
Min Times a Rand# was Chosen = 215
Max Times a Rand# was Chosen = 309
Average Times a Rand# was Chosen = 256
Average Distance between Rand# Chosen Again = 254.89397478183076
Min Average Distance = 210.71844660194174
Max Average Distance = 303.63255813953486
Min Distance = 0
Max Distance = 2803
On the face of it, it looks like it works. Of course, this is "dangerous", not only because I don't really know what I'm doing.
I might try running it through a DieHard or DieHarder test suite just for kicks and giggles.
Or maybe submit its output to: http://www.cacert.at/random/
Although, as an '8-bit machine', it may not even give a decent data set to test. That is either very possible, or absolutely true. (I don't know enough to state an exact answer -- I just know enough that I know what I don't know, to some extent, know that I should question how much I think I know, and I know enough to be a danger to myself and to others, more often than not)
But it may be "close enough for government work."
There is a seeding issue, but that can be easily resolved, more or less, by calling the routine some number of times per keyboard keypress loop. (assuming you get a keypress before you need some random numbers) Other than that, I'm not sure what a good way to seed it would be.
So I might just code this up and say, "Good enough".
(unless someone dissuades me, and/or makes some good points, etc.)
Also see 8bitPRNGcolor.html for additional visual pattern comparison tests.
Following is an article transcript about a (simple) pseudo-random number generator routine
from the January 1978 issue of the Ipso Facto newsletter; Issue 4; Pages 23 and 24 --
via PDF image scan. (so I didn't find it with a web search, which is why I am
making the text transcript available here --- NOTE: This PRNG algorithm is weak!)
We will refer to this algorithm as Mult13P1 = Multiply by 13 Plus One.
http://homepage.mac.com/ruske/cosmacelf/ipsofacto/raw/Ipso Facto - Issue 04.pdf
RANDOM NUMBER GENERATION FOR THE 1802
by B.J. Murphy
Many computer applications require the use of random numbers.
Computer games such as STAR-TREK, TIC-TAC-TOE use random number
routines to set up initial conditions.
You may be asking yourself "How can a computer generate a truly
random number?" The fact of the matter is that computers cannot
generate random numbers - the computer can be programmed however,
to generate a "pseudo-random" number.
Before you turn the page to read the next article, have a look
at listing 1. This 1802 routine will generate random numbers from
0 to 255. The program however, always generates the same sequence
of random numbers; thus we call this sequence "pseudo-random".
By changing the initial value of the variable "RANDOM",
(statement 40) the program generates different sequences of random
numbers. This initial value is formally known as the random number
seed.
An interesting technique is the use of the summation of powers
of two to achieve multiplication. The equation in statement 9 of
the program can be changed to allow the multiplication of any
number.
If you wish to learn more about random number generation,
consult the reference or any good Computer Science textbook.
REFERENCE: Grieser "Pseudorandom Number Generator", Byte Magazine,
Novemeber 1977, page 218.
LOCN OBJ CODE STMT SOURCE STATEMENT 1802 VER 1.2
0000 1 ************************************************************
0000 2 *** ***
0000 3 *** PSEUDO-RANDOM NUMBER GENERATOR FOR RCA1802 ***
0000 4 *** ***
0000 5 *** ***
0000 6 *** METHOD: TAKE PREVIOUS RANDOM NUMBER,MULTIPLY BY 13 ***
0000 7 *** AND ADD 1 ***
0000 8 *** ***
0000 9 *** MULTIPLY BY 13 BY USING: 13*N = N*2**3 + N*2**2 + N ***
0000 10 *** ***
0000 11 *** REGISTER USAGE: R0=P.C.; R2=X REG ; R3,R4=WORK ***
0000 12 *** ***
0000 13 ************************************************************
0000 14 *
0000 F8 18 15 MAINLOOP LDI RANDOM GET ADDR OF PREVIOUS RANDOM #
0002 A2 16 PLO R2 SAVE INTO R2
0003 17 * CLEAR R2 HIGH FOR SYSTEMS OVER 256 BYTES
0003 E2 18 SEX R2 MAKE R2 X REG
0004 F0 19 LDX R2 GET PREVIOUS RANDOM #
0005 FE 20 SHL X2
0006 FE 21 SHL X2 AGAIN
0007 A3 22 PLO R3 SAVE N*2**2
0008 F4 23 ADD D= N + N*2**2
0009 52 24 STR R2 STORE THE RESULT
000A 83 25 GLO R3 GET N*2**2
000B FE 26 SHL X2 AGAIN GIVES N*2**3
000C F4 27 ADD D= N + N*2**2 + N*2**3
000D FC 01 28 ADI 1 FINISH BY ADDING 1
000F 52 29 STR R2 STORE RESULT
0010 30 *
0010 31 * END OF RANDOM NUMBER CODE GENERATION
0010 32 *
0010 64 33 OUT4 DISPLAY RANDOM #
0011 B4 34 PHI R4 USE AS INTERVAL
0012 24 35 BUZZ DEC R4 DECREMENT
0013 94 36 GHI R4 GET THE VALUE
0014 3A 12 37 BNZ BUZZ DONE ?
0016 30 00 38 BR MAINLOOP YES..ANOTHER RANDOM #
0018 39 *
0018 40 RANDOM DC 57 RANDOM NUMBER SEED
0019 41 *
0019 42 END
0 DIAGNOSTICS GENERATED
3 SYMBOLS
SYMBOL TABLE:
MAINLOOP 0000
BUZZ 0012
RANDOM 0018
READY
Image snapshot of the above transcript from the PDF file.
# END #
E-mail the author / creator / programmer: Contact William Donnelly