Fast 8-bit pseudorandom number generator
While doing some retro-programming, I was after a small, fast random number generator for an old computer (specifically, a Tandy TRS-80 Colour Computer I, with 895kHz Motorola 6809 CPU). Modern algorithms tend to keep large state, or do operations that would be "hard" on an old 8-bit microcomputer (eg. multiply, divide, wide operations). After trawling the internet for too long, I can across Ultra Fast Pseudorandom number generator for 8-bit (PRNG), by EternityForest, which appeared perfect for my needs. It maintains 4 bytes of state, and so in theory could have a cycle of around [math]\displaystyle{ 2^{32} }[/math] (see note below, it doesn't), which is far better than I need, and most importantly, it's a small number of simple, fast 8-bit ops - no multiply ops, no modulo ops, no divides!
Considering the size of the state (32 bits), we can brute-force map all the cycles (only takes a couple of minutes, single threaded). Doing this, we see that there are two cycles of a little over one billion in length. However, there are also 64 cycles of only 3072 length. Starting seed value is important, and, interestingly, (0,0,0,0) results in one of the long cycles. This is more than adequate for simple games and such on an 8-bit micro. I don't know where the discrepancy with the original article comes from, although I did not use grep in my testing, but rather wrote code to map out all possible state values:
Cycle length: 1155661824, instances: 2, first seed (a,b,c,x): (0,0,0,0)
Cycle length: 550141952, instances: 2, first seed (a,b,c,x): (9,0,0,0)
Cycle length: 54042624, instances: 16, first seed (a,b,c,x): (1,0,0,0)
Cycle length: 7667712, instances: 2, first seed (a,b,c,x): (123,0,1,0)
Cycle length: 1507328, instances: 2, first seed (a,b,c,x): (172,0,0,0)
Cycle length: 32768, instances: 4, first seed (a,b,c,x): (216,0,65,0)
Cycle length: 3072, instances: 64, first seed (a,b,c,x): (74,0,127,0)
Noting that it is somewhat unusual to see a plain bit shift here rather than a rotate, we can explore how changing to a rotate changes the cycles. The changes are significant, and, notably, (0,0,0,0) is no longer a long cycle, the minimum cycle length is now 16384, and the maximum cycle length is slightly reduced:
Cycle length: 1135083520, instances: 2, first seed (a,b,c,x): (5,0,0,0)
Cycle length: 430997504, instances: 2, first seed (a,b,c,x): (10,0,0,0)
Cycle length: 226377728, instances: 4, first seed (a,b,c,x): (1,0,0,0)
Cycle length: 26771456, instances: 2, first seed (a,b,c,x): (8,0,0,0)
Cycle length: 14843904, instances: 4, first seed (a,b,c,x): (167,0,0,0)
Cycle length: 14778368, instances: 2, first seed (a,b,c,x): (2,0,0,0)
Cycle length: 5275648, instances: 2, first seed (a,b,c,x): (130,0,0,0)
Cycle length: 3217408, instances: 32, first seed (a,b,c,x): (0,0,0,0)
Cycle length: 524288, instances: 2, first seed (a,b,c,x): (147,0,12,0)
Cycle length: 16384, instances: 16, first seed (a,b,c,x): (214,0,9,0)
C Implementation
The C-code from the link, formatted and most comments stripped, is:
/***
X ABC Algorithm Random Number Generator for 8-Bit Devices
https://www.electro-tech-online.com/threads/ultra-fast-pseudorandom-number-generator-for-8-bit.124249/
Not safe for cryptographic use!
***/
static uint8_t a, b, c, x;
/* return 8-bit pseudorandom number */
uint8_t rnd8() {
x++;
a = (a ^ c) ^ x;
b = b + a;
c = (c + (b >> 1)) ^ a;
return c;
}
/* Add entropy into the state */
void init_rng(uint8_t s1, uint8_t s2, uint8_t s3) {
/* XOR new entropy into key state */
a ^= s1;
b ^= s2;
c ^= s3;
rnd8();
}
6809 Assembler
Code in Tandy CoCo EDTASM format, around 49 cycles, not including the BSR. You can shave about another 10 cycles off using Direct Page (DP) addressing for the 4 bytes of state, which I've been doing in various code where I value performance, using page 0 bytes $FC through $FF.
00010 * 8-BIT RANDOM NUMBER
00020 * GENERATOR
00030 * RANDOM RETURNED IN A
00040 RNDA FCB 0
00050 RNDB FCB 0
00060 RNDC FCB 0
00070 RNDX FCB 0
00080 RND INC RNDX
00090 LDA RNDA
00100 EORA RNDC
00110 EORA RNDX
00120 STA RNDA
00130 ADDA RNDB
00140 STA RNDB
00150 LSRA
00160 ADDA RNDC
00170 EORA RNDA
00180 STA RNDC
00190 RTSDieHarder results
Yeah, not so great, but definitely not surprising, either.
$ ./rnd8 -g | dieharder -g 200 -a
#=============================================================================#
# dieharder version 3.31.1 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name |rands/second| Seed |
stdin_input_raw| 1.21e+07 | 977501942|
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.00000000| FAILED
diehard_operm5| 0| 1000000| 100|0.00000000| FAILED
diehard_rank_32x32| 0| 40000| 100|0.00000000| FAILED
diehard_rank_6x8| 0| 100000| 100|0.00000180| WEAK
diehard_bitstream| 0| 2097152| 100|0.00000000| FAILED
diehard_opso| 0| 2097152| 100|0.00000000| FAILED
diehard_oqso| 0| 2097152| 100|0.00000000| FAILED
diehard_dna| 0| 2097152| 100|0.00000000| FAILED
diehard_count_1s_str| 0| 256000| 100|0.00000000| FAILED
diehard_count_1s_byt| 0| 256000| 100|0.00049851| WEAK
diehard_parking_lot| 0| 12000| 100|0.00000000| FAILED
diehard_2dsphere| 2| 8000| 100|0.00000000| FAILED
diehard_3dsphere| 3| 4000| 100|0.01507987| PASSED
diehard_squeeze| 0| 100000| 100|0.00000000| FAILED
diehard_sums| 0| 100| 100|0.01213356| PASSED
diehard_runs| 0| 100000| 100|0.00000000| FAILED
diehard_runs| 0| 100000| 100|0.00000000| FAILED
diehard_craps| 0| 200000| 100|0.00000000| FAILED
diehard_craps| 0| 200000| 100|0.00000000| FAILED
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
sts_monobit| 1| 100000| 100|0.49771113| PASSED
sts_runs| 2| 100000| 100|0.00002097| WEAK
sts_serial| 1| 100000| 100|0.24510342| PASSED
sts_serial| 2| 100000| 100|0.39513131| PASSED
sts_serial| 3| 100000| 100|0.17050767| PASSED
sts_serial| 3| 100000| 100|0.61339061| PASSED
sts_serial| 4| 100000| 100|0.20127654| PASSED
sts_serial| 4| 100000| 100|0.83207402| PASSED
sts_serial| 5| 100000| 100|0.00631037| PASSED
sts_serial| 5| 100000| 100|0.06772865| PASSED
sts_serial| 6| 100000| 100|0.00000000| FAILED
sts_serial| 6| 100000| 100|0.00000001| FAILED
sts_serial| 7| 100000| 100|0.00000074| FAILED
sts_serial| 7| 100000| 100|0.55324491| PASSED
sts_serial| 8| 100000| 100|0.03992936| PASSED
sts_serial| 8| 100000| 100|0.00231542| WEAK
sts_serial| 9| 100000| 100|0.00000000| FAILED
sts_serial| 9| 100000| 100|0.00000000| FAILED
sts_serial| 10| 100000| 100|0.00000000| FAILED
sts_serial| 10| 100000| 100|0.00000000| FAILED
sts_serial| 11| 100000| 100|0.00000000| FAILED
sts_serial| 11| 100000| 100|0.00000000| FAILED
sts_serial| 12| 100000| 100|0.00000000| FAILED
sts_serial| 12| 100000| 100|0.00000000| FAILED
sts_serial| 13| 100000| 100|0.00000000| FAILED
sts_serial| 13| 100000| 100|0.00000000| FAILED
sts_serial| 14| 100000| 100|0.00000000| FAILED
sts_serial| 14| 100000| 100|0.00000000| FAILED
sts_serial| 15| 100000| 100|0.00000000| FAILED
sts_serial| 15| 100000| 100|0.00000000| FAILED
sts_serial| 16| 100000| 100|0.00000000| FAILED
sts_serial| 16| 100000| 100|0.00000000| FAILED
rgb_bitdist| 1| 100000| 100|0.00000000| FAILED
rgb_bitdist| 2| 100000| 100|0.00000000| FAILED
rgb_bitdist| 3| 100000| 100|0.00000000| FAILED
rgb_bitdist| 4| 100000| 100|0.00000000| FAILED
rgb_bitdist| 5| 100000| 100|0.00000007| FAILED
rgb_bitdist| 6| 100000| 100|0.00000000| FAILED
rgb_bitdist| 7| 100000| 100|0.01921137| PASSED
rgb_bitdist| 8| 100000| 100|0.00000000| FAILED
rgb_bitdist| 9| 100000| 100|0.00000000| FAILED
rgb_bitdist| 10| 100000| 100|0.00000000| FAILED
rgb_bitdist| 11| 100000| 100|0.00000000| FAILED
rgb_bitdist| 12| 100000| 100|0.00000000| FAILED
rgb_minimum_distance| 2| 10000| 1000|0.00000000| FAILED
rgb_minimum_distance| 3| 10000| 1000|0.00000000| FAILED
rgb_minimum_distance| 4| 10000| 1000|0.00000000| FAILED
rgb_minimum_distance| 5| 10000| 1000|0.00000000| FAILED
rgb_permutations| 2| 100000| 100|0.00000000| FAILED
rgb_permutations| 3| 100000| 100|0.00000000| FAILED
rgb_permutations| 4| 100000| 100|0.00000000| FAILED
rgb_permutations| 5| 100000| 100|0.00000000| FAILED
rgb_lagged_sum| 0| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 1| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 2| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 3| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 4| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 5| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 6| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 7| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 8| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 9| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 10| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 11| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 12| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 13| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 14| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 15| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 16| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 17| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 18| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 19| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 20| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 21| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 22| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 23| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 24| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 25| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 26| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 27| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 28| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 29| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 30| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 31| 1000000| 100|0.00000000| FAILED
rgb_lagged_sum| 32| 1000000| 100|0.00000000| FAILED
rgb_kstest_test| 0| 10000| 1000|0.00000103| WEAK
dab_bytedistrib| 0| 51200000| 1|0.00000000| FAILED
dab_dct| 256| 50000| 1|0.00000000| FAILED
Preparing to run test 207. ntuple = 0
dab_filltree| 32| 15000000| 1|0.00000000| FAILED
dab_filltree| 32| 15000000| 1|0.00000000| FAILED
Preparing to run test 208. ntuple = 0
dab_filltree2| 0| 5000000| 1|0.00000000| FAILED
dab_filltree2| 1| 5000000| 1|0.00000000| FAILED
Preparing to run test 209. ntuple = 0
dab_monobit2| 12| 65000000| 1|1.00000000| FAILED
