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.
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 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.
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.
hash = 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).
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.
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
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!
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
I do not know how well it compare to whatever else is suggested in this forum.
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