Random-number generation

barrym95838 · Post by **barrym95838** » Tue May 30, 2023 3:38 pm

Arlet wrote:

It's possible to optimize in various directions. Using more/less ZP, code size, cycles, or period/quality. Let me know what you care about most.

Thank you for your kind attention. In VTLC02, code size is primary, and cycles are secondary. Everything else is a distant #3, but in this case, I also need a guarantee that all possible values are eventually visited (you and White Flame both appear to have that covered already). That's the main problem with VTLC02's current PRNG.

Arlet · Post by **Arlet** » Tue May 30, 2023 4:39 pm

If code space is at a premium, you might use the 8 bit version of my code, and call the routine twice to obtain 16 bits. While strictly not guaranteeing that every possible value will be visited, the fact that it passes good randomness tests into the gigabytes means that in practice it must have equal chance for each value. Keep in mind that it is possible that certain 16 bit values will occur multiple times while other values are not yet seen.

If you need 16 bits output where each value occurs exactly once per 64k calls, let me know. I can make that too, but it will require a different approach.

Arlet · Post by **Arlet** » Tue May 30, 2023 6:27 pm

Improved code, now 77 cycles and 5 state bytes, and passes 8GB random test. Output is stored in o+0 and o+1

Code: Select all

    CLC 
    LDA #$45
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ADC s+2
    STA s+2
    ADC s+3
    STA s+3
    LDA s+4
    ROL A
    ROL A
    STA s+4
    ADC s+2
    STA o+0
    ADC s+4
    STA s+4
    ADC s+3
    STA o+1
    ADC s+1
    ADC s+4
    STA s+4
    ADC o+0
    STA o+0
    ADC s+4
    STA s+4
    RTS

working example

Arlet · Post by **Arlet** » Wed May 31, 2023 6:13 am

More improved code, now 71 cycles and 5 state bytes, and passes 4GB random test. Output is stored in o+0 and o+1. I've also added this code to my github repository.

Code: Select all

    CLC
    LDA #$45
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ADC s+2
    STA s+2
    ADC s+3
    STA s+3
    LDA s+4
    ROL A
    STA s+4
    ADC s+2
    STA o+0
    ADC s+3
    STA o+1
    ADC s+1
    ROL A
    ADC o+0
    STA o+0
    ADC s+4
    STA s+4
    ADC o+1
    STA o+1
    RTS

Note that the last STA o+0 and STA o+1 are optional. You can modify the program to store the two output bytes somewhere else. For instance, you could return the 16 bit value in X,A pair by replacing the STA o+0 with TAX and removing the STA o+1.
owlet link

barrym95838 · Post by **barrym95838** » Wed May 31, 2023 6:22 am

Code: Select all

    LDA s+4
    ROL A
    STA s+4

can be replaced by

Code: Select all

    ROL s+4
    LDA s+4

and we save a precious byte.

Arlet · Post by **Arlet** » Wed May 31, 2023 6:37 am

I've only tested this with $45 constant at the beginning. It will still work with other odd constants, but quality of random output may vary a bit. For instance with constant 1, it still passes 1GB of output. If you happen to have an even constant in A, you can replace the CLC by SEC.

Arlet · Post by **Arlet** » Wed May 31, 2023 7:01 am

If you just wanted something super simple that produces every single 16 bit value exactly once, in random order, you could use something like this. 16 bit output in A,X:

Code: Select all

    CLC
    LDA #1 ; any odd value
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ASL A
    ADC s+0
    TAX
    EOR s+0
    RTS

Good enough for games where you need a random action for a monster, but it's not going to pass any randomness tests. It's very easy to generate these kinds of random generators. You start with some code that iterates through every single 16 bit number, which is the part between CLC .. STA s+1. You then have two bytes in s+0 and s+1, which have a bit of randomness, but not too good. You then mix these bytes together to improve quality. If you mix with any bijective (invertible) function, then you guarantee that every 16 bit value still occurs exactly once. If you have two bytes A and B, you can create bijective functions by taking any arbitrary function f(), apply it to A, and then apply that to B in an invertible way, for instance with ADC or EOR. So, A = A + f(B), or B = B ^ g(A). Just be careful that you don't add unknown carry flag. You can also use any invertible operation on A or B by itself, such as a bit rotate. These bijective mixers can be stacked.

barrym95838 · Post by **barrym95838** » Wed May 31, 2023 7:36 am

Arlet wrote:

If you just wanted something super simple that produces every single 16 bit value exactly once, in random order, you could use something like this. 16 bit output in A,X:

Code: Select all

    CLC
    LDA #1 ; any odd value
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ASL A
    ADC s+0
    TAX
    EOR s+0
    RTS

The "exactly once" part isn't strictly necessary, but it is acceptable. The winning attributes for me are the tiny code and ZP footprint, so I'll splice it in (with attribution) and run some informal tests. Thank you.

Arlet · Post by **Arlet** » Wed May 31, 2023 8:18 am

The "exactly once" comes naturally if you want tiny code and ZP footprint, but don't want a bunch of missing/duplicate values.

barnacle · Post by **barnacle** » Wed May 31, 2023 3:49 pm

https://xkcd.com/221/

Grin, duck, run...

Neil

Alex1 · Post by **Alex1** » Thu Jun 01, 2023 1:45 pm

a few other random generators :

Code: Select all

batari8 (0)
	Type:         galois8 lfsr
	6502 author:  Fred Quimby
	RAM:          1 byte
	Size:         9 bytes
	Cycles:       11-12
	Period:       255
	References:   https://github.com/batari-Basic
	Notes: 	This is the rand routine included with the 2600 development
		language batari Basic. It's main strength is it's compactness
		and speed.
	Sample:       (2a) 15 be 5f 9b f9 c8 64 32 ...
	Code:
		  LDA randv0
		  LSR
		  BCC noeor
		    EOR #$B4
		noeor:
		  STA randv0


batari8rev (1)
	Type:         galois8 lfsr
	6502 author:  (forward) Fred Quimby, (reversal) Mike Saarna
	RAM:          1 byte
	Size:         9 bytes
	Cycles:       11-12
	Period:       255
	References:   https://github.com/batari-Basic
	Notes: 	This is a reversed version of the LFSR included with batari 
		Basic.  Reversal allows the pseudorandom sequence to be 
		rewound at any point, without requiring additional storage.
	Sample:       (32) 64 c8 f9 9b 5f be 15 2a ...
	Code:
		  LDA randv0
		  ASL
		  BCC noeor
		    EOR #$69
		noeor:
		  STA randv0


batari16 (2)
	Type:         galois8 extended to 16 bits
	6502 author:  Fred Quimby
	RAM:          2 bytes
	Size:         13 bytes
	Cycles:       19-20
	Period:       65535
	References:   https://github.com/batari-Basic
	Notes: 	This is the rand16 routine included with the 2600 development
		language batari Basic, and the default rand routine in 
		7800basic. Its quick and compact for a 16-bit LFSR.
	Sample:       (2a2a) 41 a3 e3 fd d2 d8 ba 19 ...
	Code:
		  LDA randv0
		  LSR
		  ROL randv1
		  BCC noeor
		    EOR #$B4
		noeor:
		  STA randv0
		  EOR randv1

batari16rev (3)
	Type:         galois8 extended to 16 bits
	6502 author:  (forward) Fred Quimby, (reversal) bogax
	RAM:          2 bytes
	Size:         16 bytes
	Cycles:       22-23
	Period:       65535
	References:   https://github.com/batari-Basic
	Notes: 	This is the rand16 routine included with the 2600 development
		language batari Basic, and the default rand routine in 
		7800basic, run backwards
	Sample:       (a124) 19 ba d8 d2 fd e3 a3 41 ...
	Code:
		  LDA randv1
		  LSR
		  LDA randv0
		  ROL
		  BCC skip_eor16
		  EOR #$68
		skip_eor16:
		  STA randv0
		  ROR randv1
		  EOR randv1


pitfall8left (4)
	Type:         fibonacci8 lfsr
	6502 author:  David Crane
	RAM:          1 byte
	Size:         18 bytes
	Cycles:       30
	Period:       255
	References:   https://samiam.org/blog/20130606.html
	Notes:	This is the left-travelling LFSR from the Atari 2600 
		game Pitfall. It's at the core of the game's algorithmic 
		level generation.
	Sample:       (2a) 95 4a a5 52 29 14 8a 45 ...
	Code:
		  LDA randv0
		  ASL
		  EOR randv0
		  ASL
		  EOR randv0
		  ASL
		  ASL
		  ROL
		  EOR randv0
		  LSR
		  ROR randv0
		  LDA randv0


pitfall8right (5)
	Type:         fibonacci8 lfsr
	6502 author:  David Crane
	RAM:          1 byte
	Size:         17 bytes
	Cycles:       30
	Period:       255
	References:   https://samiam.org/blog/20130606.html
	Notes:	This is the right-travelling LFSR from the Atari 2600 
		game Pitfall. It's at the core of the game's algorithmic 
		level generation.
	Sample:       (45) 8a 14 29 52 a5 4a 95 2a ...
	Code:
		  LDA randv0
		  ASL
		  EOR randv0
		  ASL
		  EOR randv0
		  ASL
		  ASL
		  EOR randv0
		  ASL
		  ROL randv0
		  LDA randv0


xorshift16 (6)
	Type:         xorshift16 lfsr
	6502 author:  Veikko
	RAM:          2 bytes
	Size:         17 bytes
	Cycles:       30
	Period:       65535
	References:   http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html
	Notes:	This is an efficient 6502 implementation of the xorshift16
		algorithm.
	Sample:       (2a2a) 0a ad 77 8b 50 37 06 75 ...
	Code:
		  LDA randv1
		  LSR
		  LDA randv0
		  ROR
		  EOR randv1
		  STA randv1
		  ROR
		  EOR randv0
		  STA randv0
		  EOR randv1
		  STA randv1


xhybrid24 (7)
	Type:         hybrid xorshift16+galois8
	6502 author:  (hybrid code) Mike Saarna, (base xorshift16) Veikko
	RAM:          3 bytes
	Size:         34 bytes
	Cycles:       48-50
	Period:       16711425
	References:   
	Notes:	A bit sampling on the xorshift16 upper-byte cranks a galois8
		lfsr forward. This results in an atypical lfsr period. 
		xhybrid24 passes and scores well on most "dieharder" 
		randomness quality checks. This level of rand quality probably 
		isn't needed on 6502 based systems, but it's nice that it can
		be done with relative efficiency.
	Sample:       (010101) f4 c5 d0 ae 75 6b 70 d2 ...
	Code:

		  BIT randv1
		  BVS skipupperlfsr
		    LDA randv2
		    LSR
		    BCC skipuppereor
		      EOR #$B4
		skipuppereor:
		    STA randv2
		skipupperlfsr:

		  LDA randv1
		  LSR
		  LDA randv0
		  ROR
		  EOR randv1
		  STA randv1
		  ROR
		  EOR randv0
		  STA randv0
		  EOR randv1
		  STA randv1

		  EOR randv2


overlap24 (8)
	Type:         ??
	6502 author:  ??
	RAM:          3 bytes
	Size:         38 bytes
	Cycles:       73
	Period:       16777215
	References:   https://wiki.nesdev.com/w/index.php/Random_number_generator/Linear_feedback_shift_register_(advanced)
	Notes:	Has an XOR-feedback that contains only four bits, but by 
		shifting and feeding back 8 bits at once, a more complex 
		overlapped result is obtained.
	Sample:       (010203) 1b 36 2d 45 8a d4 81 43 ...
	Code:
		  LDY randv1
		  LDA randv2
		  LSR
		  LSR
		  LSR
		  LSR
		  STA randv1
		  LSR
		  LSR
		  EOR randv1
		  LSR
		  EOR randv1
		  EOR randv0
		  STA randv1
		  LDA randv2
		  ASL
		  EOR randv2
		  ASL
		  ASL
		  EOR randv2
		  ASL
		  EOR randv2
		  STY randv2
		  STA randv0

riverraid16 (9)
	Type:         ??
	6502 author:  Carol Shaw
	RAM:          2 bytes
	Size:         14 bytes
	Cycles:       27
	Period:       57337
	References:   http://www.bjars.com/source/RiverRaid.asm
	Notes:	"randomHi is very random, randomLo is NOT when more than one
		bit is used, because: randomLo[x+1] = randomLo[x]*2 + 0/1, but
		randomLo is used more often [in the game] [...]" 
			--Thomas Jentzsch
	Sample:       (a814) 0a 05 b6 5b 99 f8 7c 3e ...
	Code:
		  LDA randv1
		  ASL
		  ASL
		  ASL
		  EOR randv1
		  ASL
		  ROL randv0
		  ROL randv1
		  LDA randv1

barrym95838 · Post by **barrym95838** » Thu Jun 01, 2023 3:42 pm

Very nice little collection there, Alex1. Thank you!

Arlet · Post by **Arlet** » Fri Jun 02, 2023 11:24 am

Nice 32 bit random generator, with 7 bytes of state, and 4 bytes of output. Period is guaranteed to be at least 2^48 words, so for all practical purposes will never repeat. The four output bytes are written only once, and not read back, so you can modify the code to put them somewhere else instead of in the RAM array. Note that the random quality is on the low side, but at 20 cycles/byte, it is quite fast. It is possible to shorten the 6-stage ADC/STA sequence at the beginning to reduce footprint, code size, and cycle time, at the cost of lowering the random quality even more.

(I'm playing around with PRNG for Arduino, and it has a very nice SWAP instruction that swaps the high and low nibble of a register. It's very effective in combination with ADC chains to create good randomness. Unfortunately, doing a nibble swap on 6502 is quite expensive, and probably not really worth it)

Code: Select all

    CLC
    LDA #$45
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ADC s+2
    STA s+2
    ADC s+3
    STA s+3
    ADC s+4
    STA s+4
    ADC s+5
    STA s+5
    ADC s+3
    STA o+0 ; first output byte
    ADC s+6
    ASL A
    STA s+6
    ADC s+2
    STA o+1 ; second output byte
    ADC s+6
    ASL A
    STA s+6
    ADC s+4
    STA o+2 ; third output byte
    ADC s+5
    STA o+3 ; fourth output byte
    RTS

owlet code

Alex1 · Post by **Alex1** » Tue Jun 20, 2023 7:38 am

By the way my LFSR64+LCG64 still good after 16TB data...

Code: Select all

RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = core, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 8 megabytes (2^23 bytes), time= 2.9 seconds
  no anomalies in 76 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 megabytes (2^24 bytes), time= 6.5 seconds
  no anomalies in 84 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 12.9 seconds
  no anomalies in 93 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 24.8 seconds
  no anomalies in 99 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 47.7 seconds
  no anomalies in 108 test result(s)

rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 92.1 seconds
  no anomalies in 118 test result(s)

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 180 seconds
  no anomalies in 126 test result(s)

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 355 seconds
  no anomalies in 135 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 706 seconds
  no anomalies in 144 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 1406 seconds
  no anomalies in 151 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 2821 seconds
  no anomalies in 159 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 5661 seconds
  no anomalies in 167 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 11312 seconds
  no anomalies in 173 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 22845 seconds
  no anomalies in 181 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 45338 seconds
  no anomalies in 189 test result(s)

rng=RNG_stdin8, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 91090 seconds
  no anomalies in 195 test result(s)

rng=RNG_stdin8, seed=unknown
length= 512 gigabytes (2^39 bytes), time= 186524 seconds
  no anomalies in 202 test result(s)

rng=RNG_stdin8, seed=unknown
length= 1 terabyte (2^40 bytes), time= 366013 seconds
  no anomalies in 208 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 terabytes (2^41 bytes), time= 729582 seconds
  no anomalies in 213 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 terabytes (2^42 bytes), time= 1470769 seconds
  no anomalies in 218 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 terabytes (2^43 bytes), time= 2981457 seconds
  no anomalies in 222 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 terabytes (2^44 bytes), time= 6061817 seconds
no anomalies in 225 test result(s)

barrym95838 · Post by **barrym95838** » Tue Jun 20, 2023 9:49 am

Arlet wrote:

Unfortunately, doing a nibble swap on 6502 is quite expensive, and probably not really worth it.

http://6502.org/source/general/SWN.html
Eight bytes and 12 cycles, so not terrible. Depends on your definition of "expensive", I suppose.

Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation

Re: Random-number generation