OLD | NEW |
---|---|
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/rand_util.h" | 5 #include "base/rand_util.h" |
6 | 6 |
7 #include <limits> | 7 #include <limits> |
8 #include <vector> | |
8 | 9 |
9 #include "testing/gtest/include/gtest/gtest.h" | 10 #include "testing/gtest/include/gtest/gtest.h" |
10 | 11 |
11 namespace { | 12 namespace { |
12 | 13 |
13 const int kIntMin = std::numeric_limits<int>::min(); | 14 const int kIntMin = std::numeric_limits<int>::min(); |
14 const int kIntMax = std::numeric_limits<int>::max(); | 15 const int kIntMax = std::numeric_limits<int>::max(); |
15 | 16 |
16 } // namespace | 17 } // namespace |
17 | 18 |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
54 EXPECT_NE(0, accumulator); | 55 EXPECT_NE(0, accumulator); |
55 } | 56 } |
56 | 57 |
57 // Make sure that it is still appropriate to use RandGenerator in conjunction | 58 // Make sure that it is still appropriate to use RandGenerator in conjunction |
58 // with std::random_shuffle(). | 59 // with std::random_shuffle(). |
59 TEST(RandUtilTest, RandGeneratorForRandomShuffle) { | 60 TEST(RandUtilTest, RandGeneratorForRandomShuffle) { |
60 EXPECT_EQ(base::RandGenerator(1), 0U); | 61 EXPECT_EQ(base::RandGenerator(1), 0U); |
61 EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(), | 62 EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(), |
62 std::numeric_limits<int64>::max()); | 63 std::numeric_limits<int64>::max()); |
63 } | 64 } |
65 | |
66 TEST(RandUtilTest, RandGeneratorIsUniform) { | |
67 // Verify that RandGenerator has a uniform distribution. This is a | |
68 // regression test that consistently failed when RandGenerator was | |
69 // implemented this way: | |
70 // | |
71 // return base::RandUint64() % max; | |
72 // | |
73 // A degenerate case for such an implementation is e.g. a top of range | |
74 // that is 2/3rds of the way to MAX_UINT64, in which case the bottom | |
75 // half of the range would be twice as likely to occur as the top | |
76 // half. | |
77 const uint64 kTopOfRange = (std::numeric_limits<uint64>::max() / 3L) * 2L; | |
78 const uint64 kExpectedAverage = kTopOfRange / 2L; | |
79 const uint64 kAllowedVariance = kExpectedAverage / 50L; // +/- 2% | |
80 const int kMinAttempts = 1000; | |
81 const int kMaxAttempts = 1000000; | |
82 | |
83 double cumulative_average = 0.0; | |
84 int count = 0; | |
85 while (count < kMaxAttempts) { | |
86 uint64 value = base::RandGenerator(kTopOfRange); | |
87 cumulative_average = (count * cumulative_average + value) / (count + 1); | |
88 | |
89 // Don't quit too quickly for things to start converging, or we may have | |
90 // a false positive. | |
91 if (count > kMinAttempts && | |
92 kExpectedAverage - kAllowedVariance < cumulative_average && | |
93 cumulative_average < kExpectedAverage + kAllowedVariance) { | |
94 break; | |
95 } | |
96 | |
97 ++count; | |
98 } | |
99 | |
100 ASSERT_LT(count, kMaxAttempts) << "Expected average was " << | |
101 kExpectedAverage << ", average ended at " << cumulative_average; | |
102 } | |
103 | |
104 TEST(RandUtilTest, RandUint64ProducesBothValuesOfAllBits) { | |
105 // This tests to see that our underlying random generator is good | |
106 // enough, for some value of good enough. | |
107 const size_t kNumBits = sizeof(uint64) * 8; | |
108 std::vector<bool> bits_one(kNumBits, false); | |
109 std::vector<bool> bits_zero(kNumBits, false); | |
110 ASSERT_FALSE(bits_one[0]); | |
111 ASSERT_FALSE(bits_zero[0]); | |
112 | |
113 bool succeeded = false; | |
114 for (size_t i = 0; i < 1000000; ++i) { | |
jar (doing other things)
2011/05/30 17:02:07
Each bit *should* have a 50-50 probabilty. Hence
| |
115 uint64 value = base::RandUint64(); | |
jar (doing other things)
2011/05/30 17:02:07
FYI: You could have used bit-wise AND and bitwise
| |
116 for (uint64 shift = 0; shift < kNumBits; ++shift) { | |
117 uint64 mask = 1ULL << shift; | |
118 uint64 bit = (value & mask) >> shift; | |
119 if (bit == 1ULL) { | |
120 bits_one[shift] = true; | |
121 } else { | |
122 ASSERT_EQ(bit, 0ULL); | |
123 bits_zero[shift] = true; | |
124 } | |
125 } | |
126 | |
127 size_t bit = 0; | |
128 for (; bit < kNumBits; ++bit) { | |
129 if (!bits_one[bit] || !bits_zero[bit]) | |
130 break; | |
131 } | |
132 | |
133 if (bit == kNumBits) { | |
134 succeeded = true; | |
135 break; | |
136 } | |
137 } | |
138 | |
139 ASSERT_TRUE(succeeded) << | |
140 "Didn't achieve all bit values in maximum number of tries."; | |
141 } | |
OLD | NEW |