Hi,
As mentioned before, Monte Carlo simulations in physics was my thesis
topic, and there we need REALLY good PRNGs or we see the effect in
the results.
There is always a tradeoff between fast and good. If the newer Mersine
Twister algorithms (which are very good) is too slow and you want to
test an alternative, you can use the trick that is in Knuth that I
used for
my thesis work. It is a 2 step generator that shuffles. You build an
array
that holds a set of PRNGs straight from your crude but very fast
generator
(I was partial to a list of 273), Your first PRNG call mod(arraysize)
picks
the PRN you will use, and then the second refills that spot.
No promises that this is any faster, but for lattice simulations where
any correlations pop right out at you sort of like a herringbone
pattern,
this shuffling worked great for me.
Personally, I think that much of the "really high quality" issues are
not
that important for MC Go right now. I think that other things like not
having a reasonable distribution function (which UCT does a remarkable
job of smoothing over) completely overwhelm the effects of a poor PRNG.
Cheers,
David
On 16, May 2008, at 10:42 AM, Don Dailey wrote:
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 <[EMAIL PROTECTED]>
“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@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/
