need assistance with random number generator

[infidelity]

How would I go about creating a very simplistic random number generator, with values in the register in the range from 01-04?

Thank you.

[rainwarrior]

One of the simplest PRNGs to implement is a linear feedback shift register.

http://en.wikipedia.org/wiki/Linear_fee ... t_register
Essentially the operation is a shift with a conditional XOR. You can implement it as narrow or wide as you like, so you might want an 8 or 16 bit version.

You get approximately 1 bit of entropy per iteration, so for a random number from 0-3 call it twice before using the result.

If you just want a quick random number and it's acceptable to have "poor" entropy, you can just call it once and use the result.

Here's an example 8-bit LFSR. The variable _prng_seed can be given any initial value except 0. 0 creates a dead cycle to itself. (Also note that it will never give you a value of 0 for the same reason, but this is not normally a problem since you will likely be masking the result to a smaller range.)

Code: Select all

.proc _prng
    lda _prng_seed
    asl
    bcc :+
        eor #$4D
    :
    sta _prng_seed
    rts
.endproc

Edit: modified due to a problem pointed out by Bogax.

[infidelity]

Many thanks!

[bogax]

One of the simplest PRNGs to implement is a linear feedback shift register.

http://en.wikipedia.org/wiki/Linear_fee ... t_register

Here's the 8-bit LFSR I used in my coltrane.nes project. Any starting value can be used for _prng_seed, and it will output all 256 possible values in a fixed sequence. (Some LFSR implementations can't have a seed value of 0, so be careful which implementation you choose.)

Code: Select all

.proc _prng
    lda _prng_seed
    asl
    bcc :+
        eor #$4D
    :
    eor #$59
    sta _prng_seed
    rts
.endproc

um, it's got two cycles, 55 and everything else (it sticks on 55 instead of 0)

[lidnariq]

I was under the impression that unmodified LFSRs necessarily had a dead (self-recurring) point...

[tepples]

There's a dead point, all right, but you can hit it only if you start out in it.

Take the case of the LFSR used to generate noise in the NES APU. You never happen to start in such a state for the long sequence. It is possible to switch to the short sequence at just the right time that it ends up stuck, but briefly switching to the long sequence for a few periods and then switching back will always unstick the short sequence.

[rainwarrior]

Ack! Thanks Bogax!

Sorry about the confusion. It'd been a while since I wrote the code and for some reason I mistakenly remembered it as having a 256-length sequence instead of 255. I don't know why I thought that, I dug up my test logs from the time and they clearly state it has a sequence length of 255, so I know I was aware of it when I wrote it.

I've simplified the example so that the dead spot is at 0, rather than 55. (The XOR with $59 was merely an aesthetic thing to break up certain sequences.)

[Quietust]

You linked to the Wikipedia article, but what you've implemented isn't an LFSR by any definition I've ever seen - where exactly did you get it from?

An 8-bit LFSR requires XORing four different bits in order to get maximal length, while a number of other lengths (including 7, 15, 23, and 31) only require 2 bits.

Here's code for an actual 31-bit LFSR - it's not particularly fast, but the output is fairly good. As any LFSR, it generates randomness one bit at a time, and this particular one allows passing a number of bits to generate (1-8):

Code: Select all

.proc getrandom
	STA random+4
	TXA
	PHA
	LDX random+4
	LDA #$00
	STA random+4
	LDA #$08
loop:	BIT random+3
	BVS t1
	BNE t2
	BEQ t3
t1:	BNE t3
t2:	SEC
	BCS t4
t3:	CLC
t4:	ROL random+0
	ROL random+1
	ROL random+2
	ROL random+3
	ROL random+4
	DEX
	BNE loop
	PLA
	TAX
	LDA random+4
	RTS
.endproc

Shrinking this one down to 15 bits is fairly straightforward, and there's probably plenty of room for optimization as well.

[rainwarrior]

You linked to the Wikipedia article, but what you've implemented isn't an LFSR by any definition I've ever seen - where exactly did you get it from?

It's identical in operation to the Galois LFSR described in the wikipedia article. What is your definition of LFSR?

An 8-bit LFSR requires XORing four different bits in order to get maximal length, while a number of other lengths (including 7, 15, 23, and 31) only require 2 bits.

The XOR mask $4D has 4 bits set. If an alternative is desired, all of the following produce a 255-length sequence for the code I pasted: $1D, $2B, $2D, $4D, $5F, $63, $65, $69, $71, $87, $8D, $A9, $C3, $CF, $E7, $F5

[Quietust]

Ah, I must've misunderstood that section - the only LFSRs I've ever used are Fibonacci ones. Never mind.

[tepples]

The difference between the two is analogous to the difference between multiplication by 2 and division by 2 in a finite field. Galois LFSRs run "forward" and Fibonacci LFSRs "backward" (or vice versa if you learned it the other way).

And it's possible to optimize a 16-bit LFSR to generate 8 bits per iteration. Look up Greg Cook's CRC-16: 8 bits in 66 cycles without a huge LUT.

[bogax]

I rather like the Batari BASIC rand16
which justs shifts the two bytes of a
16 bit LFSR in opposite directions then
EORs them together.

Code: Select all

  lda seedhi
  lsr
  rol seedlo
  bcc noeor
  eor #$B4
noeor
  sta seedhi
  eor seedlo

[rainwarrior]

That's a pretty neat one, bogax.