CRC routines as PRNGs

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
Movax12
Posts: 541
Joined: Sun Jan 02, 2011 11:50 am

Re: CRC routines as PRNGs

Post by Movax12 »

Super Mario Bros. Pseudo code:

Code: Select all

if ( (PseudoRandom[0] & 2) ^ (PseudoRandom[1] & 2) ) == 0
    clc
else
    sec
endif

for x = 0 to 6 {
  ror PseudoRandom[ x ]
}
I should add: PseudoRandom[0] is initialized with $A5.

Also you could say:

Code: Select all

c = ( (PseudoRandom[0] & 2) ^ (PseudoRandom[1] & 2) )

for x = 0 to 6 {
  ror PseudoRandom[ x ]
}
Last edited by Movax12 on Tue Dec 11, 2012 6:38 pm, edited 2 times in total.
lidnariq
Posts: 11432
Joined: Sun Apr 13, 2008 11:12 am

Re: CRC routines as PRNGs

Post by lidnariq »

All LFSRs must have the first bit set.

http://www.newwaveinstruments.com/resou ... stages.txt is a list of many different 32-bit LFSRs; they don't know of any with fewer taps.

If you're willing to use a 31-bit LFSR there's a few with just 2 taps: http://www.newwaveinstruments.com/resou ... stages.txt

Also, the sequence of all maximal-length LFSRs contain 2ⁿ different 2ⁱ-bit-long sequences of both 1 and 0, where 2⁽ⁿ⁺ⁱ⁾-1=LFSR period length.
Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: CRC routines as PRNGs

Post by Shiru »

Bregalad wrote:It works wonders to me, and is very fast.
I checked my code few times (difficult to make a mistake), and what I'm getting from this is this picture - totally not random. I'm just generating two 8-bit number with this code to get X,Y for a point, and putting many thousands of them on the screen (points are black). Normal C rand or the code that I posted above both fill the whole screen leaving no gaps, as it expected from a properly working random generator.
random.png
random.png (1.62 KiB) Viewed 5487 times
bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Re: CRC routines as PRNGs

Post by bogax »

Drag wrote:Well yeah, unless I can find a decent 32-bit polynomial (decent meaning maximal-length, as few 1s as possible, ideally with them spread out and away from the most significant 8 bits, while also allowing a good random distribution), it's probably a lot easier to just use a traditional LFSR instead of trying to come up with an optimized one. :P
I think the general rule of thumb is you want about half 1s to stirr things up.
(dunno if that's valid)

Google "Galois LFSR" if you don't know what that is.

A common ploy is to combine two different types of PRNGs
in the hopes that they'll hide each others deficiencies.
Say, an LFSR and an LCG XORed toghether

So instead of a 32 bit PRNG you might combine two 16 bit ones

Here are lists of polynomials:
http://www.ece.cmu.edu/~koopman/lfsr/
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: CRC routines as PRNGs

Post by blargg »

Galois and Fibonacci are just two "opposite" ways to implement a particular LFSR (with Galois being simpler in software).
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

bogax wrote:A common ploy is to combine two different types of PRNGs
in the hopes that they'll hide each others deficiencies.
Say, an LFSR and an LCG XORed toghether
I would not recommend this. A better quality generator will be superior to the XOR of two crappy generators, and it's not likely you're saving performance/complexity vs the alternative. It may sometimes be an improvement over using just one crappy generator (provided they don't have overlapping/dependent failings-- and you really need to test this to make sure, because it's more likely than you might think), but it's a poor way to solve the problem of low-quality random numbers.


Two points though:

1. For a lot of gameplay situations, a crummy random generator is sufficient, since a lot of the randomness comes from the timing of the human player and when they cause random decisions to happen. A lot of logical decisions are binary anyway, so 1 random bit from an LFSR can be totally fine. There are situations where you might need better quality numbers however, such as a turn based battle system, or trying to procedurally generate a level / background (shiru's test is one of many that will quickly show a poor generator). Consider how good you need the numbers to be before you decide to seek a more complex, higher quality PRNG.

2. How often is the PRNG being used? If we're talking about a big batch during level load only, or if they're only being used once a frame, or not even every frame, there's no reason to be skimpy about performance if quality random numbers would be preferred. You probably only need a fast PRNG if you have a continual stream of random numbers during gameplay.

Long story short, "good" and "fast" PRNGs both have their place. If you're going to cut and paste somebody else's code without evaluating, I'd say it's probably better to err on the side of "good" rather than "fast".
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

lidnariq wrote:All LFSRs must have the first bit set.

http://www.newwaveinstruments.com/resou ... stages.txt is a list of many different 32-bit LFSRs; they don't know of any with fewer taps.

If you're willing to use a 31-bit LFSR there's a few with just 2 taps: http://www.newwaveinstruments.com/resou ... stages.txt

Also, the sequence of all maximal-length LFSRs contain 2ⁿ different 2ⁱ-bit-long sequences of both 1 and 0, where 2⁽ⁿ⁺ⁱ⁾-1=LFSR period length.
Thanks lidnariq! I actually ended up using one of the polynomials from 32stages.txt. Specifically, [32, 23, 21, 16].
Ok everybody, I have a working 32-bit lfsr using the shortcut method I figured out. I'll need to see if I can improvie it at all, since this was just quick and dirty. However, it runs in constant time, and it probably could be simplified even more, I'd just need to look at it some more.

Code: Select all

game_random2
 txa
 pha
 lda rnd4	;3
 tax		;2  5
 eor rnd2	;3  8
 sta rnd2	;3  11
 lsr rnd4	;5  16
 ror		;2  18
 lsr rnd4	;5  23
 ror		;2  25
 pha		;3  28
 txa		;2  30
 eor rnd4	;3  33
 sta rnd4	;3  36
 pla		;4  40
 lsr rnd4	;5  45
 ror		;2  47
 and #$e0	;2  49
 eor rnd2	;3  52
 pha		;3  55
 lda rnd4	;3  58
 eor rnd3	;3  61
 sta rnd4	;3  64
 pla		;4  68
 sta rnd3	;3  71
 lda random	;3  74
 sta rnd2	;3  77
 txa		;2  79
 sta random	;3  82
 pla
 tax
 lda random
 rts
I've had a simple NES program (the one this routine is for, actually) running a loop where it begins by copying 8 random bytes generated from this routine, and then repeatedly reads from the routine, looking for anything that matches this 8-byte string. After 10 minutes, it's still looking, so I think this has more than enough of a period for non-repeating randomness. However, I don't know how well the values are distributed; they look pretty random to me! :P

For the record, the above code is the equivalent of a Galois LFSR that uses $00A10001 as its XOR, where each byte of output is the result of 8 shifts.

If anyone wants to use this code or run some tests on it, be my guest. :D (Also, if anyone wants me to explain how I came up with this code, I'll be happy to explain; I just don't want to post a wall of text if nobody's interested. :P)

Edit: One last thing! You need to initialize this routine by writing a nonzero value to random, rnd2, rnd3, or rnd4. I did it by writing $80 to rnd4.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: CRC routines as PRNGs

Post by blargg »

Remember the trick someone mentioned a while back here (Bregalad?) of continuously writing the result to $4011 and listening for any audible patterns.
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

RANDU: A Cautionary Tale

Also, it may be worth running your PRNG for a while before you start testing for cycles. It is possible to enter a cycle from a seed value outside that cycle. (Also, obviously if you want to test longer cycles you can reimplement it on a modern computer. I usually do this first, and then implement it on the target hardware after.)
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

blargg wrote:Remember the trick someone mentioned a while back here (Bregalad?) of continuously writing the result to $4011 and listening for any audible patterns.
Hah, that's a pretty cool idea. :D I don't hear any buzzing or any subconsciously repeating tones or anything, it just sounds like white noise. It sounds even better than the APU's noise channel if you can believe it (which you probably can). :P Though, comparing with the PRNG I was using before this, I can tell this newer run runs faster. :D
rainwarrior wrote:RANDU: A Cautionary Tale

Also, it may be worth running your PRNG for a while before you start testing for cycles. It is possible to enter a cycle from a seed value outside that cycle. (Also, obviously if you want to test longer cycles you can reimplement it on a modern computer. I usually do this first, and then implement it on the target hardware after.)
I did think of that, so I had the tester generate 4 random numbers before saving the initial string of 8. Hypothetically, if the polynomial I chose is indeed a maximal-length one, then that means the number of unique states for the shift register is (2^32)-1, meaning, the shift register should cycle between every possible combination of 32 bits, minus the all-zeros one. That means, the only closed-off cycle is the all-zeros one.

As for testing on a modern computer, I would have, but I don't have any IDEs conveniently set up at the moment, other than for NES programming. I guess it saves me the need to convert my routine back and forth. :P
bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Re: CRC routines as PRNGs

Post by bogax »

rainwarrior wrote:
bogax wrote:A common ploy is to combine two different types of PRNGs
in the hopes that they'll hide each others deficiencies.
Say, an LFSR and an LCG XORed toghether
I would not recommend this.
Not sure I'd go so far as to recommend it, but it certainly is a common ploy.
A better quality generator will be superior to the XOR of two crappy generators,
Right no true scotsman would use a crappy generator :P
and it's not likely you're saving performance/complexity vs the alternative.
I definetly disagree with that. What's your idea of the alternative? (ie a better generator
that's as simple and fast as an LFSR and an LCG)
It may sometimes be an improvement over using just one crappy generator (provided they don't have overlapping/dependent failings-- and you really need to test this to make sure, because it's more likely than you might think),
I have no argument with that.
but it's a poor way to solve the problem of low-quality random numbers.
Where do you get that idea?
lidnariq
Posts: 11432
Joined: Sun Apr 13, 2008 11:12 am

Re: CRC routines as PRNGs

Post by lidnariq »

Drag wrote:then that means the number of unique states for the shift register is (2^32)-1, meaning, the shift register should cycle between every possible combination of 32 bits, minus the all-zeros one. That means, the only closed-off cycle is the all-zeros one.
Right. LFSRs are extremely well characterized (and bleed state, so it's easy to calculate the next bit and taps after watching the output for a while, but that's different from what we perceive as predictable): they are white, wide-sense stationary noise source with a too-perfect distribution of runs.

As a tangent, I managed to wikiwalk my way to the shrinking generator
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

I tested with a seed that I grabbed from a minute's worth of random numbers, $C83C5447, and after another ten minutes of random numbers (starting with that seed), there still haven't been any cycles detected.

The only reason there'd be a closed-off cycle is if I messed up when converting the polynomial into its hexadecimal representation: I took [32, 23, 21, 16] (which is supposed to be a maximal-length polynomial), interpreted it as (x^32 + x^23 + x^21 + x^16 + x^0), which I then interpreted as $00A10001 (I used x^0 instead of x^32). I wasn't sure if I was allowed to use x^0 instead of x^32, but it seems to be working so far.

So if everything is correct, this prng should give you 4,294,967,295 random numbers before it repeats the cycle. The only danger would be if it somehow got stuck in the all-zeros state, which I don't think is supposed to be naturally possible with an LFSR, be it Galois or Fibonacci.
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

bogax wrote:Right no true scotsman would use a crappy generator :P
I'm not sure how this was a "no true scotsman" argument. If faced with a choice of XORing two 16 bit generators, or one equivalent 32 bit generator (or even a 24 bit generator), I believe you would find with empirical testing that the latter will give better results, and can be done with equivalent performance.
bogax wrote:What's your idea of the alternative? (ie a better generator that's as simple and fast as an LFSR and an LCG)
A 32 bit LFSR or LCG will give better 16-bit results than a 16 bit LFSR XORed with a 16 bit LCG.
bogax wrote:
rainwarrior wrote:it's a poor way to solve the problem of low-quality random numbers.
Where do you get that idea?
The idea comes from my experience with random number generators used for a variety of purposes. I've tried this technique before and I call it a poor solution because I think you can get better results from a single generator of similar computational complexity.

The reason I don't think XORing two generators together is that both signals have a periodicity that is much-much-much shorter than the equivalent single 32 bit generator. Even though they are interfering with each other via XOR, there are situations where both periods will show through this operation.

There are also many situations where the difference doesn't matter, and it's not a big deal how you build your PRNG, but I'm talking about the case where all else is more or less equal, and if your goal is to produce a more uniform, less predictable PRNG, I think the XOR approach is a bad idea. There are better ways to improve the output of your PRNG for equivalent computational cost.

I'm sorry to be dismissive of the idea, but this is my honest opinion of it.
Last edited by rainwarrior on Wed Dec 12, 2012 4:00 am, edited 1 time in total.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: CRC routines as PRNGs

Post by Bregalad »

Shiru, did you remember to take only the 8 most significant bits of the result when you plotted this ?
I think the least significant bits are not random but the most significant bits are.

At least I tested this RNG with the $4011 white noise technique before using it and it worked fine.
Post Reply