I wrote: >In addition, xor_shift is better than builtin rand() and faster and >much smaller than MT. but it's wrong. Sorry all.
I found recently a comparison at http://www001.upp.so-net.ne.jp/isaku/rand.html (in Japanese). Time to generate 10^8 pesudorandom numberson a Core 2 Duo E6600 + VS2005: zsfmt(SSE2) : 156ms SFMT(SSE2) : 156ms zmtrand(SSE2) : 250ms zxor : 265ms zmtrand : 266ms xor128() : 328ms zsfmt : 375ms mt19937ar : 625ms SFMT : 1046ms rand() : 1969ms unsigned long xor128(){ 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)) ); } http://www.jstatsoft.org/v08/i14/ This shows SFMT/SSE2 is the fastest and twice faster than xor_shift (at least on that environment). -Hideki Hideki Kato: <[EMAIL PROTECTED]>: >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/
