# Fast 8-bit pseudorandom number generator

While doing some retro-programming, I was after a small, fast random number generator for an old computer. 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, by EternityForest, which appeared perfect for my needs. It maintains 4 bytes of state, and so in theory should have a cycle of around [math]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 divs!

Note: In my testing, depending on the initial state, the cycle is actually in the range 4.2M - 4.6M, depending on the initial state. This is still more than adequate for simple games and such on an 8-bit micro. Also, changing the shift into a rotate actually reduces the cycle to around 400k. I don't know where the discrepancy with the original article comes from, although I did not use grep in my testing, but wrote code to find a matching sequence of 500 samples (bytes).

## C Implementation

```/***
X ABC Algorithm Random Number Generator for 8-Bit Devices
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 */
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.

```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
00140         STA     RNDB
00150         LSRA
00170         EORA    RNDA
00180         STA     RNDC
00190         RTS```

## DieHarder 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```