CRC routines as PRNGs
Moderator: Moderators
Re: CRC routines as PRNGs
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.
Re: CRC routines as PRNGs
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 :
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.
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)
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.
Re: CRC routines as PRNGs
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.
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.
Re: CRC routines as PRNGs
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 :
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.
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)
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.
Re: CRC routines as PRNGs
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.
Re: CRC routines as PRNGs
I tried plotting this RNG, too, and got this picture: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.
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
Re: CRC routines as PRNGs
The picture that thefox got is the same that I'm getting using MSB.
Re: CRC routines as PRNGs
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).
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).
Re: CRC routines as PRNGs
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. I bet you could!tokumaru wrote:I continuously clock the random number generator while waiting for VBlank.
edit:
Heh. It's true. You can do pretty well! (Probably not well enough, though)
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:
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.
Re: CRC routines as PRNGs
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.
Re: CRC routines as PRNGs
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.
Re: CRC routines as PRNGs
Well, of course a better generator will be better than a crappy one, especially for sufficientlyrainwarrior wrote: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:Right no true scotsman would use a crappy generator
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.
I don't think any LFSR of similar simplicity is going to be better though it may not be anyrainwarrior wrote: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:What's your idea of the alternative? (ie a better generator that's as simple and fast as an LFSR and an LCG)
worse (I don't think that's likely but I haven't surveyed all the possibilities do you have
a candidate in mind?)
Again, if you've got a recommendation I'd love to hear itrainwarrior wrote: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.bogax wrote:Where do you get that idea?rainwarrior wrote:it's a poor way to solve the problem of low-quality random numbers.
If we were using some more objective criterion like which is best for monte carlo typerainwarrior 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.
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)
Re: CRC routines as PRNGs
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.
I do not know how well it compare to whatever else is suggested in this forum.
(Free Hero Mesh - FOSS puzzle game engine)
Re: CRC routines as PRNGs
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.
Re: CRC routines as PRNGs
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.
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_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
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