It is currently Sat Aug 18, 2018 5:58 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Random number in range
PostPosted: Sun Aug 12, 2018 12:41 pm 
Offline

Joined: Sat Jul 21, 2018 4:17 am
Posts: 5
Hi, I'm trying to get a random number between 3 and 30. First I generate a random number (0-255), then I use AND to trim it to a number between 0-31 and then I add 3 to change the range to 3-34.

Code:
JSR Random
AND #31
ADC #3 ; range from 3 to 34


But how do I account for the four possible numbers that come after 30?


Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 12:47 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10714
Location: Rio de Janeiro - Brazil
I don't think you can properly scale to a non-power-of-two range without using multiplication/division.


Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 12:52 pm 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 335
Code:
retry:
  JSR Random
  AND #31
  CMP #28
  BCS retry
  ADC #3


Last edited by pubby on Sun Aug 12, 2018 12:53 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 12:53 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2200
Location: DIGDUG
I agree with tokumaru. Properly, you would need to do a modulus, which is the remainder of a division.

The upper algorithm here...

http://6502org.wikidot.com/software-math-intdiv

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 12:56 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6596
Location: Canada
There's a few options:

1. Use modulo (rand % 28). This is kind of the "standard" way to range a random integer in higher level langauges or platforms where division is "easy". You will notice that it doesn't divide evenly: 256 / 28 = 9 R 4. However, all this means is that most results happen 9/256 times, and 4 of your results happen a slightly more often 10/256. The primary disadvantage here is that division is a relatively slow operation, but in a lot of cases not that big a deal. Sometimes an iterative subtraction loop is very practical, you don't necessarily even need an "optimized" divide. On the other end of the easy-to-implement spectrum you could also use a lookup table for very fast specific common division, at the expense of some ROM space.

2. Reroll if out of range. This has the unfortunate problem that it takes an unspecified number of iterations, but in practice it's generally mostly 1, rarely 2, almost never 3. If you're doing this make sure your random number generator is guaranteed to produce all values so you don't have the possibility of an infinite reroll.

There are some other options, like using an uneven distribution (e.g. add several power-of-two masked random values), but the two above are the most straightforward, I think.


Edit: ha ha ha 3 short posts covering both these options happened while I was explaining them. ;)


Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 1:11 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20413
Location: NE Indiana, USA (NTSC)
With many RNGs, a multiply is better than a modulo because the upper bits have better quality randomness. So here's how I'd do it, using the mul8_ay routine from Thwaite:
Code:
  jsr rand8bit  ; leaves 8 random bits in A
  ldy #28
  jsr mul8_ay  ; about 150 cycles; leaves high bits in A, low bits in $0000
  clc
  adc #3


Another thing you could try, which I mentioned a month ago, is using your PRNG to shuffle a circular buffer, favoring the least recently used values. Whether that's helpful depends on what exactly you will be using these numbers from 3 to 30 for.


Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 1:24 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6596
Location: Canada
tepples wrote:
With many RNGs, a multiply is better than a modulo because the upper bits have better quality randomness.

This only specifically applies to LCG RNGs. On an LFSR RNG all bits should be equal.

(If you're referring to cc65's LCG RNG I think the entropy of the bits is a bit of a moot point, though. The low bits of the result are already overkill for most purposes.)

The multiply will work either way (and is an interesting way to do it... i.e. this is a fixed point result that you're discarding the low 8 bits of, and the implied round-down is very important behaviour too), but this justification depends on that specific kind of RNG.


Top
 Profile  
 
PostPosted: Sun Aug 12, 2018 6:32 pm 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 385
As I mentioned a month ago, the only fair way to reduce the range of an RNG to a non-power-of-two is to reroll until the number is in range. Everything else will leave some results (slightly) more likely than others.

It's also very simple: just AND, compare and loop. The only downside is that it can sometimes require many rerolls. Keep as little as possible inside the loop (in your example, reduce the range before you add), use a fast RNG, and inline it (so you have a 'roll' function that takes a range, rather than calling the roll function in a loop). But in practice most PRNGs won't generate long series of out-of-range values, and a multiply or modulo is just slow all the time.

Otherwise, the replies above have your options pretty well covered.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group