base:ax_tinyrand8

This algorithm produces eventually all numbers between 0 and 255, but the sequence does not repeat until 59748 values. The routine has a 16bit state, but yields an 8 bit value. The randomization is a combination of an ASL, EOR and ADC command. The name AX+ is derived from comes from the ASL, XOR and addition operation. I have tested several other triplets of similar operations, this version here gave the longest period.

This version stores the seed as arguments and uses self-modifying code and requires only 15 bytes for the random function. The execution time is constant at 18 cycles and much faster than for example a 789-Xorshift.

The seeding function was tricky, since putting any two values into b1 and c1 comes with a 10% risk of ending up in a cycle with shorter period. Therefore, a seeding function is provided that takes an 8 bit value and generates a seed that is guaranteed to be in cycle with a period of 59748. Thus, there are 256 different states reachable after seeding.

In a test, I plotted the output of 51200 random values, which don't seem to reveal any visible patterns:

;; AX+ Tinyrand8 ;; A fast 8-bit random generator with an internal 16bit state ;; ;; Algorithm, implementation and evaluation by Wil ;; This version stores the seed as arguments and uses self-modifying code ;; The name AX+ comes from the ASL, XOR and addition operation ;; ;; Size: 15 Bytes (not counting the set_seed function) ;; Execution time: 18 (without RTS) ;; Period 59748 rand8: b1=*+1 lda #31 asl a1=*+1 eor #53 sta b1 adc a1 sta a1 rts ; sets the seed based on the value in A ; always sets a1 and b1 so that a cycle with maximum period is chosen ; constants 217 and 21263 have been derived by simulation set_seed: pha and #217 clc adc #<21263 sta a1 pla and #255-217 adc #>21263 sta b1 rts

base/ax_tinyrand8.txt · Last modified: 2021-11-29 00:12 by wil