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

Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: CRC routines as PRNGs

Post by Shiru »

I tried both LSB and MSB, the difference is subtle, MSB just gives more think lines on the picture, but it still does not look like random.
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 »

Have you put the right multiply and add constants ? Because I just tried to plot it in GNU octave, and it actually looks very random to me :

Code: Select all

x = 1
for i=1:1000; x(i+1) = bitand(x(i)*5 + 0x3611, 0xffff); end
y = bitand(x, 0xff00) / 0x100
plot(y)
Pehaps there is other values that would work better than 5 and 0x3611, in fact I have no idea what makes these values work particularly well or not well. In any cases, it would not make the thing more complex or slower.

PS : Oh I know ! What seed did you use ? I used 1, perhaps if you use another seed (such as 0) the sequence could be not random at all.
Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: CRC routines as PRNGs

Post by Shiru »

I tried various values for seed, they all give the same result.

I think I know how to explain the results: it simply produces very short repeating sequence, like 256 or something numbers. As my test array is 256x256, it simply can't produce enough variety to fill every possible position.
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 »

I just checked with GNU octave, and the RNG actually has a sequence of 65536 states, which means it is optimal for a 16-bit RNG (it could technically not get any better with 16-bit). It is also, of course, independant of the seed, since the loop goes through all possible states.

I execute this script as a proof :

Code: Select all

x = 0;
for i=1:65537;  x(i+1) = bitand(x(i)*5 + 0x3611, 0xffff); end;
y = bitand(x, 0xff00) / 0x100;
% plot(y)
find(not(x))	% Print when the RNG rolls back to value '0'

% Compute the probability of all 256 possible values

for i=1:256; z(i) = length(find(not(y-i-1))); end;
plot(z)
It also shows that all values are almost equiprobable for the 8 MSBs.

I don't know how you test the RNG, and how you use a bi-dimentional array for it. Would you share the details ? Thanks.
Last edited by Bregalad on Wed Dec 12, 2012 7:11 am, edited 1 time in total.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: CRC routines as PRNGs

Post by tokumaru »

I often use quick and dirty random number generators, but to improve randomness I continuously clock the random number generator while waiting for VBlank. Since the time taken to process a frame is pretty random depending on which objects are active and all the actions the engine takes in different frames, that seems to work out well.
User avatar
thefox
Posts: 3134
Joined: Mon Jan 03, 2005 10:36 am
Location: 🇫🇮
Contact:

Re: CRC routines as PRNGs

Post by thefox »

Shiru wrote:I think I know how to explain the results: it simply produces very short repeating sequence, like 256 or something numbers. As my test array is 256x256, it simply can't produce enough variety to fill every possible position.
I tried plotting this RNG, too, and got this picture:
rng-xy.png
rng-xy.png (4.53 KiB) Viewed 8302 times
The numbers were pulled in pairs of two (X and Y), so if you look at this picture carefully, it basically means that for any given value (0..255, in X axis) returned by the RNG there are only 5-6 different (sequential) values that may follow it, in other words it's very predictable.

So it's not a good RNG.
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: CRC routines as PRNGs

Post by Shiru »

The picture that thefox got is the same that I'm getting using MSB.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: CRC routines as PRNGs

Post by tepples »

And I guess that's why commonly used error detection protocols use CRC (based on LFSR) rather than a linear congruential hash like the DJB hash, right? Part of the drawback of the linear congruential structure is that high-order bits don't cascade back to low-order bits.

DJB hash:
hash[0] = 5381
hash[i + 1] = (33 * hash + data) mod 2^n

Why 33? It's a power of two plus or minus one (for quick multiplication) that's close to the number of letters in the Latin alphabet (for good distribution when used to hash strings).
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: CRC routines as PRNGs

Post by Kasumi »

tokumaru wrote:I continuously clock the random number generator while waiting for VBlank.
I'd just like to say that this is a pretty great idea. I wonder if you get could even get decent results just incrementing a variable by one during the vblank wait loop. :lol: I bet you could!
edit:
Heh. It's true. You can do pretty well! (Probably not well enough, though)
Image
This chart was made by solely incrementing $FF during the Vblank loop. Each pixel was made using the random number from each set of two consecutive frames.
Frame 1, frame 2 = point 1's x and y
Frame 3, frame 4 = point 2's x and y
etc.

The very clear diagonal line was caused by me standing completely still. (I didn't have enemies or anything else too variable in the level I used to test, so the processing time was probably pretty stable.)

Edit 2: Continuation of the same line:
Image
My game also has a bug which occasionally makes the game wait for a variable vblank sets rather than the vblank itself. (It halts the program so no new tiles are put into the buffer before the previous one have been updated by the NMI routine), This caused the second diagonal line.

Still, pretty interesting!
Last edited by Kasumi on Wed Dec 12, 2012 9:18 am, edited 3 times in total.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: CRC routines as PRNGs

Post by tepples »

Some commercial games update a random seed during wait-for-vblank as well, for which Dwedit had a heck of a time computing the exact result for PocketNES speed hacks. Ultimately the time between the end of the game logic and the next vblank is a complicated function of the entire game state, but it's still a function. Incrementing a seed while waiting for vblank is thus still a PRNG, providing no more entropy than any other way of hashing keypresses. I guess that lends credence to the concept of reading the controller dozens of times during menus with little or no animation going on, such as the title screen, to gather more entropy.
User avatar
Movax12
Posts: 541
Joined: Sun Jan 02, 2011 11:50 am

Re: CRC routines as PRNGs

Post by Movax12 »

Even if the RNG is in the NMI, the RN is still going to be accessed at random based on input in most cases. Unless you can cause an event at the same frame everytime, it will seem random if the numbers are distributed well.
bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Re: CRC routines as PRNGs

Post by bogax »

rainwarrior wrote:
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.
Well, of course a better generator will be better than a crappy one, especially for sufficiently
broad definitions of better.
But that was meant as a rhetorical statement rather than an accusation. So insofar as it
was an invitation to elaborate, perhaps it was a bit disingenuous of me not to have
elaborated a bit more myself.
If it sounded like an accusation, I apologize.
rainwarrior wrote:
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.
I don't think any LFSR of similar simplicity is going to be better though it may not be any
worse (I don't think that's likely but I haven't surveyed all the possibilities do you have
a candidate in mind?)
rainwarrior wrote:
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.
Again, if you've got a recommendation I'd love to hear it
rainwarrior wrote: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.
If we were using some more objective criterion like which is best for monte carlo type
calcultions, I'd definitely agree with all you've said.
I think this is more a matter of taste. If it doesn't need to be random but only look random
(which might actually be less random)
here's some pictures that are meant to be illustrative not necessarily representative.
for one thing they only use 8 bits. They all use the same LCG x'=x*17+103
top row are runs of 256 bottom row is 65280 (which is a full run of the 8 bit
LFSR-LCG combo)
Attachments
scatters.gif
zzo38
Posts: 1096
Joined: Mon Feb 07, 2011 12:46 pm

Re: CRC routines as PRNGs

Post by zzo38 »

I have used ARCFOUR, updated several times per frame, using the microphone for additional entropy, and initializing two of its parameters using the initial contents of RAM.

I do not know how well it compare to whatever else is suggested in this forum.
(Free Hero Mesh - FOSS puzzle game engine)
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 »

A big advantage of an entirely-software RNG is repeatability, either when debugging or when you want to generate the same sequence again from just a seed (think of SimCity's random land generation and the three?-digit code you could get if you ever wanted that land formation again). It's also testably-reliable, whereas something depending on hardware might generate low-quality numbers in some circumstances.
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: CRC routines as PRNGs

Post by JRoatch »

So for a dithering experiment I needed a lot of pseudo-random bytes but I felt that a 16 bit state space was too small. I found this thread and figured I could do a similar thing with the 32 bit Galois LFSR I was using at the time.

Code: Select all

rng_step_bit:     ; 26 to 27 cycles (+6 for rts)
  lda rand+3
  lsr
  ror rand+2
  ror rand+1
  ror rand+0
  bcc +
    eor #$a3
  +:
  sta rand+3
rts
And this is a byte version of the above using techniques hinted at by Drag. To use read rand+0 then call rng_step_byte.

Code: Select all

rng_step_byte:    ; 79 cycles (+6 for rts)
  lda #$00
rng_mix_byte:     ; 77 cycles (+6 for rts)
  eor rand+0      ; mix in input byte, and start
  sta rand+0      ; XORing this with the low byte
  asl             ; starting with x^30 term.
  asl
  asl
  asl
  eor rand+0      ; x^26 term
  asl
  eor rand+0      ; x^25 term
  asl
  eor rand+3      ; XOR with original low byte.
  sta rand+3
  lda rand+0      ; Again for the high byte.
  lsr             ; Start with x^25 term
  eor rand+0      ; x^26 term
  lsr
  lsr
  lsr
  lsr
  eor rand+0      ; x^30 term
  lsr
  lsr
  eor rand+0      ; x^32 term (or original high byte)
  ldy rand+1      ; finaly, rotate the bytes
  sty rand+0      ; if Y needs to be preserved
  ldy rand+2      ; stash A somewhere, then rotate
  sty rand+1      ; the bytes with A.
  ldy rand+3
  sty rand+2
  sta rand+3
rts
Post Reply