It is currently Mon Jan 21, 2019 8:59 am

 All times are UTC - 7 hours

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Random number in rangePosted: Sun Aug 12, 2018 12:41 pm

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

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 12:47 pm

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 11094
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

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 12:52 pm

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

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

Top

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 12:53 pm

Joined: Fri May 08, 2015 7:17 pm
Posts: 2391
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

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 12:56 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7111
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

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 1:11 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21005
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

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

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 1:24 pm

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 7111
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

 Post subject: Re: Random number in rangePosted: Sun Aug 12, 2018 6:32 pm

Joined: Thu Aug 20, 2015 3:09 am
Posts: 431
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 8 posts ]

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 1 guest

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

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki