I used this method, which I called "possession arrow", to simulate a uniform randomizer in versions of LJ65 (then called tetramino) prior to 0.33. In that version, I switched to the LRU system to reduce repetition, following Arika's TGM games that use a conceptually similar system.Kasumi wrote:Seven pieces. He used 3 bits. Seven of the possibilities deal the piece it corresponds to. (1= I, 2 = O, etc.) When the eighth possibility comes up he increments (or decrements) and wraps around a variable and deals the piece that corresponds to the current value of the variable.

## Random Number Generation?

**Moderator:** Moderators

- neilbaldwin
**Posts:**481**Joined:**Tue Apr 28, 2009 4:12 am-
**Contact:**

This question comes up a lot, so I've thought about it some.

I'm not sure I'm analyzing it correctly (and I haven't actually

tested it so take this with agrain of salt )

My thought is to take a random number MOD your range and then

accumulate and hope that the bias accumulates and distributes

itself over the range. (or the bias ends up "diluted" in the

accumulation, depending on how you look at it)

Choose a range of random numbers that's easy to MOD to your target

range.

So eg if you random number generator returns numbers 0-FF,

and you want random numbers in the range 0-1B mask off the lower

five bits (the next higher power of two, and if you start with

a range that's a power of two and MOD for a range thats a power

of two that shouldn't introduce any bias)

MOD that to your target range

Add it to your random number accumulator

MOD that to your target range.

something like this:
Edit:

I forgot to mention you could use the next lesser power of two

to start and save some MODing.

My gut says that the larger the range you start with the better

off you'll be distribution wise.

So it becomes something of a trade off between the size of the range

and the effort spent doing the MOD.

I'd guess that using the next lesser power of two probably

wouldn't make a lot of difference especially if it's close to

your target range.

I'm not sure I'm analyzing it correctly (and I haven't actually

tested it so take this with agrain of salt )

My thought is to take a random number MOD your range and then

accumulate and hope that the bias accumulates and distributes

itself over the range. (or the bias ends up "diluted" in the

accumulation, depending on how you look at it)

Choose a range of random numbers that's easy to MOD to your target

range.

So eg if you random number generator returns numbers 0-FF,

and you want random numbers in the range 0-1B mask off the lower

five bits (the next higher power of two, and if you start with

a range that's a power of two and MOD for a range thats a power

of two that shouldn't introduce any bias)

MOD that to your target range

Add it to your random number accumulator

MOD that to your target range.

something like this:

Code: Select all

```
; return a number in the range 0-1B
; start with a random number 0-FF in a
; myrand needs to be intialized to be in range
; MOD to an easier power of two
and #$1F ; the assumption is if a is random in a range
; that's a power of two this result should be random
; MOD that to the target range
cmp #$1C
bcs ACCUMULATE
sbc #$1B ; biased to account for carry clear
ACCUMULATE
clc
adc myrand
; MOD to the target range
cmp #$1C
bcs SAVE_MYRAND
sbc #$1B ; biased to account for carry clear
SAVE_MYRAND
sta myrand
rts
```

I forgot to mention you could use the next lesser power of two

to start and save some MODing.

My gut says that the larger the range you start with the better

off you'll be distribution wise.

So it becomes something of a trade off between the size of the range

and the effort spent doing the MOD.

I'd guess that using the next lesser power of two probably

wouldn't make a lot of difference especially if it's close to

your target range.

Last edited by bogax on Sat Aug 07, 2010 11:52 am, edited 1 time in total.

Code: Select all

```
random_80:
@retry:
jsr random_256 ; A = random 8-bit value
sec
sbc #80
bcc @done
sbc #80
bcc @done
sbc #80
bcs @retry
@done:
adc #80
rts
```

Code: Select all

```
unsigned char rand80() {
unsigned char raw;
do {
raw = random_256();
} while (raw >= 240);
return raw % 80;
}
```

In a video game or a real-time demo, you want the RNG to terminate within a guaranteed amount of cycles so that you don't overflow frame time. In this case, I'd recommend something similar to possession arrow logic for cases where the base RNG returns 240-255: increment a counter by 16 (mod 80) and then combine that with the low bits of the remainder. Or 3 bits for Y and 3 bits plus an LRU unit for X.blargg wrote:If random_256 is a simple 8-bit LFSR, this routine will always terminate

### Re: Random Number Generation?

Sorry for the necro post, but I didn't see another thread on the topic.

I want to produce a large number of random sequences of the numbers 0-15 where each number must occur exactly once. A 4-bit LSFR would make the sequence predictable very quickly, and an 8-bit LSFR (which would be much less predictable) doesn't guarantee that any 4 bits I choose (the last 4 out of 8, for example) do not have the same combination of values in a 16 values long sequence, as far as I know.

One solution could be to run fisher-yates on an array of the numbers I want, where the random number (i.e. the index) is taken from the last 4 bits of an 8-bit LSFR (picking the next value or truncating it should it be out of range) that is periodically seeded by the unknowing player by counting the number of frames passed between certain actions (in this case, pulling the trigger on the Zapper). That should give pretty good randomness, but I could be wrong, and I don't even know whether there's a way I could prove myself right or wrong.

Another solution could be to keep a table of sequences that are chosen from by the aforementioned frame counter, but that seems like a pretty bad idea considering, uh, [grabs a calculator] there are nearly 21 trillion different possible sequences and each sequence would need 8 bytes of memory for storage. So yeah, very bad idea.

So... does anyone feel right away that the 8-bit LSFR + Fisher-Yates solution is also a bad idea, for any reason? In particular, is anyone good enough at math to tell me whether or the sequences that are produced by this method are equally likely to happen, or whether there's a tendency to prefer a particular set of sequences? The delay between trigger pulls is likely to have some kind of normal distribution around 60 frames or so, but other than that... not sure whether I should investigate further or just try it and see how well it works. It's going to be in silico either way.

I want to produce a large number of random sequences of the numbers 0-15 where each number must occur exactly once. A 4-bit LSFR would make the sequence predictable very quickly, and an 8-bit LSFR (which would be much less predictable) doesn't guarantee that any 4 bits I choose (the last 4 out of 8, for example) do not have the same combination of values in a 16 values long sequence, as far as I know.

One solution could be to run fisher-yates on an array of the numbers I want, where the random number (i.e. the index) is taken from the last 4 bits of an 8-bit LSFR (picking the next value or truncating it should it be out of range) that is periodically seeded by the unknowing player by counting the number of frames passed between certain actions (in this case, pulling the trigger on the Zapper). That should give pretty good randomness, but I could be wrong, and I don't even know whether there's a way I could prove myself right or wrong.

Another solution could be to keep a table of sequences that are chosen from by the aforementioned frame counter, but that seems like a pretty bad idea considering, uh, [grabs a calculator] there are nearly 21 trillion different possible sequences and each sequence would need 8 bytes of memory for storage. So yeah, very bad idea.

So... does anyone feel right away that the 8-bit LSFR + Fisher-Yates solution is also a bad idea, for any reason? In particular, is anyone good enough at math to tell me whether or the sequences that are produced by this method are equally likely to happen, or whether there's a tendency to prefer a particular set of sequences? The delay between trigger pulls is likely to have some kind of normal distribution around 60 frames or so, but other than that... not sure whether I should investigate further or just try it and see how well it works. It's going to be in silico either way.

Last edited by Dafydd on Wed Mar 06, 2013 11:25 am, edited 2 times in total.

### Re: Random Number Generation?

What I'd use is a 16-bit LFSR (use Greg Cook's CRC16 from 6502.org) feeding Fisher-Yates.

### Re: Random Number Generation?

Is there any reason you can't do a straightforward shuffle of 16 values in RAM? Write an array with 0-15, then step through each of the 16 entries and swap it with a random entry from the array.

### Re: Random Number Generation?

How is a "straightforward" shuffle different from Fisher-Yates? It swaps with any value, not just the remaining ones? How does that ensure I don't get more than one of the same value in the sequence?

EDIT: Oh, wait. I'm stupid. Sorry.

EDIT: Oh, wait. I'm stupid. Sorry.

### Re: Random Number Generation?

Now I'm really confused. When swapping a

*with a[j] in an array of length N, what is the purpose of having 0 <= j <= i (as in Fisher-Yates) when it might as well be 0 <= j <= N-1 (as blargg suggests)? It should have something to do with breaking the (un-)bias, but I don't know for sure.*### Re: Random Number Generation?

In theory, there's a bias in the case of 0 <= j < N. Proof: There are N! distinct permutations after the algorithm. With 0 <= j <= i, there are also N! distinct paths to these permutations. But with 0 <= j < N, there are N^N equally distributed paths. Because N! does not generally divide N^N (example: N = 3; 3! = 6 does not divide 3^3 = 27), these states don't all have the same number of paths to them; therefore bias.

But in practice, I dare someone else to prove that this bias is any more noticeable than the limitation that a CRC16 can generate only 65536 of the 2.1×10¹³ distinct permutations.

But in practice, I dare someone else to prove that this bias is any more noticeable than the limitation that a CRC16 can generate only 65536 of the 2.1×10¹³ distinct permutations.

### Re: Random Number Generation?

I drew a trinary tree of possibilities for the array of [1, 2, 3] (i.e. length 3) and came up with 27 leaves, distributed like so:

123 x 4

132 x 5

213 x 5

231 x 5

312 x 4

321 x 4

I came up with a more elegant explanation, but tepples beat me to it.

Anyway, in this particular case, as tepples suggests, I think I'll run with blargg's version, because it's much easier to implement, and because the bias isn't going to matter, especially since the input will be shuffled from last time anyway.

Thanks, guys!

123 x 4

132 x 5

213 x 5

231 x 5

312 x 4

321 x 4

I came up with a more elegant explanation, but tepples beat me to it.

Anyway, in this particular case, as tepples suggests, I think I'll run with blargg's version, because it's much easier to implement, and because the bias isn't going to matter, especially since the input will be shuffled from last time anyway.

Thanks, guys!

### Re: Random Number Generation?

I used ARCFOUR, running several times per frame when nothing else is doing, and including the microphone if it is available.

[url=gopher://zzo38computer.org/].[/url]

- TmEE
**Posts:**741**Joined:**Wed Feb 13, 2008 9:10 am**Location:**Estonia, Rapla city (50 and 60Hz compatible :P)-
**Contact:**

### Re: Random Number Generation?

This is not exactly NES stuff but in my MD game "Glass Breaker" I used this to create some garbage for random enemy business :

It takes quite little time and provided me adequate enough output for the things I needed.

I did not really spend much time on, just arranged some instructions until I got satisfying result...

Code: Select all

```
MOVE.W (GARBAGE), D0
MOVE.W D0, D1
NOT.W D1
ROR.W #3, D0
EOR.W D1, D2
ADD.W D1, D0
ROL.W #7, D1
ADD.W D1, D0
EOR.W D2, D0
MOVE.W D0, (GARBAGE)
```

I did not really spend much time on, just arranged some instructions until I got satisfying result...