On Tue, 9 Oct 2001, Thomas Jentzsch wrote:
> B. Watson wrote::
>
> > I guess I should go & find some papers on chaos theory or something, but the
> > math is beyond me. I never learned much about statistical analysis, but it'd
> > be interesting to be able to test `how random' my random numbers are. Any
> > pointers?
>
> First, I would would test, how many random bytes (or bits, if you need less than 8) your generator produces. Just count how often you have to call your random function until the start value repeats. Good one byte random generators produce 255 values (1..255).
>
The Suicide Mission routine doesn't repeat the first time the start value comes
around again... I got a sequence like this (using $AA as seed):
55
2a
15
a
5
2
1
0
0
80
40
a0
......
55 ; 69th byte
2a
15
8a
c5
e2
f1
78
3c
9e
4f
a7
......
55 ; 136th byte
aa
d5
ea
f5
fa
7d
be
df
ef
77
bb
5d
ae
....then I don't get another $55 until the 519th byte. Even then, it doesn't
quite repeat.
I ran a meg's worth of bytes generated by this algorithm (re-coded in perl)
through a program called `ent' that's supposed to analyse the randomness of
a series of numbers, here's the results I got:
Entropy = 8.000000 bits per byte.
Optimum compression would reduce the size
of this 1048576 byte file by 0 percent.
Chi square distribution for 1048576 samples is 0.13, and randomly
would exceed this value 99.99 percent of the times.
Arithmetic mean value of data bytes is 127.4993 (127.5 = random).
Monte Carlo value for Pi is 3.107380323 (error 1.09 percent).
Serial correlation coefficient is 0.500001 (totally uncorrelated = 0.0).
According to the docs for the `ent' program, that `Chi square' statistic
means they aren't all that random... but I think that just means `not
random enough to use for generating cryptographic keys', probably plenty
random for use in a 2600 game :)
> Then it is getting more complicated, because there should also be a random distance between each value and each distance should have about same possibility.
>
> I'm not an expert to explain this, but there is a nice link
> http://www.agner.org/random/theory/
> where this is explained mainly understandable to me.
>
Thanks.
> Another idea I've posted here before, is to rely on the randomness (branches, page-faults etc.) of the execution time of your code between timer syncronisation. Then you can i.E. use the following code to produce three random bits.
>
> ldx #$FF
> .waitTim:
> lda INTIM-$FF,x ; 5 waste one cylce here
> bpl .waitTim ; 2/3
>
> Since the timer is counting every cylce after it reached zero and the loop needs eight cycles, this will return $F8..$FF, so the last 3 bits are somehow random. Or you could make the loop 16 cyles long and get 4 bits.
>
Hmmm. Where would you put this code? in the VBLANK period, before the code that
sets TIM64T to #44? Or right after the kernel and overscan processing, but
before the end-of-overscan WSYNC's, maybe? (I like to use TIM64T instead of a
KillLines loop at the end of overscan...)
I'll have to play with this some. Depending on the processing done, it might
not be all that random...
B.
---
If a trainstation is the place where trains stop, what is a workstation?
-
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
