I don't think Don was saying to use many calls to RDTSC to generate a single
random number.
I think he meant do something like (FastBadRand() XOR RDTSC).
The first part has low quality low-order bits and the second part has low
quality high-order bits.
Also, I can't imagine why executing a RDTSC would take 50 cycles. But I
couldn't find any docs on that aspect of the instruction.
steve uurtamo wrote:
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey <[EMAIL PROTECTED]> wrote:
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/
_______________________________________________
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/
