It is currently Sun Dec 17, 2017 10:56 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 44 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Thu Jul 07, 2016 1:08 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19353
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 1:25 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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.


Last edited by rainwarrior on Tue Jul 12, 2016 12:27 am, edited 1 time in total.

Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 1:31 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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 999 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.


Last edited by rainwarrior on Thu Jul 07, 2016 1:59 pm, edited 2 times in total.

Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 1:39 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7319
Location: Chexbres, VD, Switzerland
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.


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 1:52 pm 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Thu Jul 07, 2016 11:44 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7319
Location: Chexbres, VD, Switzerland
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".


Top
 Profile  
 
PostPosted: Fri Jul 08, 2016 12:34 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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.


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 1:38 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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.


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 3:20 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1517
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
?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 3:37 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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.


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 3:53 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1517
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".

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 4:03 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19353
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 4:03 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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.


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 4:42 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1517
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.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Mon Jul 11, 2016 4:55 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5899
Location: Canada
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.


Last edited by rainwarrior on Mon Jul 11, 2016 5:20 pm, edited 1 time in total.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 44 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 8 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