rand(N) ?

[Danjovic]

Does anybody know a good function to generate a random number withing a range delimited by 1 to N  being N not a power of two?

for instance between 1 and 75  or maybe between 1 and 100 ?

 

Thanks

[+Andrew Davie]

53 minutes ago, Danjovic said:

Does anybody know a good function to generate a random number withing a range delimited by 1 to N  being N not a power of two?

for instance between 1 and 75  or maybe between 1 and 100 ?

 

Thanks

If you have a multiply, and a random from 0..255... yes.

C-like pseudocode....

rndN = ((random & 0xFF) * N) >> 8

Essentially, you treat your generic random (0-255) as a fraction from 0 to 1.  When you do the multiply by N, you end up with a 16-bit number whose format is conceptually A.B where A is the whole part and B is the fractional. The shift in the above discards the fractional ,leaving you with a number from 0 to N-1.  I use the above in my CDFJ code regularly. But it does require a multiply.

 

 

 

 

 

 

[Danjovic]

Thanks Andrew! I will try that!

 

I wonder if I discard the numbers above N (picking another in this case), will the probability for numbers below N still equal to each other? 

 

 

[Thomas Jentzsch]

55 minutes ago, Danjovic said:

I wonder if I discard the numbers above N (picking another in this case), will the probability for numbers below N still equal to each other? 

That should be the case, else the generator would have a general bias (even without removing numbers).

[+Andrew Davie]

2 hours ago, Danjovic said:

Thanks Andrew! I will try that!

 

I wonder if I discard the numbers above N (picking another in this case), will the probability for numbers below N still equal to each other? 

 

 

Yeah, don't do that. Potentially infinite delays while you wait for a number in the desired range to be selected. Depending on N and the repeat-cycle of your random generator.

[RevEng]

You just mask first to get a range that's the closest-fitting power-of-two. Worst case you have a range nearly double what you need, and it really doesn't take a lot of iteration to get a pick within the desired range.

[+Andrew Davie]

Had a go implementing a simple solution using the algorithm I described.

Untested, so be warned!

    ; pass y = N (range returned is 0..N-1)
    ; pass rnd = 0..255 random number
    ; result = the calculated random (from 0 to N-1 inclusive)

    lda #0
    sta result
mult  clc
	adc rnd
    bcc next
    inc result
next dey
    bne mult

 

[RevEng]

2 hours ago, RevEng said:

You just mask first to get a range that's the closest-fitting power-of-two. Worst case you have a range nearly double what you need, and it really doesn't take a lot of iteration to get a pick within the desired range.

To quantify this, I ran through a few different LFSRs, and it seems the maximum-iterations you'll encounter with this approach (for the worst-case of throwing away half of the range) is equal to the bits in the LFSR. So worst-case is 16 iterations for a 16-bit LFSR, 8 iterations for an 8-bit LFSR. The average case iterations always seems to be nearly 2, regardless of the LFSR size. (all of which makes intuitive sense)

 

The situation improves the closer your range is to a power-of-two.

 

[Danjovic]

7 minutes ago, RevEng said:

So worst-case is 16 iterations for a 16-bit LFSR, 8 iterations for an 8-bit LFSR.

Thanks! I think that even the worst case this is plainly acceptable for what I have in mind. 

[+Andrew Davie]

 

R(17) = R(16) + R(1)

R(45) = R(32) + R(8) + R(4) + R(1)

R(194) = R(128) + R(64) + R(2)

 

So what I'm thinking with the above is you could hardwire some masking and addition.

If you know N as a preset value... using (2^n)-1 as the mask for each component, then you can do an AND

For example, R(16) --> "and #15" giving 16 possibilities.

So you choose a random range of each of the "1" bits of the N value.

 

so for the first example

R(17) = (rnd & 15) + (rnd & 1)

 

You'd need to call rnd several times, or shift so you were using different bits.

 

; weirdo random 0..16 (inclusive)
; uses R(17) = R(16) + R(1)

  lda rnd
  and #15
  sta result	; = R(16)
  
  lda rnd
  and #2
  lsr			; = R(1), and carry clear

  adc result	; = R(16) + R(1)

; returned value in A

 

Just throwing this up as an alternate method. I have no idea, other than intuition, that it's valid to sum sub-randoms like this.

Its advantages -- fixed time, no multiplies, can be really efficient.  Disadvantage - hardwired for a particular N

 

 

 

Edited March 30, 2022 by Andrew Davie

[+Andrew Davie]

 ; pass N = defines range of random (0..N-1)

  lda #0
  sta result
  lda #$7F
  sta mask

bitloop
  asl N
  bcc nobit

  lda rnd   ; get another random
  and mask
  clc
  adc result
  sta result

nobit  lsr mask
  bne bitloop

; A = random in chosen range

Well, the above is untested but I had fun writing it. The idea is that it starts with a mask of 127, and if bit 7 of N is set, then it effectively adds a random (0-127) to the result. And then for bit 6, it adds a random from (0-63)... right down to bit 0 where it adds a random from (0-1).

It is supposed to work for any N, and sums randoms masked by (2^N)-1, for each on-bit in the N range.

Pretty quick, guaranteed runtime for any given N.

 

I just have a vague suspicion that the concept is faulty -- but I don't yet know why.

Somebody should give this a try

 

 

Edited March 30, 2022 by Andrew Davie

[RevEng]

1 hour ago, Andrew Davie said:

Just throwing this up as an alternate method. I have no idea, other than intuition, that it's valid to sum sub-randoms like this.

Its advantages -- fixed time, no multiplies, can be really efficient.  Disadvantage - hardwired for a particular N

This gives a non-uniform distribution, with the edges of the range getting lower probability. I actually like this particular method for random screen coordinates, as more middle is more likely than the extremes, which can be seen as a feature. See this post for a graphic of the distribution of a 0-159 range.

[+Andrew Davie]

10 minutes ago, RevEng said:

This gives a non-uniform distribution, with the edges of the range getting lower probability. I actually like this particular method for random screen coordinates, as more middle is more likely than the extremes, which can be seen as a feature. See this post for a graphic of the distribution of a 0-159 range.

 

Yes, you are right I think. I wrote a short test and binned the frequency for N=9, over 10 million generated randoms, and got..

[645512, 1262827, 1245957, 1245087, 1244236, 1245984, 1243539, 1246423, 620435]

It's not a gaussian... just a sharp dropoff on the edges. The middle numbers' frequencies look remarkably consistent.

No doubt I've botched the test code

 

 

[+Karl G]

9 hours ago, RevEng said:

To quantify this, I ran through a few different LFSRs, and it seems the maximum-iterations you'll encounter with this approach (for the worst-case of throwing away half of the range) is equal to the bits in the LFSR. So worst-case is 16 iterations for a 16-bit LFSR, 8 iterations for an 8-bit LFSR.

I've always avoided the re roll the dice method before, not knowing how many retries might be needed. Knowing the worst case scenario definitely makes this approach much more viable. 

[RevEng]

Yeah, pretty pleased to quantify that. Plus it was a good excuse to break out lfsr6502 to generate the sequences.

[Danjovic]

Nice way to graphically assess the randomness of an given algorithm! 

The batari basic's embedded rand16 should fit nicely for me.

I understand that the rand16 runs in background, right? Then If I pick a value whenever I press a button It will never repeat a sequence, right?

 

[RevEng]

Thanks!

 

Actually, the bB rand16 gets cranked every time you use it. So something like "myposition = rand & 127" generates assembly code that includes a "jsr randomize" call. It's best practise to seed the generator based on human interaction, like running continuously during a game title screen, so the game will start somewhere unique in the whole sequence.

 

In terms of never repeating, it's worth saying the sequence does repeat after 65535 values, as most 16-bit LFSRs do.

[Danjovic]

2 hours ago, RevEng said:

It's best practise to seed the generator based on human interaction, like running continuously during a game title screen, so the game will start somewhere unique in the whole sequence.

That´s great. I should pick a new value every screen then, but I should only use the random value when I press a button.