This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Quality of the CC65 randomizer

Quality of the CC65 randomizer
by on (#174868)
Would you say that the randomizer of CC65 is a good one?
https://github.com/cc65/cc65/blob/maste ... mon/rand.s

My problem is: I have a character in a game that has a 3 out of 8 chance to do the motion where it is attackable.

My call is basically this:
Code:
/* 3 out of 8 chance
   (random values can go from 0-7)
   to be attackable. */
if ((rand() & 0x07) < 3)
    PrepareMovementAttackable();

/* If non-attackable,
   the movement is chosen by a
   1 to 1 (i.e. 1 out of 2) chance. */
else if ((rand() & 0x01) == 0)
    PrepareMovementNonAttackable1();
else
    PrepareMovementNonAttackable2();

But the attackable movement is triggered quite rarely.

Yesterday, the character did a non-attackable movement probably 10 times in a row before I finally gave up.
(In the moment, I only have one distinct non-attackable movement, so I couldn't check in how much that second random call switched between both alternatives.)

Is this normal? Or is the randomizer crap?
Re: Quality of the CC65 randomizer
by on (#174870)
I would say it's normal. A random number generator does not try for an even distribution of values. It tries for random values. It does not try to flip heads only half the time. It could flip heads 10 times in a row.

If that is not desirable you can use a variable so that it doesn't do the non-attackable movement more than X times in a row even if the random number generator says that's what it should do.
Re: Quality of the CC65 randomizer
by on (#174871)
I don't see a call to srand() anywhere. Maybe that's partially the problem? (Normally with libc you only call this function once)

But in general, I can't see how a "generic rand()" is going to be "extremely random". A per-system (and/or per-architecture) implementation would be needed. There should be several threads here on the forum of how people go about getting "random data" in their NES games. In fact, here's a great one.
Re: Quality of the CC65 randomizer
by on (#174873)
Kasumi wrote:
I would say it's normal. A random number generator does not try for an even distribution of values. It tries for random values. It does not try to flip heads only half the time. It could flip heads 10 times in a row.

Sure, but I had to struggle with this for a few times now. It's never that the attackable movement comes too often. It's always the non-attackable that is much more frequent. (But the attackable stuff does appear from time to time.)

Kasumi wrote:
If that is not desirable you can use a variable so that it doesn't do the non-attackable movement more than X times in a row even if the random number generator says that's what it should do.

Sure, I can do this when the randomizer is definitely working correctly. But first I need to be sure that the randomizer itself isn't faulty.

koitsu wrote:
I don't see a call to srand() anywhere. Maybe that's partially the problem?

You don't see a function head either, do you? Which means it was just a code snippet and not a fully-working example. So, why do you think that the srand function should be anywhere near the movement function of one specific character?

koitsu wrote:
But in general, I can't see how a "generic rand()" is going to be "extremely random".

It doesn't need to be extremely random, but the one that I'm using still seems a little off.

koitsu wrote:
There should be several threads here on the forum of how people go about getting "random data" in their NES games.

If I'm not even sure whether one specific randomizer works correctly, in how far would it help me to have 10 more randomizers (unconfirmed ones, that is) that people posted in various forum threads?
Re: Quality of the CC65 randomizer
by on (#174875)
Here's another older thread about RNGs: viewtopic.php?f=2&t=9598. One trick shown there is that you can keep running the RNG in your VBlank poll loop, which will add an ounce of randomness to the mix since the poll time typically varies.

I know linear congruential RNGs, often used on modern platforms for rand(), have widely documented problems with randomness if you use modulo (or bitwise AND) to limit their range. But cc65's implementation is probably not a LCG because that would require a multiplication.

If you want some data, you can quite easily test the implementation by using the "sim65" target of cc65. Just generate some numbers with rand() (possibly with some additional masking), print with printf(), and look at the results in a spreadsheet program or whatever floats your boat.

EDIT: Turns it out it is an LCG in ca65, just with a multiplier (0x01010101) that allows an efficient implementation.
Re: Quality of the CC65 randomizer
by on (#174876)
Even if it's not perfect, I'm quite content with Shiru's implementation in neslib. Have you tried?
Re: Quality of the CC65 randomizer
by on (#174880)
I think this is another example of 'humans don't understand the concept of randomization'

http://www.dailymail.co.uk/home/moslive ... stand.html

Like when you tell an ipod to shuffle, but then get mad when it plays two songs from the same artist in a row.

If you want a hard 3 times out of 8, have it randomly pick from SETS of 8 (pre-shuffled), where each set has exactly 3 in it (but in a different order).
Re: Quality of the CC65 randomizer
by on (#174881)
Quote:
Like when you tell an ipod to shuffle, but then get mad when it plays two songs from the same artist in a row.

Actually, some shufflers picks the same song twice, which sucks a bit.
Re: Quality of the CC65 randomizer
by on (#174882)
Some game designs make an enemy invulnerable at random times, make no attempt to ensure an occasional vulnerable state, and give the player no way to bypass the encounter. These games have a flaw that the invulnerable state may last too long if the player. A Luck-Based Mission is rarely fun.

If you want short-term randomness but don't want a long-term string of the same result, I recommend using the least recently used (LRU) algorithm to modulate the output of your RNG. You store a list of all outcomes sorted by how recent they are. Then you choose one closer to the front of the list. For example, if you have two outcomes, with 3/8 probability for outcome A and 5/8 probability for outcome B, you toss three A's and five B's into a list. Then you randomly choose one of the four elements at the head of the list, move it to the back, and move all elements after it forward one space.

Tetris the Grand Master uses "history with rerolls" (similar to LRU) to determine which piece to deal next. Thwaite uses LRU to select targets for enemy missiles, and RHDE uses LRU to for the same thing as TGM.

Ninja'd:

Dougeff describes a different randomizer, which EA Games and the Tetris fan community have referred to as the "bag" method. Fill the list with the three A and five B. Then each time, select a random element from that list and remove it. Once the set is empty, refill it with the original set. Most Tetris games since about 2001 use a bag of all seven pieces to address past concerns of an "I drought" (not receiving the straight "I" shaped piece for an extended period) wrecking one's game. Occasionally, as Bregalad alludes, you get two of a piece in a row when one bag ends with a particular piece and the next starts with the same piece. This has caused some TGM fans to refer to bag as the "SZSZ" randomizer, based on a perceived tendency to allow clumps of the S and Z pieces near the boundary between two bags. LRU allows the occasional drought but is less likely to allow brief floods.

The practical problem with bag on a 6502 is that selection without replacement from a set of variable size needs either multiplication with a variable multiplier or modulo with a variable divisor. With LRU, you can tune the length of the head to always be a power of two, allowing (fast) shifts and ANDs to select an outcome.

If you're fine with results repeating themselves after about 32000 or so steps, you can use Greg Cook's fast implementation of CRC16 to generate eight pseudorandom bits quickly. And srand(time(NULL)) won't work on any pre-Dreamcast console, as they lack a real-time clock. Instead seed it based on the time from power on to the player pressing Start.
Re: Quality of the CC65 randomizer
by on (#174884)
thefox wrote:
I know linear congruential RNGs, often used on modern platforms for rand(), have widely documented problems with randomness if you use modulo (or bitwise AND) to limit their range.

Why should there be a problem with it as long as the range isn't limited in the randomizer's value itself, but only with the returned copy?
Or do you mean that, for example, values where the third bit from the right is a 1 appear less often than values where the third bit from the right is a 0, so that it shouldn't be used for getting values from 0 to 7 since it will mostly produce values from 0 to 3 since the highest bit is mostly 0?

I guess I really need to write a test program: Generating numbers from 0 to 15, then using the sprite tiles to check how many of them have been created within a certain loop.


na_th_an wrote:
Even if it's not perfect, I'm quite content with Shiru's implementation in neslib. Have you tried?

No. As I said, this is not about trying out a dozen randomizers that I happen to come by, nor do I want to implement some specific algorithm myself. I want to make sure whether the randomizer in CC65 has any specific issues, so that I need to use another one.

tepples wrote:
And srand(time(NULL)) won't work on any pre-Dreamcast console, as they lack a real-time clock.

Sure, I know that of course.
Re: Quality of the CC65 randomizer
by on (#174885)
dougeff wrote:
I think this is another example of 'humans don't understand the concept of randomization'

This is not about understanding or not understanding randomization. This is about the the fact that randomizers in programs don't create truly random numbers, but use a mathematical algorithm and I get a bit suspicious when there's a very large bias towards a certain outcome.

But as I said, I'll do some tests with the randomizer in CC65 and post the results here later.
Re: Quality of the CC65 randomizer
by on (#174894)
DRW wrote:
koitsu wrote:
There should be several threads here on the forum of how people go about getting "random data" in their NES games.

If I'm not even sure whether one specific randomizer works correctly, in how far would it help me to have 10 more randomizers (unconfirmed ones, that is) that people posted in various forum threads?

You seem to be referring directly to this other thread where you asked a very similar question?

rand.s is a linear congruential generator, which is the same kind of PRNG that a lot of C standard libraries use.

If you want to test how good a random number generator is, just write a program to test it. You seem to be interested in whether results happen with even probability, and whether you're getting too many of a particular value in a row. Here's some statistics on a million iterations of rand.s:
Code:
rand() % 2 statistics:
         0 happened     499999 times, average run      1.984
         1 happened     500001 times, average run      1.985
rand() % 8 statistics:
         0 happened     125001 times, average run      1.143
         1 happened     124999 times, average run      1.143
         2 happened     125001 times, average run      1.143
         3 happened     124998 times, average run      1.143
         4 happened     124998 times, average run      1.143
         5 happened     125000 times, average run      1.143
         6 happened     125000 times, average run      1.143
         7 happened     125003 times, average run      1.143

So... looks perfectly fine; this is as good a result as I could hope from any PRNG, for these particular tests. You can try other random number generators if you're interested. Any good one should perform in a similar way, really. Most PRNGs will exhibit some kind of flaw if you throw the right test at it, but a lot of usage won't be affected by the flaw in a relevant way.

The test program is attached, so that you can verify my implemenation, but also so that you can modify and try it with other random number generators or other tests, if you like.

Edit: I realized later, that lower bits are independent of higher ones and the implementation unnecessarily discards 8 bits, so "rand() & 1" has an unfortunate sequence length of only 512 (9 bits), and "rand() % 8" only 2048 (11 bits), for example, so despite having normal frequency of bits, they are badly repetitive.


Edit: Python scripts were later disallowed on this forum. Uploading a ZIP with what I think was the original script.
Re: Quality of the CC65 randomizer
by on (#174895)
Code:
def rand():
    global seed
    seed *= 0x01010101
    seed += 0x31415927
    seed &= 0xFFFFFFFF
    return (seed >> 8) & 0x7FFF

Clever. I hadn't thought to use 16843009 as the multiplier for an LCG. I can see how it was chosen for ease of computation; it may be one of the few LCGs practical on a 6502. But has anyone done spectral tests on it? A spectral test determines longer-term correlations among elements in the LCG's sequence.

But if it's shifting right by only 8 ((seed >> 8) & 0x7FFF), it's using bits 22-8 of seed, with bits 31-23 calculated but never affecting anything. I tested the following, and it produces the same sequence with only 3 bytes of state:
Code:
def rand():
    global seed
    seed *= 0x010101
    seed += 0x415927
    seed &= 0x7FFFFF
    return (seed >> 8)


The following (untested) should return the same sequence with slightly fewer cycles. It turns out to be even faster than Greg Cook's CRC16. Thank you for suggesting that I look at it.
Code:
;
; Random number generator
;
; Written and donated by Sidney Cadot - sidney[at]ch[dot]twi[dot]tudelft[dot]nl
; Optimized by Damian Yerrick - pino[at]pineight[dot]com
; May be distributed with the cc65 runtime using the same license.
;
; This implements a linear congruential generator with period 2^23.
; The multiplier in an LCG needs to be congruent to 1 (mod 4),
; and the addend needs to be odd.
; Bits 22-8 are returned because LCGs are known for patterns
; in low-order bits.
;

.export _lcg23_rand, _lcg23_srand

.data

; At main() entry, the program expects srand(1) to have been called.
; Initialize the seed as if so.
rand: .byte 1, 0, 0
rand_addend = 4282663

.code

;;
; int lcg23_rand(void);
;
; Clocks the LCG using the iteration
;     seed[n+1] = ((seed[n] * 65793) + 4282663) & ((1<<23) - 1)
; @return bits 22-8 of seed.
.proc _lcg23_rand
  ; Multiply by 0x10101: 22 cycles
  clc
  lda rand+0
  adc rand+1
  sta rand+1
  adc rand+2
  sta rand+2

  ; Add 0x415927: 34 cycles
  clc
  lda rand+0
  adc #<rand_addend
  sta rand+0
  lda rand+1
  adc #>rand_addend
  sta rand+1
  lda rand+2
  adc #^rand_addend
  and #$7F
  sta rand+2
 
  ; Get return value in XXAA: 6 cycles + 6 for RTS
  tax
  lda rand+1
  rts
.endproc

;;
; void lcg23_srand(unsigned int seed);
;
; Sets the state of the LCG to a particular value.
; Only 1/256 of states are reachable from this function.
.proc _lcg23_srand
  sta rand+0
  stx rand+1
  lda #0
  sta rand+2
  rts
.endproc
Re: Quality of the CC65 randomizer
by on (#174904)
tepples wrote:
But has anyone done spectral tests on it? A spectral test determines longer-term correlations among elements in the LCG's sequence.

Here's a quick X/Y plot of 9000 iterations of rand() % 256:
Attachment:
File comment: 9000 iterations of cc65's rand() plotted as X/Y pairs modulo 256.
cc65_256_9000.png
cc65_256_9000.png [ 11.33 KiB | Viewed 6472 times ]


Specifically a spectral test is graphing correlations between successive elements; i.e. can you predict the next output if you knew the last one? All LCGs exhibit planes in spectral tests depending on how you organize it; it's actually a good way to detect and study LCGs, and it's why they aren't cryptographically secure. A "better" LCG has more even distribution (i.e. more planes). cc65's rand() seems pretty good for an LCG, though this visible pattern is a good example why you don't usually want to use an LCG for generating X,Y pairs; it's one of the usage cases that exposes this flaw of the LCG paradigm.

For comparison here's what a "very good" spectral test looks like, from the LFSR PRNG example on the wiki, which DRW doesn't want to use because it was written by a "random" person like me:
Attachment:
File comment: LFSR with 8 bits of entropy
lfsr8_256_9000.png
lfsr8_256_9000.png [ 14.37 KiB | Viewed 6472 times ]


And a "very bad" test, made using the same generator but with the entropy turned down to 1 bit per iteration:
Attachment:
File comment: LFSR with 1 bit of entropy
lfsr1_256_9000.png
lfsr1_256_9000.png [ 2.39 KiB | Viewed 6472 times ]


All three PRNGs from these spectral tests pass the other tests (even distribution of values, even distribution of run lengths) from my previous post, though. Again, whether or not this particular flaw matters depends on how you're using it.


tepples wrote:
But if it's shifting right by only 8 ((seed >> 8) & 0x7FFF), it's using bits 22-8 of seed, with bits 31-23 calculated but never affecting anything.

That seems an oversight worth pointing out to the maintainers of CC65. (Are you on the CC65 mailing list?) I suspect, though, that the better solution would not be to reduce it to a 24-bit PRNG for efficiency, but rather to repair it as a full 32-bit PRNG.
Re: Quality of the CC65 randomizer
by on (#174906)
By the way, if you do a complete cycle with that modulo 256 graph on cc65's rand(), you get 50% coverage of the plane, which is actually very good for an LCG. A "bad" LCG would have them pile up in fewer planes.

Again, you could be using other PRNGs, but for the question of how good the output of CC65's is, I'd say so far it looks pretty good. Probably no worse than most C library implementations of rand().

Edit: eventually discovered the low bits have poor sequence length, keep reading.
Re: Quality of the CC65 randomizer
by on (#174908)
rainwarrior wrote:
tepples wrote:
But if it's shifting right by only 8 ((seed >> 8) & 0x7FFF), it's using bits 22-8 of seed, with bits 31-23 calculated but never affecting anything.

That seems an oversight worth pointing out to the maintainers of CC65.

Issue filed, citing this very discussion.

Quote:
(Are you on the CC65 mailing list?)

I either am or was, though I've never been a fan of mailing lists, instead preferring web-based discussion (or even Usenet back when it was popular).

Quote:
I suspect, though, that the better solution would not be to reduce it to a 24-bit PRNG for efficiency, but rather to repair it as a full 32-bit PRNG.

I provided both options in my post.
Re: Quality of the CC65 randomizer
by on (#174910)
Continuing the spectral tests, its planes in a proper 3D plot are fairly dense (hard to show as a picture here, you need to look at it from many angles to see). It looks like a nice healthy LCG to me.

Anyhow, basically I think this is a good PRNG. I don't see any particular deficiencies in the quality of the output, understanding that it's accidentally a 24-bit PRNG instead of a 32-bit PRNG. ;P

Edit: I overlooked a flaw in that the low bits have poor sequence length. keep reading.
Re: Quality of the CC65 randomizer
by on (#174911)
Replacing:
Code:
return (seed >> 8) & 0x7FFF

With:
Code:
return (seed >> 16) & 0x7FFF

The results of this actually look better than the previous one too, at least from my current tests.
It covers the whole mod 256 plane, and doesn't demonstrate patterns like the current version.

For comparison:
Attachment:
File comment: rand() using bits 16-30 instead, mod 256 plot
cc65b_256_9000.png
cc65b_256_9000.png [ 14.1 KiB | Viewed 2416 times ]


For a more valid spectral test, expanding up to 32768/32768 they both seem to have a similar number of planes in that larger space. It's just less patterned in this simplified mod 256 test.
Re: Quality of the CC65 randomizer
by on (#174913)
tepples wrote:
Code:
def rand():
    global seed
    seed *= 0x01010101
    seed += 0x31415927
    seed &= 0xFFFFFFFF
    return (seed >> 8) & 0x7FFF

If this actually works, then it is incredibly clever !! However, usually PRNG have a complicated number as a multiplicator and a simple low number as an adder. So I am kind of doubtful this works so well.

Kinda off-topic, but in my game I use a PRGN that Blargg posted once, and even though it was later proven to suck (*), it is good enough for my game. It was just a small loop and only uses the accumulator and the stack and a couple of temp variables.

(*) The distribution itself was even, however, the transition distribution was not good.
Re: Quality of the CC65 randomizer
by on (#174914)
Bregalad wrote:
If this actually works, then it is incredibly clever !! However, usually PRNG have a complicated number as a multiplicator and a simple low number as an adder. So I am kind of doubtful this works so well.


I don't see anything glaringly wrong with their factorization...

0x01010101 = 16843009 = 257 * 65537
0x31415927 = 826366247 = 7 * 118052321

What's the source of your intuition that a "simple low number" makes a better adder? Do you think my assessment is incorrect?

This doesn't seem to agree with your intuition, either:
https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use
Re: Quality of the CC65 randomizer
by on (#174939)
Quote:
This doesn't seem to agree with your intuition, either: https://en.wikipedia.org/wiki/Linear_co ... common_use

That's precisely my "source". Quite a few of them have '1' as "increment".
Re: Quality of the CC65 randomizer
by on (#174940)
Bregalad wrote:
Quite a few of them have '1' as "increment".

1 is an acceptable value to add, but it's not really a better one for quality of randomness, in any way that I'm aware of (but not necessarily worse; it's all about the right combo of numbers). I think it's common because of efficiency, not randomness (e.g. platforms with a good way to multi-byte increment). You'll notice some even use 0 instead; do you think they are better or worse than the ones that use 1? ;)

It's important that all these generators are not returning the low bits, because they're less "random" than the upper bits. The low bits are acting as a buffer to build up entropy as stuff propagates to the higher bits.
Re: Quality of the CC65 randomizer
by on (#175166)
As a follow-up, because I'm looking at various implementations again, the performance of rand.s is actually quite good, potentially. If you move the seed variable to the zeropage, fix the discarding of the high byte, and just output 8-bits, it becomes pretty fair to compare it against the LFSR that I was using as an example for the spectral test. Some rough efficiency estimates:

32-bit:
  • rand.s: 69 cycles, 41 bytes
  • naive-LFSR: 217 cycles, 23 bytes
  • unrolled-LFSR: 183 cycles, 79 bytes

16-bit:
  • rand.s: 53 cycles, 29 bytes
  • naive-LFSR: 137 cycles, 19 bytes
  • unrolled-LFSR: 103 cycles, 47 bytes

I think is is actually a pretty good quality generator, with a good balance of speed vs entropy, at least in the 8-bit case. If you need less than 8 bits at a time, you can certainly get efficiency savings with the LFSR, but for a simple generic 8-bit generator I think it's very nice indeed.

This LCG's 32-bit version has a very good spectral test, from what I could see, the 24-bit version has a pretty good one (maybe ~7 bits of entropy instead of 8), but it starts to get poor at 16 bits or less. You kind of need enough low bits to "throw away" to build up entropy, so I wouldn't actually recommend this LCG method at 16 or less bits.
Re: Quality of the CC65 randomizer
by on (#175180)
What do you mean with "fix the discarding of the high byte".

Also, when you say "and just output 8-bits", do you mean that one should change the code from
Code:
sta     rand+2
and     #$7f
tax
lda     rand+3
adc     #$31
sta     rand+3
pla
to
Code:
sta     rand+2
ldx #0
lda     rand+3
adc     #$31
sta     rand+3
pla
?
Re: Quality of the CC65 randomizer
by on (#175182)
If you just comment out 4 lines, it will instead return only the high byte (rand+3):
Code:
_rand:  clc
        lda     rand+0          ; SEED *= $01010101
        adc     rand+1
        sta     rand+1
        adc     rand+2
        sta     rand+2
        adc     rand+3
        sta     rand+3
        clc
        lda     rand+0          ; SEED += $31415927
        adc     #$27
        sta     rand+0
        lda     rand+1
        adc     #$59
        sta     rand+1
        ;pha
        lda     rand+2
        adc     #$41
        sta     rand+2
        ;and     #$7f            ; Suppress sign bit (make it positive)
        ;tax
        lda     rand+3
        adc     #$31
        sta     rand+3
        ;pla                     ; return bit 8-22 in (X,A)
        rts


If using this with C, you should leave the AND/TAX though to keep it as a 16-bit value in the correct range for rand().

For extra efficiency you can put "rand" on the zeropage as well.
Re: Quality of the CC65 randomizer
by on (#175183)
Why does writing or omitting PHA and PLA have to do with the question whether the return value is eight or 16 bit?
As far as I understand, PHA puts A to the stack and PLA puts the current stack value back into A.
Now, since the seed is still supposed to work with more than eight bits, why should I comment this out?
If I see it right, the version with PHA and PLA would result in rand+1 being the return value while not using it means rand+3 is the return value. Why is switching from rand+1 to rand+3 preferrable?

Also, using the C compiler means that all return values are 16 bit, even if your return value is only a byte value. So, if I only want an 8 bit return value, shouldn't I set the X register to 0 instead of leaving it untouched?

Besides, what did you mean with "fix the discarding of the high byte".
Re: Quality of the CC65 randomizer
by on (#175187)
DRW wrote:
If I see it right, the version with PHA and PLA would result in rand+1 being the return value while not using it means rand+3 is the return value. Why is switching from rand+1 to rand+3 preferrable?

In a linear congruential generator, more significant bits are is less correlated from one number to the next than less significant bits.

Quote:
Also, using the C compiler means that all return values are 16 bit, even if your return value is only a byte value. So, if I only want an 8 bit return value, shouldn't I set the X register to 0 instead of leaving it untouched?

Yes, but you're not allowed to call it rand(). C specifies that rand() shall return at least 15 bits (RAND_MAX >= 32767). You can make rand8() and specify that it returns values from 0 to 255.

Quote:
Besides, what did you mean with "fix the discarding of the high byte".

The "high byte" or "most significant byte" of a 32-bit number is the byte holding bits 31 through 24. The "low byte" or "least significant byte" is the byte holding bits 7 through 0. Byte 0 is the low byte, and byte 3 is the high byte.

In current rand.s, X contains byte 2 AND $7F, A contains byte 1, and byte 3 (the high byte) never affects the state. A corrected version might have X contain byte 3 AND $7F and A contain byte 2, so that the resulting sequence is less predictable. Or if you're going to rename it, you can just load byte 3 into A and zero out X.
Re: Quality of the CC65 randomizer
by on (#175188)
DRW wrote:
Why is switching from rand+1 to rand+3 preferrable?

As I said prior, the low bits are a buffer for entropy, and the quality of randomness bubbles up from the low bits into the high bits. rand+1 is of lower quality than rand+3.

DRW wrote:
"fix the discarding of the high byte".

tepples pointed this out several posts ago; it's doing all the work of a 32-bit LCG but by returning bits from only rand+1 and rand+2 it's effectively ignoring rand+3 (nothing that happens in rand+3 ever propagates to the lower bytes). It's a bug that reduces it from a 32-bit LCG to a 24-bit one.

DRW wrote:
Also, using the C compiler means that all return values are 16 bit, even if your return value is only a byte value. So, if I only want an 8 bit return value, shouldn't I set the X register to 0 instead of leaving it untouched?

Not untouched, you must explicitly fill X. Either with that TAX that is already there, or sure you could LDX #0 if you want instead, but I don't understand the advantage of that.

The 8 bit return value suggestion is just if you're calling it from assembly only.


Edit: tepples was answering at the same time, sorry for redundancy.
Re: Quality of the CC65 randomizer
by on (#175192)
tepples wrote:
Yes, but you're not allowed to call it rand(). C specifies that rand() shall return at least 15 bits (RAND_MAX >= 32767). You can make rand8() and specify that it returns values from 0 to 255.

Sure. I had my own name for this function anyway.

tepples wrote:
In current rand.s, X contains byte 2 AND $7F, A contains byte 1, and byte 3 (the high byte) never affects the state. A corrected version might have X contain byte 3 AND $7F and A contain byte 2, so that the resulting sequence is less predictable. Or if you're going to rename it, you can just load byte 3 into A and zero out X.

Aren't the four bytes of the seed just there to calculate the next seed?
I mean, the seed is four bytes while the return value is two bytes. So, two of them go unused anyway when it comes to the return value.
Or do you mean that byte 3 not even influences the calculation of the next seed and is totally useless?

rainwarrior wrote:
As I said prior, the low bits are a buffer for entropy, and the quality of randomness bubbles up from the low bits into the high bits. rand+1 is of lower quality than rand+3.

But doesn't that mean that, when I use the original rand() function and I only need a value from 0 to 255 and I use it like this:
rand() & 0xFF
that this would be bad since I only use the not so good bits?

rainwarrior wrote:
DRW wrote:
"fix the discarding of the high byte".

tepples pointed this out several posts ago; it's doing all the work of a 32-bit LCG but by returning bits from only rand+1 and rand+2 it's effectively ignoring rand+3 (nothing that happens in rand+3 ever propagates to the lower bytes). It's a bug that reduces it from a 32-bit LCG to a 24-bit one.
Why does the corrected version in this thread look so totally different with an additional variable called rand_addend and the value 4282663? Is this all necessary or is there a minimum fix that changes the randomizer back to 32 bit, but with only small changes in the code?

rainwarrior wrote:
Not untouched, you must explicitly fill X. Either with that TAX that is already there, or sure you could LDX #0 if you want instead, but I don't understand the advantage of that.

If I use TAX, then I fill X with whatever is in A, right? If the eight bit randomizer function gets called and the return value is stored in an integer, then the integer value isn't a value from 0 to 255, but the high byte and the low byte have an equal value. Why would I want this? That's why I would set X to 0, so that I always get the same value, no matter if my eight bit value gets saved by an eight bit variable or by a 16 bit variable. Or am I missing something here?

rainwarrior wrote:
The 8 bit return value suggestion is just if you're calling it from assembly only.

Well, I changed it to an eight bit return value, even though I use it from C.
The reason: LDX #0 is still shorter than AND #$7F, TAX.
And I included a parameter for the function:
byte __fastcall__ GetRandomNumber(byte bitMask)
Since I never actually need a value from 0 to 255, but more like values from 0 to 3 or 0 to 7 or 0 to 15, I always called GetRandomNumber() & 0x0F or something like that. Now, I included this AND-connection into the function itself, so of course the return value is only one byte.
Re: Quality of the CC65 randomizer
by on (#175193)
DRW wrote:
Or do you mean that byte 3 not even influences the calculation of the next seed and is totally useless?

Bingo.

DRW wrote:
rand() & 0xFF
that this would be bad since I only use the not so good bits?

Yeah, sort of. The LCG is like a nested set of smaller LCGs, increasing in size. rand+0 is really an 8-bit LCG. rand+1 is 16-bit. rand+2 is 24-bit. rand+3 is 32-bit. Each byte has longer and more chaotic cycles than the previous ones (as it combines all the chaos of the previous ones while adding its own). The altered version (i.e. remove pha/pla) I suggested puts the "best" bits right where you want them, in the low byte of your return value.

DRW wrote:
Why does the corrected version in this thread look so totally different with an additional variable called rand_addend and the value 4282663? Is this all necessary or is there a minimum fix that changes the randomizer back to 32 bit, but with only small changes in the code?

WTF are you talking about? The corrected version is literally cut and paste from rand.s on github, and the difference is 4 semicolons.
Re: Quality of the CC65 randomizer
by on (#175194)
DRW wrote:
tepples wrote:
In current rand.s, X contains byte 2 AND $7F, A contains byte 1, and byte 3 (the high byte) never affects the state. A corrected version might have X contain byte 3 AND $7F and A contain byte 2, so that the resulting sequence is less predictable. Or if you're going to rename it, you can just load byte 3 into A and zero out X.

Aren't the four bytes of the seed just there to calculate the next seed?
I mean, the seed is four bytes while the return value is two bytes. So, two of them go unused anyway when it comes to the return value.
Or do you mean that byte 3 not even influences the calculation of the next seed and is totally useless?

Correct, in the version of rand.s at the HEAD on GitHub. Byte 0 feeds into future values of bytes 1 and 2, but byte 3 doesn't feed into anything. A corrected version of this subroutine would use byte 3 in some capacity to form the output.

DRW wrote:
rainwarrior wrote:
rand+1 is of lower quality than rand+3.

But doesn't that mean that, when I use the original rand() function and I only need a value from 0 to 255 and I use it like this:
rand() & 0xFF
that this would be bad since I only use the not so good bits?

Correct.

Quote:
Why does the corrected version in this thread look so totally different with an additional variable called rand_addend and the value 4282663? Is this all necessary or is there a minimum fix that changes the randomizer back to 32 bit, but with only small changes in the code?

In theory, each LCG is characterized by three numbers: the modulus (in this case 2^31 or 2^32 for the 31/32-bit version or 2^23 or 2^24 for the 23/24 bit version), the multiplier (in this case 0x01010101 = 16843009 for the 31/32-bit version or 0x010101 = 65793 for the 24-bit version), and the addend (in this case 0x31415927 = 826366247 for the 31/32 bit version or 0x415927 = 4282663 for the 24-bit version). As I understand it, the standard form of specifying an LCG is with the multiplier and addend expressed in base 10 (decimal) rather than base 16 (hexadecimal).

rainwarrior: DRW is referring to my suggested optimized version, not the corrected version. The optimized version has the same behavior as the current rand.s but doesn't calculate the otherwise unused byte 3 at all.
Re: Quality of the CC65 randomizer
by on (#175216)
I have slightly modified the earlier Python script link

It seems the standard deviation of the run length from CC65's routine is significantly different from that of Python's random.randrange for choosing n<2. Namely, it is ~0.95 for the former and ~1.4 for the latter. This doesn't seem to hold for choosing n<N where N is >2.

This could be potentially relevant as the length of the runs will be slightly less varied.
Re: Quality of the CC65 randomizer
by on (#175220)
This is the LCG I proposed by the minimal removal of pha/pla:
Code:
return ((seed >> 8) & 0x7F00) | (seed >> 24)

Since the flow of information in the LCG only goes from low bits to higher bits, and never the other way, if you're looking at just the lowest bit from the original rand.s, it's really only a 9-bit LFSR. So... I think that would explain a low deviation. There's only so much variation you can get from a sequence length of only 512.


...actually realizing this, that means that probably the most commonly used bits in rand(), e.g. things like "rand() & 1" or "rand() & 3" are actually relatively short sequences (only a bit or two better than an 8-bit PRNG). With that in mind, the existing form of rand.s is actually somewhat poor, despite giving passable results in other tests. :S The proposed revision does not suffer from this problem at all though.
Re: Quality of the CC65 randomizer
by on (#175222)
tepples wrote:
As I understand it, the standard form of specifying an LCG is with the multiplier and addend expressed in base 10 (decimal) rather than base 16 (hexadecimal).

There's nothing particularly meaningful about base 10 here. It offers no insight into the (inherently binary) implementation, and neither number has 2 or 5 as a factor, so base 10 has nothing at all to contribute to their understanding.

Base 16 on the other hand gives me 2 numbers that I can take a glance at and know exactly why they exist and what they're going to be doing in this program. The multiplier's design around 8-bit structure is obvious, and the adder is a whimsically chosen "base 10 pi digits expressed in base 16, rounded up so that it's odd". There's a huge comprehension advantage with hexadecimal here.

Converting them back to base 10 hides all of those things, obfuscating them into essentially "random" looking numbers. I can see why DRW was confused by them.
Re: Quality of the CC65 randomizer
by on (#175223)
rainwarrior wrote:
DRW wrote:
Or do you mean that byte 3 not even influences the calculation of the next seed and is totally useless?

Bingo.

But in this case, why is it a good idea to remove PLA and PHA to get rand+3 as the return value if this is some value that never really influences anything (at least in the unaltered version)? Wouldn't it be a bad idea to use it since it basically stands for itself and only influences itself?
Re: Quality of the CC65 randomizer
by on (#175224)
DRW wrote:
rainwarrior wrote:
DRW wrote:
Or do you mean that byte 3 not even influences the calculation of the next seed and is totally useless?

Bingo.

But in this case, why is it a good idea to remove PLA and PHA to get rand+3 as the return value if this is some value that never really influences anything (at least in the unaltered version)? Wouldn't it be a bad idea to use it since it basically stands for itself and only influences itself?

No. You're looking for a random number. More influences = more sources of randomness. The highest bit is influenced by every other bit below it. That's the one you want to use most. The most influenced is best, not the most influencing.

The bit that influences the most is bit 0 of rand+0. Watch it iterate as it flips back and forth with each call. 0->1->0->1->0->1->0->1... never deviating. It would be the worst thing to use for randomness.
Re: Quality of the CC65 randomizer
by on (#175225)
O.k.

When I'm home I'll rewrite my copy of the random function to include the optimizations and include all the stuff that I need. Then I'll post the final version.

One last thing:
rainwarrior wrote:
DRW wrote:
Why does the corrected version in this thread look so totally different with an additional variable called rand_addend and the value 4282663? Is this all necessary or is there a minimum fix that changes the randomizer back to 32 bit, but with only small changes in the code?

WTF are you talking about? The corrected version is literally cut and paste from rand.s on github, and the difference is 4 semicolons.

tepples wrote:
rainwarrior: DRW is referring to my suggested optimized version, not the corrected version. The optimized version has the same behavior as the current rand.s but doesn't calculate the otherwise unused byte 3 at all.

Is your version (i.e. the one that was only slightly changed, not tepples' that has some more changes) a 32 bit LCG or a 24 bit LGC now?
If it's still the 24 bit one, what is the minimum change that I have to do to convert this to a 32 bit LGC?
Re: Quality of the CC65 randomizer
by on (#175244)
Yeah, just delete pha/pla and it's golden.
Re: Quality of the CC65 randomizer
by on (#175256)
O.k., the following code is the randomizer, altered according to your suggestions as well as my specific needs.

Can you please check if everything is still correct?

The randomizer is supposed to be 32 bit, but the return value is only an 8 bit value.

These are the function prototypes in C:
Code:
void __fastcall__ InitializeRandomizer(unsigned int seed);
unsigned char __fastcall__ GetRandomNumber(unsigned char bitMask);


The bit mask is there to shorten the return value. The value will get AND-connected with the bit mask (of course, only the temporary value in A gets AND-connected, not rand+3 itself), so that I can specify that I want only a value from 0 to 3 or from 0 to 15 etc.

Since I don't have a DATA segment in my game, the whole "If you don't call srand before rand, then rand has to behave as if srand was called with the value 1" is ignored. In my game, I make sure that no random number gets created before the seed was initialized. (Would there even be a problem in this implementation if you call the randomizer if the seed is 0?)

Code:
.zeropage

        rand:    .res 4
        bitMask: .res 1

.code

_GetRandomNumber:

        sta     bitMask

        clc
        lda     rand+0
        adc     rand+1
        sta     rand+1
        adc     rand+2
        sta     rand+2
        adc     rand+3
        sta     rand+3

        clc
        lda     rand+0
        adc     #$27
        sta     rand+0
        lda     rand+1
        adc     #$59
        sta     rand+1
        lda     rand+2
        adc     #$41
        sta     rand+2
        lda     rand+3
        adc     #$31
        sta     rand+3

        and     bitMask
        ldx     #0
        rts


_InitializeRandomizer:

        sta     rand+0
        stx     rand+1
        lda     #0
        sta     rand+2
        sta     rand+3
        rts

X was set to 0, so that the return value doesn't differ between those two calls:
Code:
unsigned char c = GetRandomNumber(0xFF);
unsigned int i = GetRandomNumber(0xFF);
(As far as I know, in the second call, X would become the high byte of the integer, so it should be set to 0 and not to some other value.)
Re: Quality of the CC65 randomizer
by on (#175257)
DRW wrote:
The randomizer is supposed to be 32 bit, but the return value is only an 8 bit value.

The "bits" of a PRNG don't have to do with the return value, directly. A 32-bit PRNG generates a repeating sequence of at most 2^32 values.

In reality with this LCG, each bit has its own period of randomness. i.e. rand() & 1 is a 24-bit sequence, rand() & 2 is a 25-bit, etc. Technically the "best" bit is rand() & 128.

DRW wrote:
Would there even be a problem in this implementation if you call the randomizer if the seed is 0?

No, with the LCG there's no problem if the seed is 0. That's only a problem for LFSRs.

DRW wrote:
Can you please check if everything is still correct?

Looks okay to me.
Re: Quality of the CC65 randomizer
by on (#175260)
rainwarrior wrote:
DRW wrote:
Would there even be a problem in this implementation if you call the randomizer if the seed is 0?

No, with the LCG there's no problem if the seed is 0. That's only a problem for LFSRs.

Or (technically) with Lehmer LCGs, which use a prime period and a zero addend instead of a power-of-two period and an odd addend. But it won't be a problem for this particular LCG.
Re: Quality of the CC65 randomizer
by on (#175261)
Thanks for the check.

rainwarrior wrote:
The "bits" of a PRNG don't have to do with the return value, directly. A 32-bit PRNG generates a repeating sequence of at most 2^32 values.

Yes, I know. The bits indicate how many times you can generate a random number until the whole sequence starts again.
I was just saying this because people might get the idea that a randomizer that returns an 8 bit value also has an 8 bit seed while a 16 bit randomizer has a 16 bit seed etc., which is of course not the case here.

rainwarrior wrote:
In reality with this LCG, each bit has its own period of randomness. i.e. rand() & 1 is a 24-bit sequence, rand() & 2 is a 25-bit, etc. Technically the "best" bit is rand() & 128.

So, does that mean that the bits of the copy of rand+3 in A should be inverted before being AND-connected with the bit mask? Because the bit mask parameter is always %00000001, %00000011, %00000111 etc. and inverting A lets the return value become more random since the high bits are more randomized and inverting them turns the highest bits into the lowest bits?
Re: Quality of the CC65 randomizer
by on (#175264)
DRW wrote:
rainwarrior wrote:
In reality with this LCG, each bit has its own period of randomness. i.e. rand() & 1 is a 24-bit sequence, rand() & 2 is a 25-bit, etc. Technically the "best" bit is rand() & 128.

So, does that mean that the bits of the copy of rand+3 in A should be inverted before being AND-connected with the bit mask? Because the bit mask parameter is always %00000001, %00000011, %00000111 etc. and inverting A lets the return value become more random since the high bits are more randomized and inverting them turns the highest bits into the lowest bits?

Not really. You're already getting a 24-bit sequence with the lowest bit (>16 million!), I don't think you need to worry about not getting "the best" once it's good enough.

If you really wanted to increase quality, you could just add another byte (rand+4). I don't think there's much point; 16+ bits is probably good enough for almost any NES game's needs.
Re: Quality of the CC65 randomizer
by on (#175408)
The main branch of cc65's rand.s has now been fixed. (change)