[computer-go] Re: computer-go Digest, Vol 25, Issue 14, Message 7

[Jacques Basaldúa]

Don Dailey wrote:
 > As I mentioned earlier, I use what is currently considered an extremely
 > fast and high quality random number generator and it's capable of
 > generating 32 bit random numbers,  so I can get a 64 bit random number
 > with 2 calls.

A congruential generator has a cycle length which is usually a prime.
That guarantees (since the numbers modulo a prime form a group) that no
subgroup exists (because as Group Theory states: subgroups divide the
order of the group and no integer divides a prime number by definition).
In practical terms: If you make n successive extractions of your random
number generator, *cycle length is kept*. Note that if cycle length is
not a prime it will be even worse: you will get the same problem plus
reduced cycle length.

No matter if you make 2 or 3 extractions, you get the same number of
different signatures as you get with the 32-bit generator alone. You
could just have copied the lower 32 bits into the upper 32 bits, it
wouldn't make much difference, because: If the lower 32 bits match,
*the full 64 bits will do*. Because any number has only one successor
in the cycle which is a fixed sequence. Since the Zobrist hash uses
simple xor (no rotations), this applies to the hash of a full board
as well.

I would be very careful calling this a 64-bit generator, not to mention
a "quality" 64-bit random number generator. I would advise: If you need
a 64-bit generator, get a 64-bit generator. E.g. A Mersenne twister.

PD: This is my first reply, excuse if it does not go to the correct
thread and feel free to move it. I read this as "computer-go Digest"
(19 messages in one).
I am replying to:

-----Original Message-----
Date: Tue, 15 Aug 2006 14:24:58 -0400
From: Don Dailey <drd at mit.edu>
Subject: RE: [computer-go] compiling orego on m$'s vc++ 2005
    express-nostdint.h
To: computer-go <computer-go at computer-go.org>
Message-ID: <1155666298.17437.120.camel at localhost.localdomain>
Content-Type: text/plain

Jacques.