IGNORED

# rand(N) ?

## Recommended Posts

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

##### Share on other sites

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.

##### Share on other sites

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?

##### Share on other sites

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).

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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
bcc next
inc result
next dey
bne mult

```

• 1
• 1
##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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 by Andrew Davie
##### Share on other sites

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

lda #0
sta result
lda #\$7F

bitloop
asl N
bcc nobit

lda rnd   ; get another random
clc
sta result

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 by Andrew Davie
##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

• 1
• 1
##### Share on other sites

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?

##### Share on other sites

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.

##### Share on other sites

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.