[Assorted-commits] SF.net SVN: assorted:[1092] cpp-commons/trunk/src/commons/rand.h

[<yan...@us...>]

Revision: 1092
          http://assorted.svn.sourceforge.net/assorted/?rev=1092&view=rev
Author:   yangzhang
Date:     2008-12-04 10:24:21 +0000 (Thu, 04 Dec 2008)

Log Message:
-----------
added randint()

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/rand.h

Modified: cpp-commons/trunk/src/commons/rand.h
===================================================================
--- cpp-commons/trunk/src/commons/rand.h	2008-12-04 08:13:56 UTC (rev 1091)
+++ cpp-commons/trunk/src/commons/rand.h	2008-12-04 10:24:21 UTC (rev 1092)
@@ -1,6 +1,9 @@
 #ifndef COMMONS_RAND_H_
 #define COMMONS_RAND_H_
 
+#include <cassert>
+#include <cstdlib> // random, RAND_MAX
+
 namespace commons
 {
   /**
@@ -19,6 +22,86 @@
     inline long draw() { return randx = randx * 1103515245 + 12345; }
     inline long operator()() { return abs(draw()); }
   };
+
+  /**
+   * Generate a random int up to but excluding max.
+   * \param[in] max Must be greater than one.
+   */
+  inline int
+  randint(int max = RAND_MAX)
+  {
+    // My flow of thought:
+    //
+    // It seems simplest to just mod.  But what if not each bit was
+    // identically random?  What if the randomness was only a uniform spread
+    // over RAND_MAX, but all the integers are even (and we only ended up
+    // selecting the lowest bit because max = 2)?
+    //
+    // We want to solve for x:
+    //
+    //   random() ./ RAND_MAX = x ./ max
+    //   x = max * random() ./ RAND_MAX
+    //
+    // But the multiplication could overflow if RAND_MAX is near the max of
+    // long int (random()'s return type), so re-write:
+    //
+    //   random() / (RAND_MAX / max)
+    //
+    // Now nothing overflows, but information is lost.  Is that OK?  No!
+    // If RAND_MAX = 5 and max = 3 and random() = 4, then
+    //
+    //   4 / ((5 / 3 = 1) + 1) = 4 which is >= 3!
+    //
+    // Makes sense, since:
+    //
+    //   RAND_MAX / max <= RAND_MAX ./ max
+    //
+    // so
+    //
+    //   random() / quotient >= random() / real_quotient
+    //
+    // More "spatious" example:
+    //
+    //   (random() = 20000) / ( ( (RAND_MAX = 32768) / (max = 16637) ) = 1 ) =
+    //   20000 which is > max.
+    //
+    // Let's tweak that formula by incrementing the denominator so that it's
+    // impossible for the quotient to exceed max.
+    //
+    //   random() / (RAND_MAX / max + 1)
+    //
+    // How does this fare?
+    //
+    //   4 / ((5 / 2 = 2) + 1 = 3) = 1, which is < 2
+    //   4 / ((5 / 5 = 1) + 1 = 2) = 2, which is < 5, but too much less
+    //   32767 / ((32768 / 32760 = 1) + 1 = 2) = 16633,
+    //     which is < 32760, but too much less
+    //
+    // Think of the problem in terms of pixel line drawing algorithms; we can
+    // only take steps up at fixed periods, so it's impossible to choose a
+    // period that will span enough of the space up to max (in the worst case,
+    // you'll span nearly half the space).
+    //
+    //   0 / ((5 / 4 = 1) + 1 = 2) = 0, which is < 4
+    //   1 / ((5 / 4 = 1) + 1 = 2) = 0, which is < 4
+    //   2 / ((5 / 4 = 1) + 1 = 2) = 1, which is < 4
+    //   3 / ((5 / 4 = 1) + 1 = 2) = 1, which is < 4
+    //   4 / ((5 / 4 = 1) + 1 = 2) = 2, which is < 4
+    //   4 / ((5 / 5 = 1) + 1 = 2) = 2, which is < 4
+    //
+    // random() / (RAND_MAX / (max - 1)) doesn't work either (it's even worse):
+    //
+    //   4 / (5 / (3 - 1 = 2) = 2) = 2, which is < 3
+    //   4 / (5 / (5 - 1 = 4) = 1) = 4, which is < 5
+    //   4 / (5 / (2 - 1 = 1) = 5) = 0, which is < 2, but too much less
+    //   5 / (6 / (3 - 1 = 2) = 3) = 1, which is < 3, but too much less
+    //
+    // OK, this path isn't taking us anywhere.  Let's go back to the original
+    // formula.  Sure, it exceeds max.  But what if we just wrap it back around
+    // when it does?  We can do so using %max.  Success!
+
+    return static_cast<int>( random() / ( RAND_MAX / max ) % max );
+  }
 }
 
 #endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.