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@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
