Index: base/rand_util_unittest.cc |
diff --git a/base/rand_util_unittest.cc b/base/rand_util_unittest.cc |
index d7fa37af827e8589299c4a066ef83308ca4a384a..98b64d08101ffd5500cb31a5ddbec924c8f0e4a8 100644 |
--- a/base/rand_util_unittest.cc |
+++ b/base/rand_util_unittest.cc |
@@ -61,3 +61,47 @@ TEST(RandUtilTest, RandGeneratorForRandomShuffle) { |
EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(), |
std::numeric_limits<int64>::max()); |
} |
+ |
+TEST(RandUtilTest, RandGeneratorIsUniform) { |
brettw
2011/05/27 18:13:21
I'm not super excited about this test. It seems by
Paweł Hajdan Jr.
2011/05/27 19:28:11
Right, everything based on randomness is quite har
Jói
2011/05/27 19:41:48
That wouldn't verify that the random distribution
|
+ // Verify that RandGenerator has a uniform distribution. This is a |
+ // regression test that consistently failed when RandGenerator was |
+ // implemented this way: |
+ // |
+ // return base::RandUint64() % max; |
+ // |
+ // The worst case for such an implementation is e.g. a top of range |
+ // that is 2/3rds of the way to MAX_UINT64, in which case the bottom |
+ // half of the range would be twice as likely to occur as the top |
+ // half, assuming a naive modulus implementation of RandGenerator. |
+ const uint64 kTopOfRange = (std::numeric_limits<uint64>::max() / 3L) * 2L; |
+ const uint64 kExpectedAverage = kTopOfRange / 2L; |
+ const uint64 kAllowedVariance = kExpectedAverage / 100L; // 1% either way. |
Paweł Hajdan Jr.
2011/05/27 19:28:11
nit: 1% seems quite strict, how about something mo
Jói
2011/05/27 19:41:48
The test already passes in an average of 14 ms wal
|
+ const int kMaxAttempts = 1000000; |
+ const int kReportEveryNAttempts = 10000; |
+ |
+ double cumulative_average = 0.0; |
+ int count = 0; |
+ while (count < kMaxAttempts) { |
Paweł Hajdan Jr.
2011/05/27 19:28:11
nit: Why not a for loop then?
Jói
2011/05/27 19:41:48
Because I want to test the value of count after th
|
+ uint64 value = base::RandGenerator(kTopOfRange); |
+ cumulative_average = (count * cumulative_average + value) / (count + 1); |
+ |
+ // Don't quit too quickly for things to start converging. |
+ if (count > 1000) { |
Ilya Sherman
2011/05/27 19:23:26
nit: As long as you're making everything else a na
Jói
2011/05/27 19:41:48
Done.
|
+ if (kExpectedAverage - kAllowedVariance < cumulative_average && |
+ cumulative_average < kExpectedAverage + kAllowedVariance) { |
+ break; |
+ } |
+ } |
+ |
+ if (count >= kReportEveryNAttempts && count % kReportEveryNAttempts == 0) { |
brettw
2011/05/27 18:22:20
I don't think tests should be printing stuff out.
Ilya Sherman
2011/05/27 19:23:26
Yes, please remove these printf()'s, or find a way
Paweł Hajdan Jr.
2011/05/27 19:28:11
Yeah, and also it's better to use LOG or gtest mac
Jói
2011/05/27 19:41:48
Done.
Jói
2011/05/27 19:41:48
Done.
Jói
2011/05/27 19:41:48
Done.
|
+ if (count == kReportEveryNAttempts) |
+ printf("Expected average is %ld\n", kExpectedAverage); |
+ printf("Cumulative average hasn't converged, is %.0f after %d samples.\n", |
+ cumulative_average, count); |
+ } |
+ |
+ ++count; |
+ } |
+ |
+ ASSERT_LT(count, kMaxAttempts); |
+} |