Random numbers

[+johnnywc]

Hello all,

 

I'm using the following function to generate a random number:

 

; random # mask
RAND_EOR_8	  =	   $B2

	lda  random			; 3
	lsr					; 2
	bcc  .skipEor0		 ; 2³
	eor  #RAND_EOR_8	   ; 2
.skipEor0
	sta random			 ; 3

 

The distribution seems to be pretty good, but I've had a few instances when the random number is 0 (and all subsequent numbers are 0). Is this normal? Is this code correct? Should I put a check in the code to see if random goes to 0, and if so, reseed? I'm trying to figure out whether I'm inadvertantly setting this to 0 or does it naturally go to 0 sometimes.

 

Thanks!

[djmips]

I think you must be setting it to zero sometimes by accident.

 

Edit: I had this python test code lying around and it prints out the sequence...

 

def lfsr():

reg = 1

for count in range(0,257):

	print count ,hex(reg), hex(reg ^ 255)

	if reg & 1:
		reg = reg >> 1
		reg = reg ^ 0xb2
	else:
		reg = reg >> 1

lfsr()

Edited September 2, 2006 by djmips

[DEBRO]

Hi John,

The distribution seems to be pretty good, but I've had a few instances when the random number is 0 (and all subsequent numbers are 0). Is this normal? Is this code correct? Should I put a check in the code to see if random goes to 0, and if so, reseed? I'm trying to figure out whether I'm inadvertantly setting this to 0 or does it naturally go to 0 sometimes.

There has been talk about this on [stella]. If you set the seed to a non-zero number and you use the routine you mentioned I don't think you should get 0.

 

Eric Ball modified the routine to check for zero and if the value was zero jump to the EOR. You can see this in the [stella] Random Numbers thread.

 

David Galloway posted another version that uses BCS instead of BCC. If you use the BCS version then you don't have to worry about setting the seed to a non-zero number. Doing this doesn't make you numbers "random" as it's value would be based on your RAND_EOR_8 value.

 

As David states, both versions give you a full sequence. The BCS version gives values 0 <= a < 255 and the BCC version gives values 0 < a <=255.

 

Check out the [stella] incoming source thread to see David's explanation.

[+johnnywc]

Hi John,

The distribution seems to be pretty good, but I've had a few instances when the random number is 0 (and all subsequent numbers are 0). Is this normal? Is this code correct? Should I put a check in the code to see if random goes to 0, and if so, reseed? I'm trying to figure out whether I'm inadvertantly setting this to 0 or does it naturally go to 0 sometimes.

There has been talk about this on [stella]. If you set the seed to a non-zero number and you use the routine you mentioned I don't think you should get 0.

 

Eric Ball modified the routine to check for zero and if the value was zero jump to the EOR. You can see this in the [stella] Random Numbers thread.

 

David Galloway posted another version that uses BCS instead of BCC. If you use the BCS version then you don't have to worry about setting the seed to a non-zero number. Doing this doesn't make you numbers "random" as it's value would be based on your RAND_EOR_8 value.

 

As David states, both versions give you a full sequence. The BCS version gives values 0 <= a < 255 and the BCC version gives values 0 < a <=255.

 

Check out the [stella] incoming source thread to see David's explanation.

 

Thanks Dennis. The problem my be in the way I seed the number. Right now, after CLEAN_START I do:

 

ldy INTIM

sty random

 

Is it possible for INTIM to be 0 at this point? If so, that would certainly be the issue. The other possibility is that I'm accidentally writing to that location in RAM and setting it to 0.

Edited September 2, 2006 by johnnywc

[DEBRO]

Hi John,

Thanks Dennis. The problem my be in the way I seed the number. Right now, after CLEAN_START I do:

 

ldy INTIM

sty random

 

Is it possible for INTIM to be 0 at this point?

You always have the possibility of INTIM being zero even if you set it before CLEAN_START. I don't think CLEAN_START sets the timer values. Doesn't CLEAN_START only do ZP? Either way the read could come back with zero (remember it's sort of random )

 

With that being said it would be safer for you to use the BCS method. This would eliminate the problem with INTIM being a zero value. Of course you lose 255 as a value but if that's not an issue I'd use the BCS method. Sure wish I would have used the BCS method for Climber 5

[+johnnywc]

Hi John,

Thanks Dennis. The problem my be in the way I seed the number. Right now, after CLEAN_START I do:

 

ldy INTIM

sty random

 

Is it possible for INTIM to be 0 at this point?

You always have the possibility of INTIM being zero even if you set it before CLEAN_START. I don't think CLEAN_START sets the timer values. Doesn't CLEAN_START only do ZP? Either way the read could come back with zero (remember it's sort of random )

Yes - clean start only clears ZP. z26 shows that the value in INTIM is random at the point I'm seeding it. I just need to make sure it's not 0. Funny how sometimes the obvious things are the hardest to find..

 

With that being said it would be safer for you to use the BCS method. This would eliminate the problem with INTIM being a zero value. Of course you lose 255 as a value but if that's not an issue I'd use the BCS method. Sure wish I would have used the BCS method for Climber 5

 

Well, bsc sounds better to me as you save a few bytes since you don't have to check to see if your seed is 0. You mentioned that using bsc is not truly random since it depends on the value that you EOR with. What did you mean by that? What's the difference in random numbers between bcc and bcs (besides one doesn't return 0 and one doesn't return 255)?

 

Thanks!

[djmips]

I'll try to summarize some of the features of these type of pseudo random number generators.

 

Using this type of Linear Feedback Shift Register (LFSR) you are getting a psuedo random sequence. The next 8 bit number is always correlated to the previous because you are only generating one new 'random' bit each time. (There is essentially no difference between the bcc or bcs routines in terms of randomness)

 

I have found that for certain game operations, it is better to have a routine that generates n new bits of random data and to use a 16 bit LFSR. So if I need a random # between 0-16 I would call the routine to generate 4 new bits of data.

 

Other types of games can work well with the 8 bit LFSR only generating one new bit per cycle. In fact, it might be an advantage to have the correlation and certainly you can take advantage of the repeatability of the sequnces from a given seed, like the oft cited example in River Raid in which the LFSR output generates the 'level'.

 

In another thread on AtariAge, John Payson (supercat) had his own take on how to effectively remove correlation with a compact routine using two 8 bit LFSR, only one iteration on each and some folding method IIRC. I'm too lazy to search for the thread...

 

- David Galloway (djmips)

 

Edit:

OK - I did a quick search and you may find more interesting tidbits here. Random number generator, not so random?

Edited September 2, 2006 by djmips

[DEBRO]

Hi John,

Well, bsc sounds better to me as you save a few bytes since you don't have to check to see if your seed is 0. You mentioned that using bsc is not truly random since it depends on the value that you EOR with. What did you mean by that? What's the difference in random numbers between bcc and bcs (besides one doesn't return 0 and one doesn't return 255)?

I really shouldn't have said that. There is no such thing as a random number on any computer. They will always be based on something. What I meant by my statement was that the initial set of your random seed would be based on your EOR value (i.e. 0 XOR value = value). You can help this routine a bit by the frequency you call it. Sure the number will repeat after a while but if you call it periodically then the seed could be better.

[DEBRO]

Hi David,

- David Galloway (djmips)

[stella] is calling...come back

[supercat]

In another thread on AtariAge, John Payson (supercat) had his own take on how to effectively remove correlation with a compact routine using two 8 bit LFSR, only one iteration on each and some folding method IIRC. I'm too lazy to search for the thread...

 

It's really very easy. When coding a simple LFSR, one uses ROL or ROR instructions to shift the bits through; swapping directions will not change the output sequence if one also swaps the bits in the value one "EOR"'s with. There is thus no problem using a 16-bit LFSR in which the two halves are shifted in opposite directions. When one needs a "random" number, return the result of EOR'ing the two halves together.

 

If the "EOR" value is properly chosen (I think $DB was okay, but I'm not positive) then any value 0-255 may follow any other value, except that there cannot be two zeroes in a row. If one outputs the result of this munged LFSR as a bitmap, the result will generally look pretty random except for the a sequence of 16 output values where there is only one bit set in the whole LFSR; those will show up as very clear anomolies.

 

The effect of these anomolies may be mitigated by calling the LFSR two or four times for each value output. Do not use three or five times, as some values will be unavailable when using those (the period of the LFSR is 65,535 which is a multiple of 3 and 5).

[supercat]

Well, bsc sounds better to me as you save a few bytes since you don't have to check to see if your seed is 0.

 

Using BCS instead of BCC does not solve the problem of the PRNG getting stuck. It won't get stuck at zero, but it will still get stuck somewhere else. For example, a seed value of $B4 yields a period 255 PRNG, but ($D8/2) xor $B4 is $D8. Using a period of 254, there will be two "oddball" values which will munge into each other.

 

My recommendation is to use an LFSR where zero is the only oddball value, and then deal with that.

[DEBRO]

Hi John,

Using BCS instead of BCC does not solve the problem of the PRNG getting stuck. It won't get stuck at zero, but it will still get stuck somewhere else. For example, a seed value of $B4 yields a period 255 PRNG, but ($D8/2) xor $B4 is $D8. Using a period of 254, there will be two "oddball" values which will munge into each other.

 

My recommendation is to use an LFSR where zero is the only oddball value, and then deal with that.

I wrote a simple program to output values based on the $B2 XOR and I don't see any odd ball situations except for 0 when using the BCC method. The BCS method even shows that 255 is a valid value. Am I missing something?

lfsr_test.zip

[+batari]

In another thread on AtariAge, John Payson (supercat) had his own take on how to effectively remove correlation with a compact routine using two 8 bit LFSR, only one iteration on each and some folding method IIRC. I'm too lazy to search for the thread...

 

It's really very easy. When coding a simple LFSR, one uses ROL or ROR instructions to shift the bits through; swapping directions will not change the output sequence if one also swaps the bits in the value one "EOR"'s with. There is thus no problem using a 16-bit LFSR in which the two halves are shifted in opposite directions. When one needs a "random" number, return the result of EOR'ing the two halves together.

I have used this method successfully - it seems to work quite well. You can seed with any two values except (0,0).

 

randomize
	lda randlo
	lsr
	rol randhi
	bcc noeor
	eor #$B4
noeor
	sta randlo
	eor randhi
	rts

[Thomas Jentzsch]

Here is a good link for which EOR values to use (e.g. 8.txt).

[TROGDOR]

This is a very interesting discussion. I've been using the below algorithm for random numbers in all my games, including Hunt the Wumpus. It was the best algorithm I found after about an hour of web research. Although it has worked reliably, it's wasteful in all respects (4 RAM bytes, extra ROM bytes, and many extra cycles.) I'll play around with the 2 byte implementation mentioned above and see if I can integrate it into my games.

 

Thanks for the info guys.

 

;Random number generator.  Creates random bits, and loads them into A.
;The number of bits desired is passed in through the X register.

RandomBits

  LDA Rand4
  ASL
  ASL
  ASL
  EOR Rand4	  ;new bit is now in bit 6 of A
  ASL
  ASL			;new bit is now in carry
  ROL Rand1	  ;shift new bit into bit 0 of register; bit 7 goes into carry
  ROL Rand2	  ;shift old bit 7 into bit 8, etc.
  ROL Rand3
  ROL Rand4

  DEX
  BNE RandomBits
  LDA Rand1
  RTS

[Heaven/TQA]

on A800 i am using the "standard" way of reading hardware register to get a random value:

 

;***** Pseudo Random Routine
;x=min, y=max, a=random value
get_random 
rand00	stx rand0+1
	sty rand1+1
rand	lda 53770
rand0	cmp #0
	bcc rand
rand1	cmp #0
	bcs rand
	rts

;***** another pseudo random generator
;***** based on random seeds		
_get_Random 
_rand	inc	 rnd2
	lda	 rnd2
	clc
	adc	 rnd1
	adc	 rnd2
	sta	 rnd1
	eor	 rnd2
	sta	 rnd2
	sbc	 rnd0
	sta	 rnd0
	rts

rnd0	dta 0
rnd1	dta 0
rnd2	dta 0

 

the 2nd one is the one i have used in the venus express port and will be used in my role playing game for the map generator.

 

as i am using a lot of "get random in a desired range" can someone give me a nice and better way as the first one with the 2 CMPs? i can not use AND as the ranges are based on the tons of weapons my item generator is creating...

 

would this work? i found this in my toolbox:

 

CLC	; clear carry for add
ADC	#$FF-m; make m = $FF
ADC	#m-n+1; carry set if in range n to m

 

which had to be changed into some longer code than the above? (m-n, $ff-m f.e.)

 

how would you make some range checks?