1 /* 2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #include <math.h> 12 13 #include <limits> 14 #include <vector> 15 16 #include "testing/gtest/include/gtest/gtest.h" 17 #include "webrtc/base/random.h" 18 19 namespace webrtc { 20 21 namespace { 22 // Computes the positive remainder of x/n. 23 template <typename T> 24 T fdiv_remainder(T x, T n) { 25 RTC_CHECK_GE(n, static_cast<T>(0)); 26 T remainder = x % n; 27 if (remainder < 0) 28 remainder += n; 29 return remainder; 30 } 31 } // namespace 32 33 // Sample a number of random integers of type T. Divide them into buckets 34 // based on the remainder when dividing by bucket_count and check that each 35 // bucket gets roughly the expected number of elements. 36 template <typename T> 37 void UniformBucketTest(T bucket_count, int samples, Random* prng) { 38 std::vector<int> buckets(bucket_count, 0); 39 40 uint64_t total_values = 1ull << (std::numeric_limits<T>::digits + 41 std::numeric_limits<T>::is_signed); 42 T upper_limit = 43 std::numeric_limits<T>::max() - 44 static_cast<T>(total_values % static_cast<uint64_t>(bucket_count)); 45 ASSERT_GT(upper_limit, std::numeric_limits<T>::max() / 2); 46 47 for (int i = 0; i < samples; i++) { 48 T sample; 49 do { 50 // We exclude a few numbers from the range so that it is divisible by 51 // the number of buckets. If we are unlucky and hit one of the excluded 52 // numbers we just resample. Note that if the number of buckets is a 53 // power of 2, then we don't have to exclude anything. 54 sample = prng->Rand<T>(); 55 } while (sample > upper_limit); 56 buckets[fdiv_remainder(sample, bucket_count)]++; 57 } 58 59 for (T i = 0; i < bucket_count; i++) { 60 // Expect the result to be within 3 standard deviations of the mean. 61 EXPECT_NEAR(buckets[i], samples / bucket_count, 62 3 * sqrt(samples / bucket_count)); 63 } 64 } 65 66 TEST(RandomNumberGeneratorTest, BucketTestSignedChar) { 67 Random prng(7297352569824ull); 68 UniformBucketTest<signed char>(64, 640000, &prng); 69 UniformBucketTest<signed char>(11, 440000, &prng); 70 UniformBucketTest<signed char>(3, 270000, &prng); 71 } 72 73 TEST(RandomNumberGeneratorTest, BucketTestUnsignedChar) { 74 Random prng(7297352569824ull); 75 UniformBucketTest<unsigned char>(64, 640000, &prng); 76 UniformBucketTest<unsigned char>(11, 440000, &prng); 77 UniformBucketTest<unsigned char>(3, 270000, &prng); 78 } 79 80 TEST(RandomNumberGeneratorTest, BucketTestSignedShort) { 81 Random prng(7297352569824ull); 82 UniformBucketTest<int16_t>(64, 640000, &prng); 83 UniformBucketTest<int16_t>(11, 440000, &prng); 84 UniformBucketTest<int16_t>(3, 270000, &prng); 85 } 86 87 TEST(RandomNumberGeneratorTest, BucketTestUnsignedShort) { 88 Random prng(7297352569824ull); 89 UniformBucketTest<uint16_t>(64, 640000, &prng); 90 UniformBucketTest<uint16_t>(11, 440000, &prng); 91 UniformBucketTest<uint16_t>(3, 270000, &prng); 92 } 93 94 TEST(RandomNumberGeneratorTest, BucketTestSignedInt) { 95 Random prng(7297352569824ull); 96 UniformBucketTest<signed int>(64, 640000, &prng); 97 UniformBucketTest<signed int>(11, 440000, &prng); 98 UniformBucketTest<signed int>(3, 270000, &prng); 99 } 100 101 TEST(RandomNumberGeneratorTest, BucketTestUnsignedInt) { 102 Random prng(7297352569824ull); 103 UniformBucketTest<unsigned int>(64, 640000, &prng); 104 UniformBucketTest<unsigned int>(11, 440000, &prng); 105 UniformBucketTest<unsigned int>(3, 270000, &prng); 106 } 107 108 // The range of the random numbers is divided into bucket_count intervals 109 // of consecutive numbers. Check that approximately equally many numbers 110 // from each inteval are generated. 111 void BucketTestSignedInterval(unsigned int bucket_count, 112 unsigned int samples, 113 int32_t low, 114 int32_t high, 115 int sigma_level, 116 Random* prng) { 117 std::vector<unsigned int> buckets(bucket_count, 0); 118 119 ASSERT_GE(high, low); 120 ASSERT_GE(bucket_count, 2u); 121 uint32_t interval = static_cast<uint32_t>(high - low + 1); 122 uint32_t numbers_per_bucket; 123 if (interval == 0) { 124 // The computation high - low + 1 should be 2^32 but overflowed 125 // Hence, bucket_count must be a power of 2 126 ASSERT_EQ(bucket_count & (bucket_count - 1), 0u); 127 numbers_per_bucket = (0x80000000u / bucket_count) * 2; 128 } else { 129 ASSERT_EQ(interval % bucket_count, 0u); 130 numbers_per_bucket = interval / bucket_count; 131 } 132 133 for (unsigned int i = 0; i < samples; i++) { 134 int32_t sample = prng->Rand(low, high); 135 EXPECT_LE(low, sample); 136 EXPECT_GE(high, sample); 137 buckets[static_cast<uint32_t>(sample - low) / numbers_per_bucket]++; 138 } 139 140 for (unsigned int i = 0; i < bucket_count; i++) { 141 // Expect the result to be within 3 standard deviations of the mean, 142 // or more generally, within sigma_level standard deviations of the mean. 143 double mean = static_cast<double>(samples) / bucket_count; 144 EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); 145 } 146 } 147 148 // The range of the random numbers is divided into bucket_count intervals 149 // of consecutive numbers. Check that approximately equally many numbers 150 // from each inteval are generated. 151 void BucketTestUnsignedInterval(unsigned int bucket_count, 152 unsigned int samples, 153 uint32_t low, 154 uint32_t high, 155 int sigma_level, 156 Random* prng) { 157 std::vector<unsigned int> buckets(bucket_count, 0); 158 159 ASSERT_GE(high, low); 160 ASSERT_GE(bucket_count, 2u); 161 uint32_t interval = static_cast<uint32_t>(high - low + 1); 162 uint32_t numbers_per_bucket; 163 if (interval == 0) { 164 // The computation high - low + 1 should be 2^32 but overflowed 165 // Hence, bucket_count must be a power of 2 166 ASSERT_EQ(bucket_count & (bucket_count - 1), 0u); 167 numbers_per_bucket = (0x80000000u / bucket_count) * 2; 168 } else { 169 ASSERT_EQ(interval % bucket_count, 0u); 170 numbers_per_bucket = interval / bucket_count; 171 } 172 173 for (unsigned int i = 0; i < samples; i++) { 174 uint32_t sample = prng->Rand(low, high); 175 EXPECT_LE(low, sample); 176 EXPECT_GE(high, sample); 177 buckets[static_cast<uint32_t>(sample - low) / numbers_per_bucket]++; 178 } 179 180 for (unsigned int i = 0; i < bucket_count; i++) { 181 // Expect the result to be within 3 standard deviations of the mean, 182 // or more generally, within sigma_level standard deviations of the mean. 183 double mean = static_cast<double>(samples) / bucket_count; 184 EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); 185 } 186 } 187 188 TEST(RandomNumberGeneratorTest, UniformUnsignedInterval) { 189 Random prng(299792458ull); 190 BucketTestUnsignedInterval(2, 100000, 0, 1, 3, &prng); 191 BucketTestUnsignedInterval(7, 100000, 1, 14, 3, &prng); 192 BucketTestUnsignedInterval(11, 100000, 1000, 1010, 3, &prng); 193 BucketTestUnsignedInterval(100, 100000, 0, 99, 3, &prng); 194 BucketTestUnsignedInterval(2, 100000, 0, 4294967295, 3, &prng); 195 BucketTestUnsignedInterval(17, 100000, 455, 2147484110, 3, &prng); 196 // 99.7% of all samples will be within 3 standard deviations of the mean, 197 // but since we test 1000 buckets we allow an interval of 4 sigma. 198 BucketTestUnsignedInterval(1000, 1000000, 0, 2147483999, 4, &prng); 199 } 200 201 TEST(RandomNumberGeneratorTest, UniformSignedInterval) { 202 Random prng(66260695729ull); 203 BucketTestSignedInterval(2, 100000, 0, 1, 3, &prng); 204 BucketTestSignedInterval(7, 100000, -2, 4, 3, &prng); 205 BucketTestSignedInterval(11, 100000, 1000, 1010, 3, &prng); 206 BucketTestSignedInterval(100, 100000, 0, 99, 3, &prng); 207 BucketTestSignedInterval(2, 100000, std::numeric_limits<int32_t>::min(), 208 std::numeric_limits<int32_t>::max(), 3, &prng); 209 BucketTestSignedInterval(17, 100000, -1073741826, 1073741829, 3, &prng); 210 // 99.7% of all samples will be within 3 standard deviations of the mean, 211 // but since we test 1000 buckets we allow an interval of 4 sigma. 212 BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng); 213 } 214 215 // The range of the random numbers is divided into bucket_count intervals 216 // of consecutive numbers. Check that approximately equally many numbers 217 // from each inteval are generated. 218 void BucketTestFloat(unsigned int bucket_count, 219 unsigned int samples, 220 int sigma_level, 221 Random* prng) { 222 ASSERT_GE(bucket_count, 2u); 223 std::vector<unsigned int> buckets(bucket_count, 0); 224 225 for (unsigned int i = 0; i < samples; i++) { 226 uint32_t sample = bucket_count * prng->Rand<float>(); 227 EXPECT_LE(0u, sample); 228 EXPECT_GE(bucket_count - 1, sample); 229 buckets[sample]++; 230 } 231 232 for (unsigned int i = 0; i < bucket_count; i++) { 233 // Expect the result to be within 3 standard deviations of the mean, 234 // or more generally, within sigma_level standard deviations of the mean. 235 double mean = static_cast<double>(samples) / bucket_count; 236 EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); 237 } 238 } 239 240 TEST(RandomNumberGeneratorTest, UniformFloatInterval) { 241 Random prng(1380648813ull); 242 BucketTestFloat(100, 100000, 3, &prng); 243 // 99.7% of all samples will be within 3 standard deviations of the mean, 244 // but since we test 1000 buckets we allow an interval of 4 sigma. 245 // BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng); 246 } 247 248 TEST(RandomNumberGeneratorTest, SignedHasSameBitPattern) { 249 Random prng_signed(66738480ull), prng_unsigned(66738480ull); 250 251 for (int i = 0; i < 1000; i++) { 252 signed int s = prng_signed.Rand<signed int>(); 253 unsigned int u = prng_unsigned.Rand<unsigned int>(); 254 EXPECT_EQ(u, static_cast<unsigned int>(s)); 255 } 256 257 for (int i = 0; i < 1000; i++) { 258 int16_t s = prng_signed.Rand<int16_t>(); 259 uint16_t u = prng_unsigned.Rand<uint16_t>(); 260 EXPECT_EQ(u, static_cast<uint16_t>(s)); 261 } 262 263 for (int i = 0; i < 1000; i++) { 264 signed char s = prng_signed.Rand<signed char>(); 265 unsigned char u = prng_unsigned.Rand<unsigned char>(); 266 EXPECT_EQ(u, static_cast<unsigned char>(s)); 267 } 268 } 269 270 TEST(RandomNumberGeneratorTest, Gaussian) { 271 const int kN = 100000; 272 const int kBuckets = 100; 273 const double kMean = 49; 274 const double kStddev = 10; 275 276 Random prng(1256637061); 277 278 std::vector<unsigned int> buckets(kBuckets, 0); 279 for (int i = 0; i < kN; i++) { 280 int index = prng.Gaussian(kMean, kStddev) + 0.5; 281 if (index >= 0 && index < kBuckets) { 282 buckets[index]++; 283 } 284 } 285 286 const double kPi = 3.14159265358979323846; 287 const double kScale = 1 / (kStddev * sqrt(2.0 * kPi)); 288 const double kDiv = -2.0 * kStddev * kStddev; 289 for (int n = 0; n < kBuckets; ++n) { 290 // Use Simpsons rule to estimate the probability that a random gaussian 291 // sample is in the interval [n-0.5, n+0.5]. 292 double f_left = kScale * exp((n - kMean - 0.5) * (n - kMean - 0.5) / kDiv); 293 double f_mid = kScale * exp((n - kMean) * (n - kMean) / kDiv); 294 double f_right = kScale * exp((n - kMean + 0.5) * (n - kMean + 0.5) / kDiv); 295 double normal_dist = (f_left + 4 * f_mid + f_right) / 6; 296 // Expect the number of samples to be within 3 standard deviations 297 // (rounded up) of the expected number of samples in the bucket. 298 EXPECT_NEAR(buckets[n], kN * normal_dist, 3 * sqrt(kN * normal_dist) + 1); 299 } 300 } 301 302 } // namespace webrtc 303