nesdev.org

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.
But how do I account for the four possible numbers that come after 30?

I don't think you can properly scale to a non-power-of-two range without using multiplication/division.

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

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.

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

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.

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.