It is currently Sun Nov 18, 2018 4:08 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 45 posts ]  Go to page Previous  1, 2, 3
Author Message
PostPosted: Wed Dec 12, 2012 2:48 am 
Offline

Joined: Sat Jan 23, 2010 11:41 pm
Posts: 1161
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.


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 5:29 am 
Offline
User avatar

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


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 6:17 am 
Offline

Joined: Sat Jan 23, 2010 11:41 pm
Posts: 1161
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.


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 7:04 am 
Offline
User avatar

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

Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 7:06 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10974
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 7:20 am 
Offline
User avatar

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3138
Location: Tampere, Finland
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:

Attachment:
rng-xy.png
rng-xy.png [ 4.53 KiB | Viewed 3677 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


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 7:26 am 
Offline

Joined: Sat Jan 23, 2010 11:41 pm
Posts: 1161
The picture that thefox got is the same that I'm getting using MSB.


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 8:16 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20783
Location: NE Indiana, USA (NTSC)
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[i] + data[i]) 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).


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 8:41 am 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1251
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!

_________________
https://kasumi.itch.io/indivisible


Last edited by Kasumi on Wed Dec 12, 2012 9:18 am, edited 3 times in total.

Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 9:03 am 
Offline

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


Top
 Profile  
 
PostPosted: Wed Dec 12, 2012 9:52 am 
Offline
User avatar

Joined: Sun Jan 02, 2011 11:50 am
Posts: 522
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.


Top
 Profile  
 
PostPosted: Fri Dec 14, 2012 11:49 am 
Offline

Joined: Wed Jul 30, 2008 12:03 am
Posts: 34
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
scatters.gif [ 47.49 KiB | Viewed 3623 times ]
Top
 Profile  
 
PostPosted: Thu Dec 20, 2012 2:22 pm 
Offline
User avatar

Joined: Mon Feb 07, 2011 12:46 pm
Posts: 1022
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.

_________________
.


Top
 Profile  
 
PostPosted: Thu Dec 20, 2012 3:13 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Top
 Profile  
 
PostPosted: Sat Jan 03, 2015 10:43 am 
Offline
Formerly 43110
User avatar

Joined: Wed Feb 05, 2014 7:01 am
Posts: 362
Location: us-east
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:
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:
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


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

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