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 values and generates a seed that is guaranteed to be in cycle with a period of 59748. However, there are only 64 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:	
c1=*+1
	lda #31
	asl
b1=*+1
	eor #53
	sta c1
	adc b1
	sta b1
	rts

set_seed:
	pha
	and #$fa
	sta b1
	pla
	ora #$05
	sta c1
	rts