Fast 8-bit pseudorandom number generator

From Wikistix
Jump to navigation Jump to search

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[edit]

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 */
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[edit]

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

DieHarder results[edit]

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

See Also[edit]


Misinformation found herein copyright Paul Ripke (aka “stix”) stixpjr@gmail.com.