Re: [stella] entropy & randomness

Subject: Re: [stella] entropy & randomness
From: Thomas Jentzsch <tjentzsch@xxxxxx>
Date: Tue, 9 Oct 2001 22:44:42 +0100
B. Watson wrote:
>> 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):

Sure, it's a TWO byte random generator, so you have to check both bytes.


> 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
[snip]
> 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 :)

I doubt that a bit, look at your sequence: 55, 2a, 15 is repeated within
only 69 bytes. The "Chi square" and correlation values confirm that
somehow. Maybe you could test some other (one or two byte) LFSRs.
Try Starmaster (could be worse), Pitfall! (should be better) and River
Raid (looks promising).

But everything is random, as long as nobody notices it isn't.


>> 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...)

You can put it at the end of the VBLANK period (or: at the begin of
DrawScreen).
If you do some processing in OverScan too (unlike "How to..."), then you
will need the timer there too. So at the end of OverScan, you'll have to
wait for the timer and could use my code there too.


> I'll have to play with this some. Depending on the processing done, it might
> not be all that random...

Yes, it really depends on processing. When that is getting rather
complex, every possible branch (or memory-access with possible cycle
penalty) adds some more randomness. Your code itself is used as a very
big random number generator.

Have fun!
Thomas                            
_______________________________________________________
Thomas Jentzsch         | *** Every bit is sacred ! ***
tjentzsch at web dot de |


-
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/

Current Thread