I didn't against you, Álvaro, rather I just made a caution for
programmers who will use your pseudo code as is. :)
First, I prefer SFMT (SIMD-oriented Fast Mersenne Twister) rather
than integer pseudo random number generators in practice where the
quality of play-out is important. Modern processors execute floating
operations as fast as interger ones and
picked = mt_rand() * (double) num_candidates;
is the simplest and safe.
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
#Converting int to double is, in fact, not so fast that
using double num_candidate through out the code may be faster.
When using integer pseudo random number generators and keeping exact
uniform distribution, following code can be used (slower twice).
This discards extra random numbers that bias the distribution.
#As Álvaro wrote, if n << RAND_MAX the bias is very small and may be
ignored.
unsigned long exactly_uniform_random(unsigned long n) {
unsigned long m, r;
if (n == 0) return 0;
m = RAND_MAX % n;
do {
r = rand();
} while (r <= m) ;
return r % n;
}
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT. #Hiroshi, the author of Aya, uses this.
http://en.wikipedia.org/wiki/Xorshift
http://www.jstatsoft.org/v08/i14/paper
unsigned long xorshiftrand(void) {
static unsigned long
x=123456789, y=362436069,
z=521288629, w=88675123;
unsigned long t;
t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
-Hideki
Álvaro Begué: <[EMAIL PROTECTED]>:
>On Tue, May 13, 2008 at 11:57 PM, Hideki Kato <[EMAIL PROTECTED]> wrote:
>>
>> Álvaro Begué: <[EMAIL PROTECTED]>:
>> >Ooops! I hit sent before I finished writing the pseudo code. Sorry.
>> >
>> >int pick(Move *empties, int num_empties) {
>> > int num_candidates = num_empties;
>> > int picked;
>> >
>> > while(1) {
>> > picked = rand()%num_candidates;
>>
>> This code introduces few bias unless num_candidates is a power of two,
>> though.
>> #Assuming rand() returns [0 .. power of two).
>
>Oh, please. I should probably just take that as a provocation and
>ignore it, but I am weak. :)
>
>The pseudo-code I posted was meant to illustrate the process by which
>you move an element to the end and then exclude it from the lottery.
>rand()%num_candidates is just a quick way of telling the reader "pick
>a random integer in [0,num_candidates)".
>
>Besides, some people didn't care if a point had probability that was
>twice as large as the rest. In my system, RAND_MAX is 2147483647,
>which means that in the worst case, some points will have a
>probability that is a factor of 5948709/5948708=1.00000016810372941485
>larger than the rest. Even I can live with that.
>
>Preemptive argument: Now someone will point out that the last few bits
>of rand() may not be very random in some common implementations, so in
>the case where num_candidates is a power of two I may have some
>biases. Please, reread two paragraphs above, or substitute rand() with
>the Mersenne twister.
>
>
>Álvaro.
>_______________________________________________
>computer-go mailing list
>computer-go@computer-go.org
>http://www.computer-go.org/mailman/listinfo/computer-go/
--
[EMAIL PROTECTED] (Kato)
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
