Re: [stella] entropy & randomness

Subject: Re: [stella] entropy & randomness
From: "Thomas Jentzsch" <tjentzsch@xxxxxx>
Date: Wed, 10 Oct 2001 10:05:55 +0200
B. Watson wrote:
> The Suicide Mission routine...
[snip]
> 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).

I've done the same tests with the River Raid LFSR, here are the results:
(The complete two bytes squence repeats after 57337 values.)

*** River Raid low-byte ***
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 57337 byte file by 0 percent.

Chi square distribution for 57337 samples is 0.03, and randomly
would exceed this value 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4978 (127.5 = random).
Monte Carlo value for Pi is 3.137714525 (error 0.12 percent).
Serial correlation coefficient is 0.000013 (totally uncorrelated = 0.0).

*** River Raid high-byte ***
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 57337 byte file by 0 percent.

Chi square distribution for 57337 samples is 0.03, and randomly
would exceed this value 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4978 (127.5 = random).
Monte Carlo value for Pi is 3.123064044 (error 0.59 percent).
Serial correlation coefficient is 0.000013 (totally uncorrelated = 0.0).

While Chi square is still very bad, the Monte Carlo and Serial correlation test look much better. 
I think, a high serial correlation should be avoided in games, because that's something the human player will notice. So that's maybe the most important test for us.

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


_______________________________________________________________________
1.000.000 DM gewinnen - kostenlos tippen - http://millionenklick.web.de
IhrName@xxxxxx, 8MB Speicher, Verschluesselung - http://freemail.web.de



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

Current Thread