[computer-go] Random

[Don Dailey]

terry mcintyre wrote:
> Regarding the time used by RDTSC:
>
> From
> http://smallcode.weblogs.us/2007/12/07/performance-measurements-with-rdtsc/
>
> Intel and Agner Fog recommend measuring the overhead
> of RDTSC function and subtracting it from your result.
> The overhead is relatively low (150-200 clock cycles)
> and it occurs in all tested functions, so you can
> neglect it when measuring long functions (e.g., 100
> 000 clock cycles).
>
> NOTE: the page above recommends flushing the cache
> before  calling RDTSC, when using it for timing
> purposes. There is probably no need to do so when
> grabbing LSBs.
>
> I wonder, however, if the LSBs would be as random as
> all that, when called frequently in
> quasi-deterministic code which takes a predictable
> number of cycles between invocations.
>   
I'm not interested in using it here to measure performance, but as a 
possible way to have a very fast and very high quality random number 
function. But this won't happen if RDTSC isn't fast and it doesn't 
appear to be very fast.

I don't expect RDTSC to be very random either, I'm more interested in 
the chaos it presents to the random number system which is produced even 
with very little agitation added to the system. Even an occasional 1 bit 
change would cure many of the problems of some fast random number 
generators.

If you were to call this random number generator consecutively, many 
time in a tight loop, I suspect that you will get a LOT of variation in 
the number of cycles that have passed between calls, certainly enough to 
make it completely unpredictable in the long run. Like weather 
predictions you might predict the next day (or call) with some level of 
reasonable accuracy but not a specific day in the next month.

Every deterministic pseudo random number generator in existence always 
has some kind of structure. The main difference between what we consider 
good and bad ones is how well that structure is obfuscated or hidden 
from view. We try to be clever so that statistical tests cannot see the 
structure. One of primary methods to "hide" this structure is to make it 
so big (by long cycle lengths) that we can only see a tiny portion of 
it. For instance if every zillion'th bit alternated between 0 and 1, it 
would be hard to observe.

So if you can add a small amount of non-determinism you can probably 
"bust up" the hidden structure.

At any rate, it seems like it's not workable as a fast alternative to 
RNG. It might be combined with a slow very high quality generator to 
produce numbers that are somewhat closer to true random numbers.

- Don


>
>
> Terry McIntyre <terrymcintyre at yahoo.com>
>
> “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.”
>
> Benjamin Disraeli, Speech in the House of Commons [June 15, 1874]
>
>
>       
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>