[gnugo-devel] rand() % n

[Douglas Ridgway]

Some random number generators have low order bits which are less random
than the high order bits. Since modulo picks out the low order bits, it
may not be the best way to generate a random integer in a given range. I
don't know whether this is a concern for GnuGo's generator, but it makes
me nervous anyway.  Here's a patch:

Index: utils/random.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/utils/random.c,v
retrieving revision 1.9
diff -u -r1.9 random.c
--- utils/random.c      24 Jan 2004 04:04:57 -0000      1.9
+++ utils/random.c      7 May 2004 17:21:33 -0000
@@ -148,6 +149,16 @@
 gg_urand(void)
 {
   return next_rand();
+}
+
+/* Obtain one random integer value in the interval [0, n-1].
+ * Use the high order bits, not the low ones.
+ */
+
+unsigned int
+gg_nrand(unsigned int n)
+{
+  return (unsigned int) (1.0*n*next_rand()/(0xffffffff+1.0));
 }
 
 
Index: utils/random.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/utils/random.h,v
retrieving revision 1.7
diff -u -r1.7 random.h
--- utils/random.h      24 Jan 2004 04:04:57 -0000      1.7
+++ utils/random.h      7 May 2004 17:21:33 -0000
@@ -59,6 +59,10 @@
 /* Obtain one random integer value in the interval [0, 2^32-1]. */
 unsigned int gg_urand(void);
 
+/* Obtain one random integer value in the interval [0, n-1].
+   Use this instead of gg_rand() % n. */
+unsigned int gg_nrand(unsigned int n);
+
 /* Obtain one random floating point value in the half open interval
  * [0.0, 1.0).
  *
Index: engine/fuseki.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/fuseki.c,v
retrieving revision 1.22
diff -u -r1.22 fuseki.c
--- engine/fuseki.c     24 Jan 2004 04:04:56 -0000      1.22
+++ engine/fuseki.c     7 May 2004 17:21:13 -0000
@@ -174,7 +174,7 @@
   for (i = 0; i < 8; i++)
     sum_of_weights += table[i];
 
-  q = gg_rand() % sum_of_weights;
+  q = gg_nrand(sum_of_weights);
   for (i = 0; i < 8; i++) {
     q -= table[i];
     if (q < 0)
@@ -302,7 +302,7 @@
   /* Choose randomly with respect to relative weights for matched moves. */
   /* Do not choose moves with less value than 20% of the best move */
   best_fuseki_value = fuseki_value[0];
-  q = gg_rand() % fuseki_total_value;
+  q = gg_nrand(fuseki_total_value);
   for (k = 0; k < num_fuseki_moves; k++) {
     if (fuseki_value[k] < (best_fuseki_value / 5))
       break;
Index: engine/handicap.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/handicap.c,v
retrieving revision 1.7
diff -u -r1.7 handicap.c
--- engine/handicap.c   24 Jan 2004 04:04:56 -0000      1.7
+++ engine/handicap.c   7 May 2004 17:21:14 -0000
@@ -322,11 +322,9 @@
     sum_values += handicap_matches[k].value;
   }
 
-  /* Pick a random number between 0 and sum_values. Don't bother with
-   * the fact that lower numbers will tend to be very slightly
-   * overrepresented.
+  /* Pick a random number between 0 and sum_values.
    */
-  r = gg_rand() % sum_values;
+  r = gg_nrand(sum_values);
   
   /* Find the chosen pattern. */
   for (k = 0; k < number_of_matches; k++) {
Index: interface/play_solo.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_solo.c,v
retrieving revision 1.31
diff -u -r1.31 play_solo.c
--- interface/play_solo.c       28 Apr 2004 16:37:44 -0000      1.31
+++ interface/play_solo.c       7 May 2004 17:21:14 -0000
@@ -54,7 +54,7 @@
    * of playing stones near the edge.
    */
   
-  int n = 6 + 2*gg_rand()%5;
+  int n = 6 + 2*gg_nrand(5);
   int i, j;
 
   gnugo_set_komi(5.5);
@@ -68,8 +68,8 @@
   if (boardsize > 6) {
     do {
       do {
-       i = (gg_rand() % 4) + (gg_rand() % (boardsize - 4));
-       j = (gg_rand() % 4) + (gg_rand() % (boardsize - 4));
+       i = gg_nrand(4) + gg_nrand(boardsize - 4);
+       j = gg_nrand(4) + gg_nrand(boardsize - 4);
       } while (!gnugo_is_legal(i, j, gameinfo->to_move));
 
       gnugo_play_move(i, j, gameinfo->to_move);
Index: patterns/dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.35
diff -u -r1.35 dfa.c
--- patterns/dfa.c      24 Jan 2004 04:04:56 -0000      1.35
+++ patterns/dfa.c      7 May 2004 17:21:14 -0000
@@ -1812,7 +1812,7 @@
     /* Randomly change some variations. */
     for (pattern = patterns->patterns; pattern; pattern = pattern->next, k++) {
       if (gg_drand() < change_probability && pattern->num_variations > 1) {
-       int new_variation = gg_rand() % (pattern->num_variations - 1);
+       int new_variation = gg_nrand(pattern->num_variations - 1);
        if (new_variation >= pattern->current_variation)
          new_variation++;
        pattern->current_variation = new_variation;
@@ -1850,7 +1850,7 @@
        */
       double delta = gg_drand() / patterns->num_patterns;
       if (change_probability > upper_limit
-         || (change_probability >= lower_limit && gg_rand() % 2 == 0))
+         || (change_probability >= lower_limit && gg_nrand(2) == 0))
        delta = -delta;
 
       change_probability += delta;