[computer-go] Random

[Don Dailey]

For a long time I have pondered whether you could build a very high 
quality random number generator that was extremely fast using the 
pentium RDTSC instruction as a low order bit entropy source.     The 
idea would be to use an extremely fast (but low quality) pseudo random 
number generator,  but modify the output (or the internal state of the 
generator) with the time stamp register at each call.

RDTSC reads the pentiums internal clock and is basically just a 64 bit 
counter.    However it increments very quickly and could be viewed as an 
entropy source in the lowest bits as it would introduce at least a 
little bit of non-determinism, and I think a little is all you would 
need to transform a horrible generator into a good practical one for 
many applications.   I  think the lowest 2 or 3 (or more)  bits would 
appear to modern processors as almost unpredictable since there is so 
much going on inside modern computers that are unpredictable. 

I don't know if the call to RDTSC is fast or how it would affect the 
parallelism of todays modern machines.   I'm not particularly interested 
in non-deterministic generators as I sometimes depend on this for 
testing and debugging,  but it's an idea I thought I would throw out 
there.     

- Don




Don Dailey wrote:
> If you are looking for a cheap fast and simple random number 
> generator,  A post by George Marsaglia, an expert/guru on random 
> number generation has several and a C implemention.
>
> These are one line generators,  coded as macros.    He also discusses 
> the period and quality of each of them. 
> This is a gem of a post  on sci.stat.math,sci.math  if you are 
> interested in RNG:
>
>        http://www.math.niu.edu/~rusin/known-math/99/RNG
>
> - Don
>
>
>
> Heikki Levanto wrote:
>>> In addition, xor_shift is better than builtin rand() and faster and
>>> much smaller than MT.      
>>
>> I don't know that much about random numbers, so excuse my ignorance. 
>> But a
>> bit of googling got me to the Park - Miller Minimal Standard random 
>> number
>> generator    http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
>>
>> >From what I read, it should be quite sufficient for go programs. It is
>> dead simple and fast:
>>
>> long int pmrand() {
>>     const long int a=16807;
>>     const long int m= ( 1 << 31 ) -1;
>>     pmrandseed = ( pmrandseed * a ) % m ;
>>     return pmrandseed;
>> } /* pmrand */
>>
>>
>> Should I worry about this not being good enough?
>>   - Heikki
>>
>>
>>
>>   
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>