Fix base::RandGenerator bug (it had non-uniform random distribution).

base/rand_util.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/rand_util.h"
 
 #include <math.h>
 
 #include <limits>
 
@@ skipping 27 matching lines @@
   static const int kBits = std::numeric_limits<double>::digits;
   uint64 random_bits = bits & ((GG_UINT64_C(1) << kBits) - 1);
   double result = ldexp(static_cast<double>(random_bits), -1 * kBits);
   DCHECK_GE(result, 0.0);
   DCHECK_LT(result, 1.0);
   return result;
 }
 
 uint64 RandGenerator(uint64 max) {
   DCHECK_GT(max, 0ULL);
-  return base::RandUint64() % max;
+
+  // We must discard random results above this number, as they would
+  // make the random generator non-uniform (consider e.g. if
+  // MAX_UINT64 was 4 and max was 3, then a result of 1 would be twice
+  // as likely as a result of 0 or 2).
+  uint64 max_acceptable_value =
+      (std::numeric_limits<uint64>::max() / max) * max;
+
+  uint64 value;
+  do {
+    value = base::RandUint64();
+  } while (value > max_acceptable_value);

[jar (doing other things), 2011/05/27 20:25:14]

Very cute.... but I think there is a typo, and this should read:

while(value >= max_acceptable_value)

Am I confused??

I think this currently gives a higher probability of returning 0 than any other
number in the range.

[Jói, 2011/05/27 23:18:01]

You're right, thanks for catching that. Fixed and uploaded a new version.

[jar (doing other things), 2011/05/28 17:26:40]

OK... With that change I'm convinced it is "right," but when I've seen this code
historically in many codebases, (despite being aware of the bias), I never
thought it was significant (with uint64 max being a whopping 2^64).  The fact
that your first patch introduced this class of bias (due to a typo) and was
virtually undetectable partially substantiates my wonder.

For my edification, can you cite how this bias was burning you in your code? 

For example, when max is 3, the bias in randomness amounts to roughly 1 in 2^62.
 I strongly suspect the underlying rand to have biases of that order.   I'd
expect you'd need to perform a LOT of experiments before you could detect that
bias.  

You tested the other extreme, where max is very close to 2^64.  (see interesting
comment in the test).

When max is that large, each sample comes from a GIANT range.  As a result, any
small number of samples will come with a large bias because we don't come any
where near to getting enough samples to prove the range of answers are all even
possible :-/.

What is the example where this was harming you in a measurable way?

Again, the change is IMO "right."  rand is a real slow function usually, so I
don't like to see too many extra calls... but the likelihood of such extras are
small for most all users (who stay away from a giant max, that is not nearly a
power of 2).


On 2011/05/27 23:18:01, Jói wrote:

+
+  return value % max;
 }
 
 void RandBytes(void* output, size_t output_length) {
   uint64 random_int;
   size_t random_int_size = sizeof(random_int);
   for (size_t i = 0; i < output_length; i += random_int_size) {
     random_int = base::RandUint64();
     size_t copy_count = std::min(output_length - i, random_int_size);
     memcpy(((uint8*)output) + i, &random_int, copy_count);
   }
 }
 
 std::string RandBytesAsString(size_t length) {
   std::string result;
   RandBytes(WriteInto(&result, length + 1), length);
   return result;
 }
 
 }  // namespace base