| /* |
| * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. |
| * |
| * Use of this source code is governed by a BSD-style license |
| * that can be found in the LICENSE file in the root of the source |
| * tree. An additional intellectual property rights grant can be found |
| * in the file PATENTS. All contributing project authors may |
| * be found in the AUTHORS file in the root of the source tree. |
| */ |
| |
| #include "rtc_base/random.h" |
| |
| #include <math.h> |
| |
| #include <limits> |
| #include <vector> |
| |
| #include "rtc_base/numerics/math_utils.h" // unsigned difference |
| #include "test/gtest.h" |
| |
| namespace webrtc { |
| |
| namespace { |
| // Computes the positive remainder of x/n. |
| template <typename T> |
| T fdiv_remainder(T x, T n) { |
| RTC_CHECK_GE(n, 0); |
| T remainder = x % n; |
| if (remainder < 0) |
| remainder += n; |
| return remainder; |
| } |
| } // namespace |
| |
| // Sample a number of random integers of type T. Divide them into buckets |
| // based on the remainder when dividing by bucket_count and check that each |
| // bucket gets roughly the expected number of elements. |
| template <typename T> |
| void UniformBucketTest(T bucket_count, int samples, Random* prng) { |
| std::vector<int> buckets(bucket_count, 0); |
| |
| uint64_t total_values = 1ull << (std::numeric_limits<T>::digits + |
| std::numeric_limits<T>::is_signed); |
| T upper_limit = |
| std::numeric_limits<T>::max() - |
| static_cast<T>(total_values % static_cast<uint64_t>(bucket_count)); |
| ASSERT_GT(upper_limit, std::numeric_limits<T>::max() / 2); |
| |
| for (int i = 0; i < samples; i++) { |
| T sample; |
| do { |
| // We exclude a few numbers from the range so that it is divisible by |
| // the number of buckets. If we are unlucky and hit one of the excluded |
| // numbers we just resample. Note that if the number of buckets is a |
| // power of 2, then we don't have to exclude anything. |
| sample = prng->Rand<T>(); |
| } while (sample > upper_limit); |
| buckets[fdiv_remainder(sample, bucket_count)]++; |
| } |
| |
| for (T i = 0; i < bucket_count; i++) { |
| // Expect the result to be within 3 standard deviations of the mean. |
| EXPECT_NEAR(buckets[i], samples / bucket_count, |
| 3 * sqrt(samples / bucket_count)); |
| } |
| } |
| |
| TEST(RandomNumberGeneratorTest, BucketTestSignedChar) { |
| Random prng(7297352569824ull); |
| UniformBucketTest<signed char>(64, 640000, &prng); |
| UniformBucketTest<signed char>(11, 440000, &prng); |
| UniformBucketTest<signed char>(3, 270000, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, BucketTestUnsignedChar) { |
| Random prng(7297352569824ull); |
| UniformBucketTest<unsigned char>(64, 640000, &prng); |
| UniformBucketTest<unsigned char>(11, 440000, &prng); |
| UniformBucketTest<unsigned char>(3, 270000, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, BucketTestSignedShort) { |
| Random prng(7297352569824ull); |
| UniformBucketTest<int16_t>(64, 640000, &prng); |
| UniformBucketTest<int16_t>(11, 440000, &prng); |
| UniformBucketTest<int16_t>(3, 270000, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, BucketTestUnsignedShort) { |
| Random prng(7297352569824ull); |
| UniformBucketTest<uint16_t>(64, 640000, &prng); |
| UniformBucketTest<uint16_t>(11, 440000, &prng); |
| UniformBucketTest<uint16_t>(3, 270000, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, BucketTestSignedInt) { |
| Random prng(7297352569824ull); |
| UniformBucketTest<signed int>(64, 640000, &prng); |
| UniformBucketTest<signed int>(11, 440000, &prng); |
| UniformBucketTest<signed int>(3, 270000, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, BucketTestUnsignedInt) { |
| Random prng(7297352569824ull); |
| UniformBucketTest<unsigned int>(64, 640000, &prng); |
| UniformBucketTest<unsigned int>(11, 440000, &prng); |
| UniformBucketTest<unsigned int>(3, 270000, &prng); |
| } |
| |
| // The range of the random numbers is divided into bucket_count intervals |
| // of consecutive numbers. Check that approximately equally many numbers |
| // from each inteval are generated. |
| void BucketTestSignedInterval(unsigned int bucket_count, |
| unsigned int samples, |
| int32_t low, |
| int32_t high, |
| int sigma_level, |
| Random* prng) { |
| std::vector<unsigned int> buckets(bucket_count, 0); |
| |
| ASSERT_GE(high, low); |
| ASSERT_GE(bucket_count, 2u); |
| uint32_t interval = unsigned_difference<int32_t>(high, low) + 1; |
| uint32_t numbers_per_bucket; |
| if (interval == 0) { |
| // The computation high - low + 1 should be 2^32 but overflowed |
| // Hence, bucket_count must be a power of 2 |
| ASSERT_EQ(bucket_count & (bucket_count - 1), 0u); |
| numbers_per_bucket = (0x80000000u / bucket_count) * 2; |
| } else { |
| ASSERT_EQ(interval % bucket_count, 0u); |
| numbers_per_bucket = interval / bucket_count; |
| } |
| |
| for (unsigned int i = 0; i < samples; i++) { |
| int32_t sample = prng->Rand(low, high); |
| EXPECT_LE(low, sample); |
| EXPECT_GE(high, sample); |
| buckets[unsigned_difference<int32_t>(sample, low) / numbers_per_bucket]++; |
| } |
| |
| for (unsigned int i = 0; i < bucket_count; i++) { |
| // Expect the result to be within 3 standard deviations of the mean, |
| // or more generally, within sigma_level standard deviations of the mean. |
| double mean = static_cast<double>(samples) / bucket_count; |
| EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); |
| } |
| } |
| |
| // The range of the random numbers is divided into bucket_count intervals |
| // of consecutive numbers. Check that approximately equally many numbers |
| // from each inteval are generated. |
| void BucketTestUnsignedInterval(unsigned int bucket_count, |
| unsigned int samples, |
| uint32_t low, |
| uint32_t high, |
| int sigma_level, |
| Random* prng) { |
| std::vector<unsigned int> buckets(bucket_count, 0); |
| |
| ASSERT_GE(high, low); |
| ASSERT_GE(bucket_count, 2u); |
| uint32_t interval = high - low + 1; |
| uint32_t numbers_per_bucket; |
| if (interval == 0) { |
| // The computation high - low + 1 should be 2^32 but overflowed |
| // Hence, bucket_count must be a power of 2 |
| ASSERT_EQ(bucket_count & (bucket_count - 1), 0u); |
| numbers_per_bucket = (0x80000000u / bucket_count) * 2; |
| } else { |
| ASSERT_EQ(interval % bucket_count, 0u); |
| numbers_per_bucket = interval / bucket_count; |
| } |
| |
| for (unsigned int i = 0; i < samples; i++) { |
| uint32_t sample = prng->Rand(low, high); |
| EXPECT_LE(low, sample); |
| EXPECT_GE(high, sample); |
| buckets[(sample - low) / numbers_per_bucket]++; |
| } |
| |
| for (unsigned int i = 0; i < bucket_count; i++) { |
| // Expect the result to be within 3 standard deviations of the mean, |
| // or more generally, within sigma_level standard deviations of the mean. |
| double mean = static_cast<double>(samples) / bucket_count; |
| EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); |
| } |
| } |
| |
| TEST(RandomNumberGeneratorTest, UniformUnsignedInterval) { |
| Random prng(299792458ull); |
| BucketTestUnsignedInterval(2, 100000, 0, 1, 3, &prng); |
| BucketTestUnsignedInterval(7, 100000, 1, 14, 3, &prng); |
| BucketTestUnsignedInterval(11, 100000, 1000, 1010, 3, &prng); |
| BucketTestUnsignedInterval(100, 100000, 0, 99, 3, &prng); |
| BucketTestUnsignedInterval(2, 100000, 0, 4294967295, 3, &prng); |
| BucketTestUnsignedInterval(17, 100000, 455, 2147484110, 3, &prng); |
| // 99.7% of all samples will be within 3 standard deviations of the mean, |
| // but since we test 1000 buckets we allow an interval of 4 sigma. |
| BucketTestUnsignedInterval(1000, 1000000, 0, 2147483999, 4, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, UniformSignedInterval) { |
| Random prng(66260695729ull); |
| BucketTestSignedInterval(2, 100000, 0, 1, 3, &prng); |
| BucketTestSignedInterval(7, 100000, -2, 4, 3, &prng); |
| BucketTestSignedInterval(11, 100000, 1000, 1010, 3, &prng); |
| BucketTestSignedInterval(100, 100000, 0, 99, 3, &prng); |
| BucketTestSignedInterval(2, 100000, std::numeric_limits<int32_t>::min(), |
| std::numeric_limits<int32_t>::max(), 3, &prng); |
| BucketTestSignedInterval(17, 100000, -1073741826, 1073741829, 3, &prng); |
| // 99.7% of all samples will be within 3 standard deviations of the mean, |
| // but since we test 1000 buckets we allow an interval of 4 sigma. |
| BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng); |
| } |
| |
| // The range of the random numbers is divided into bucket_count intervals |
| // of consecutive numbers. Check that approximately equally many numbers |
| // from each inteval are generated. |
| void BucketTestFloat(unsigned int bucket_count, |
| unsigned int samples, |
| int sigma_level, |
| Random* prng) { |
| ASSERT_GE(bucket_count, 2u); |
| std::vector<unsigned int> buckets(bucket_count, 0); |
| |
| for (unsigned int i = 0; i < samples; i++) { |
| uint32_t sample = bucket_count * prng->Rand<float>(); |
| EXPECT_LE(0u, sample); |
| EXPECT_GE(bucket_count - 1, sample); |
| buckets[sample]++; |
| } |
| |
| for (unsigned int i = 0; i < bucket_count; i++) { |
| // Expect the result to be within 3 standard deviations of the mean, |
| // or more generally, within sigma_level standard deviations of the mean. |
| double mean = static_cast<double>(samples) / bucket_count; |
| EXPECT_NEAR(buckets[i], mean, sigma_level * sqrt(mean)); |
| } |
| } |
| |
| TEST(RandomNumberGeneratorTest, UniformFloatInterval) { |
| Random prng(1380648813ull); |
| BucketTestFloat(100, 100000, 3, &prng); |
| // 99.7% of all samples will be within 3 standard deviations of the mean, |
| // but since we test 1000 buckets we allow an interval of 4 sigma. |
| // BucketTestSignedInterval(1000, 1000000, -352, 2147483647, 4, &prng); |
| } |
| |
| TEST(RandomNumberGeneratorTest, SignedHasSameBitPattern) { |
| Random prng_signed(66738480ull), prng_unsigned(66738480ull); |
| |
| for (int i = 0; i < 1000; i++) { |
| signed int s = prng_signed.Rand<signed int>(); |
| unsigned int u = prng_unsigned.Rand<unsigned int>(); |
| EXPECT_EQ(u, static_cast<unsigned int>(s)); |
| } |
| |
| for (int i = 0; i < 1000; i++) { |
| int16_t s = prng_signed.Rand<int16_t>(); |
| uint16_t u = prng_unsigned.Rand<uint16_t>(); |
| EXPECT_EQ(u, static_cast<uint16_t>(s)); |
| } |
| |
| for (int i = 0; i < 1000; i++) { |
| signed char s = prng_signed.Rand<signed char>(); |
| unsigned char u = prng_unsigned.Rand<unsigned char>(); |
| EXPECT_EQ(u, static_cast<unsigned char>(s)); |
| } |
| } |
| |
| TEST(RandomNumberGeneratorTest, Gaussian) { |
| const int kN = 100000; |
| const int kBuckets = 100; |
| const double kMean = 49; |
| const double kStddev = 10; |
| |
| Random prng(1256637061); |
| |
| std::vector<unsigned int> buckets(kBuckets, 0); |
| for (int i = 0; i < kN; i++) { |
| int index = prng.Gaussian(kMean, kStddev) + 0.5; |
| if (index >= 0 && index < kBuckets) { |
| buckets[index]++; |
| } |
| } |
| |
| const double kPi = 3.14159265358979323846; |
| const double kScale = 1 / (kStddev * sqrt(2.0 * kPi)); |
| const double kDiv = -2.0 * kStddev * kStddev; |
| for (int n = 0; n < kBuckets; ++n) { |
| // Use Simpsons rule to estimate the probability that a random gaussian |
| // sample is in the interval [n-0.5, n+0.5]. |
| double f_left = kScale * exp((n - kMean - 0.5) * (n - kMean - 0.5) / kDiv); |
| double f_mid = kScale * exp((n - kMean) * (n - kMean) / kDiv); |
| double f_right = kScale * exp((n - kMean + 0.5) * (n - kMean + 0.5) / kDiv); |
| double normal_dist = (f_left + 4 * f_mid + f_right) / 6; |
| // Expect the number of samples to be within 3 standard deviations |
| // (rounded up) of the expected number of samples in the bucket. |
| EXPECT_NEAR(buckets[n], kN * normal_dist, 3 * sqrt(kN * normal_dist) + 1); |
| } |
| } |
| |
| } // namespace webrtc |