xref: /aosp_15_r20/external/abseil-cpp/absl/random/gaussian_distribution_test.cc (revision 9356374a3709195abf420251b3e825997ff56c0f)
1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "absl/random/gaussian_distribution.h"
16 
17 #include <algorithm>
18 #include <cmath>
19 #include <cstddef>
20 #include <ios>
21 #include <iterator>
22 #include <random>
23 #include <string>
24 #include <type_traits>
25 #include <vector>
26 
27 #include "gmock/gmock.h"
28 #include "gtest/gtest.h"
29 #include "absl/base/macros.h"
30 #include "absl/log/log.h"
31 #include "absl/numeric/internal/representation.h"
32 #include "absl/random/internal/chi_square.h"
33 #include "absl/random/internal/distribution_test_util.h"
34 #include "absl/random/internal/sequence_urbg.h"
35 #include "absl/random/random.h"
36 #include "absl/strings/str_cat.h"
37 #include "absl/strings/str_format.h"
38 #include "absl/strings/str_replace.h"
39 #include "absl/strings/strip.h"
40 
41 namespace {
42 
43 using absl::random_internal::kChiSquared;
44 
45 template <typename RealType>
46 class GaussianDistributionInterfaceTest : public ::testing::Test {};
47 
48 // double-double arithmetic is not supported well by either GCC or Clang; see
49 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048,
50 // https://bugs.llvm.org/show_bug.cgi?id=49131, and
51 // https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests
52 // with double doubles until compiler support is better.
53 using RealTypes =
54     std::conditional<absl::numeric_internal::IsDoubleDouble(),
55                      ::testing::Types<float, double>,
56                      ::testing::Types<float, double, long double>>::type;
57 TYPED_TEST_SUITE(GaussianDistributionInterfaceTest, RealTypes);
58 
TYPED_TEST(GaussianDistributionInterfaceTest,SerializeTest)59 TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) {
60   using param_type =
61       typename absl::gaussian_distribution<TypeParam>::param_type;
62 
63   const TypeParam kParams[] = {
64       // Cases around 1.
65       1,                                           //
66       std::nextafter(TypeParam(1), TypeParam(0)),  // 1 - epsilon
67       std::nextafter(TypeParam(1), TypeParam(2)),  // 1 + epsilon
68       // Arbitrary values.
69       TypeParam(1e-8), TypeParam(1e-4), TypeParam(2), TypeParam(1e4),
70       TypeParam(1e8), TypeParam(1e20), TypeParam(2.5),
71       // Boundary cases.
72       std::numeric_limits<TypeParam>::infinity(),
73       std::numeric_limits<TypeParam>::max(),
74       std::numeric_limits<TypeParam>::epsilon(),
75       std::nextafter(std::numeric_limits<TypeParam>::min(),
76                      TypeParam(1)),           // min + epsilon
77       std::numeric_limits<TypeParam>::min(),  // smallest normal
78       // There are some errors dealing with denorms on apple platforms.
79       std::numeric_limits<TypeParam>::denorm_min(),  // smallest denorm
80       std::numeric_limits<TypeParam>::min() / 2,
81       std::nextafter(std::numeric_limits<TypeParam>::min(),
82                      TypeParam(0)),  // denorm_max
83   };
84 
85   constexpr int kCount = 1000;
86   absl::InsecureBitGen gen;
87 
88   // Use a loop to generate the combinations of {+/-x, +/-y}, and assign x, y to
89   // all values in kParams,
90   for (const auto mod : {0, 1, 2, 3}) {
91     for (const auto x : kParams) {
92       if (!std::isfinite(x)) continue;
93       for (const auto y : kParams) {
94         const TypeParam mean = (mod & 0x1) ? -x : x;
95         const TypeParam stddev = (mod & 0x2) ? -y : y;
96         const param_type param(mean, stddev);
97 
98         absl::gaussian_distribution<TypeParam> before(mean, stddev);
99         EXPECT_EQ(before.mean(), param.mean());
100         EXPECT_EQ(before.stddev(), param.stddev());
101 
102         {
103           absl::gaussian_distribution<TypeParam> via_param(param);
104           EXPECT_EQ(via_param, before);
105           EXPECT_EQ(via_param.param(), before.param());
106         }
107 
108         // Smoke test.
109         auto sample_min = before.max();
110         auto sample_max = before.min();
111         for (int i = 0; i < kCount; i++) {
112           auto sample = before(gen);
113           if (sample > sample_max) sample_max = sample;
114           if (sample < sample_min) sample_min = sample;
115           EXPECT_GE(sample, before.min()) << before;
116           EXPECT_LE(sample, before.max()) << before;
117         }
118         if (!std::is_same<TypeParam, long double>::value) {
119           LOG(INFO) << "Range{" << mean << ", " << stddev << "}: " << sample_min
120                     << ", " << sample_max;
121         }
122 
123         std::stringstream ss;
124         ss << before;
125 
126         if (!std::isfinite(mean) || !std::isfinite(stddev)) {
127           // Streams do not parse inf/nan.
128           continue;
129         }
130 
131         // Validate stream serialization.
132         absl::gaussian_distribution<TypeParam> after(-0.53f, 2.3456f);
133 
134         EXPECT_NE(before.mean(), after.mean());
135         EXPECT_NE(before.stddev(), after.stddev());
136         EXPECT_NE(before.param(), after.param());
137         EXPECT_NE(before, after);
138 
139         ss >> after;
140 
141         EXPECT_EQ(before.mean(), after.mean());
142         EXPECT_EQ(before.stddev(), after.stddev())  //
143             << ss.str() << " "                      //
144             << (ss.good() ? "good " : "")           //
145             << (ss.bad() ? "bad " : "")             //
146             << (ss.eof() ? "eof " : "")             //
147             << (ss.fail() ? "fail " : "");
148       }
149     }
150   }
151 }
152 
153 // http://www.itl.nist.gov/div898/handbook/eda/section3/eda3661.htm
154 
155 class GaussianModel {
156  public:
GaussianModel(double mean,double stddev)157   GaussianModel(double mean, double stddev) : mean_(mean), stddev_(stddev) {}
158 
mean() const159   double mean() const { return mean_; }
variance() const160   double variance() const { return stddev() * stddev(); }
stddev() const161   double stddev() const { return stddev_; }
skew() const162   double skew() const { return 0; }
kurtosis() const163   double kurtosis() const { return 3.0; }
164 
165   // The inverse CDF, or PercentPoint function.
InverseCDF(double p)166   double InverseCDF(double p) {
167     ABSL_ASSERT(p >= 0.0);
168     ABSL_ASSERT(p < 1.0);
169     return mean() + stddev() * -absl::random_internal::InverseNormalSurvival(p);
170   }
171 
172  private:
173   const double mean_;
174   const double stddev_;
175 };
176 
177 struct Param {
178   double mean;
179   double stddev;
180   double p_fail;  // Z-Test probability of failure.
181   int trials;     // Z-Test trials.
182 };
183 
184 // GaussianDistributionTests implements a z-test for the gaussian
185 // distribution.
186 class GaussianDistributionTests : public testing::TestWithParam<Param>,
187                                   public GaussianModel {
188  public:
GaussianDistributionTests()189   GaussianDistributionTests()
190       : GaussianModel(GetParam().mean, GetParam().stddev) {}
191 
192   // SingleZTest provides a basic z-squared test of the mean vs. expected
193   // mean for data generated by the poisson distribution.
194   template <typename D>
195   bool SingleZTest(const double p, const size_t samples);
196 
197   // SingleChiSquaredTest provides a basic chi-squared test of the normal
198   // distribution.
199   template <typename D>
200   double SingleChiSquaredTest();
201 
202   // We use a fixed bit generator for distribution accuracy tests.  This allows
203   // these tests to be deterministic, while still testing the qualify of the
204   // implementation.
205   absl::random_internal::pcg64_2018_engine rng_{0x2B7E151628AED2A6};
206 };
207 
208 template <typename D>
SingleZTest(const double p,const size_t samples)209 bool GaussianDistributionTests::SingleZTest(const double p,
210                                             const size_t samples) {
211   D dis(mean(), stddev());
212 
213   std::vector<double> data;
214   data.reserve(samples);
215   for (size_t i = 0; i < samples; i++) {
216     const double x = dis(rng_);
217     data.push_back(x);
218   }
219 
220   const double max_err = absl::random_internal::MaxErrorTolerance(p);
221   const auto m = absl::random_internal::ComputeDistributionMoments(data);
222   const double z = absl::random_internal::ZScore(mean(), m);
223   const bool pass = absl::random_internal::Near("z", z, 0.0, max_err);
224 
225   // NOTE: Informational statistical test:
226   //
227   // Compute the Jarque-Bera test statistic given the excess skewness
228   // and kurtosis. The statistic is drawn from a chi-square(2) distribution.
229   // https://en.wikipedia.org/wiki/Jarque%E2%80%93Bera_test
230   //
231   // The null-hypothesis (normal distribution) is rejected when
232   // (p = 0.05 => jb > 5.99)
233   // (p = 0.01 => jb > 9.21)
234   // NOTE: JB has a large type-I error rate, so it will reject the
235   // null-hypothesis even when it is true more often than the z-test.
236   //
237   const double jb =
238       static_cast<double>(m.n) / 6.0 *
239       (std::pow(m.skewness, 2.0) + std::pow(m.kurtosis - 3.0, 2.0) / 4.0);
240 
241   if (!pass || jb > 9.21) {
242     // clang-format off
243     LOG(INFO)
244         << "p=" << p << " max_err=" << max_err << "\n"
245            " mean=" << m.mean << " vs. " << mean() << "\n"
246            " stddev=" << std::sqrt(m.variance) << " vs. " << stddev() << "\n"
247            " skewness=" << m.skewness << " vs. " << skew() << "\n"
248            " kurtosis=" << m.kurtosis << " vs. " << kurtosis() << "\n"
249            " z=" << z << " vs. 0\n"
250            " jb=" << jb << " vs. 9.21";
251     // clang-format on
252   }
253   return pass;
254 }
255 
256 template <typename D>
SingleChiSquaredTest()257 double GaussianDistributionTests::SingleChiSquaredTest() {
258   const size_t kSamples = 10000;
259   const int kBuckets = 50;
260 
261   // The InverseCDF is the percent point function of the
262   // distribution, and can be used to assign buckets
263   // roughly uniformly.
264   std::vector<double> cutoffs;
265   const double kInc = 1.0 / static_cast<double>(kBuckets);
266   for (double p = kInc; p < 1.0; p += kInc) {
267     cutoffs.push_back(InverseCDF(p));
268   }
269   if (cutoffs.back() != std::numeric_limits<double>::infinity()) {
270     cutoffs.push_back(std::numeric_limits<double>::infinity());
271   }
272 
273   D dis(mean(), stddev());
274 
275   std::vector<int32_t> counts(cutoffs.size(), 0);
276   for (int j = 0; j < kSamples; j++) {
277     const double x = dis(rng_);
278     auto it = std::upper_bound(cutoffs.begin(), cutoffs.end(), x);
279     counts[std::distance(cutoffs.begin(), it)]++;
280   }
281 
282   // Null-hypothesis is that the distribution is a gaussian distribution
283   // with the provided mean and stddev (not estimated from the data).
284   const int dof = static_cast<int>(counts.size()) - 1;
285 
286   // Our threshold for logging is 1-in-50.
287   const double threshold = absl::random_internal::ChiSquareValue(dof, 0.98);
288 
289   const double expected =
290       static_cast<double>(kSamples) / static_cast<double>(counts.size());
291 
292   double chi_square = absl::random_internal::ChiSquareWithExpected(
293       std::begin(counts), std::end(counts), expected);
294   double p = absl::random_internal::ChiSquarePValue(chi_square, dof);
295 
296   // Log if the chi_square value is above the threshold.
297   if (chi_square > threshold) {
298     for (size_t i = 0; i < cutoffs.size(); i++) {
299       LOG(INFO) << i << " : (" << cutoffs[i] << ") = " << counts[i];
300     }
301 
302     // clang-format off
303     LOG(INFO) << "mean=" << mean() << " stddev=" << stddev() << "\n"
304                  " expected " << expected << "\n"
305               << kChiSquared << " " << chi_square << " (" << p << ")\n"
306               << kChiSquared << " @ 0.98 = " << threshold;
307     // clang-format on
308   }
309   return p;
310 }
311 
TEST_P(GaussianDistributionTests,ZTest)312 TEST_P(GaussianDistributionTests, ZTest) {
313   // TODO(absl-team): Run these tests against std::normal_distribution<double>
314   // to validate outcomes are similar.
315   const size_t kSamples = 10000;
316   const auto& param = GetParam();
317   const int expected_failures =
318       std::max(1, static_cast<int>(std::ceil(param.trials * param.p_fail)));
319   const double p = absl::random_internal::RequiredSuccessProbability(
320       param.p_fail, param.trials);
321 
322   int failures = 0;
323   for (int i = 0; i < param.trials; i++) {
324     failures +=
325         SingleZTest<absl::gaussian_distribution<double>>(p, kSamples) ? 0 : 1;
326   }
327   EXPECT_LE(failures, expected_failures);
328 }
329 
TEST_P(GaussianDistributionTests,ChiSquaredTest)330 TEST_P(GaussianDistributionTests, ChiSquaredTest) {
331   const int kTrials = 20;
332   int failures = 0;
333 
334   for (int i = 0; i < kTrials; i++) {
335     double p_value =
336         SingleChiSquaredTest<absl::gaussian_distribution<double>>();
337     if (p_value < 0.0025) {  // 1/400
338       failures++;
339     }
340   }
341   // There is a 0.05% chance of producing at least one failure, so raise the
342   // failure threshold high enough to allow for a flake rate of less than one in
343   // 10,000.
344   EXPECT_LE(failures, 4);
345 }
346 
GenParams()347 std::vector<Param> GenParams() {
348   return {
349       // Mean around 0.
350       Param{0.0, 1.0, 0.01, 100},
351       Param{0.0, 1e2, 0.01, 100},
352       Param{0.0, 1e4, 0.01, 100},
353       Param{0.0, 1e8, 0.01, 100},
354       Param{0.0, 1e16, 0.01, 100},
355       Param{0.0, 1e-3, 0.01, 100},
356       Param{0.0, 1e-5, 0.01, 100},
357       Param{0.0, 1e-9, 0.01, 100},
358       Param{0.0, 1e-17, 0.01, 100},
359 
360       // Mean around 1.
361       Param{1.0, 1.0, 0.01, 100},
362       Param{1.0, 1e2, 0.01, 100},
363       Param{1.0, 1e-2, 0.01, 100},
364 
365       // Mean around 100 / -100
366       Param{1e2, 1.0, 0.01, 100},
367       Param{-1e2, 1.0, 0.01, 100},
368       Param{1e2, 1e6, 0.01, 100},
369       Param{-1e2, 1e6, 0.01, 100},
370 
371       // More extreme
372       Param{1e4, 1e4, 0.01, 100},
373       Param{1e8, 1e4, 0.01, 100},
374       Param{1e12, 1e4, 0.01, 100},
375   };
376 }
377 
ParamName(const::testing::TestParamInfo<Param> & info)378 std::string ParamName(const ::testing::TestParamInfo<Param>& info) {
379   const auto& p = info.param;
380   std::string name = absl::StrCat("mean_", absl::SixDigits(p.mean), "__stddev_",
381                                   absl::SixDigits(p.stddev));
382   return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}});
383 }
384 
385 INSTANTIATE_TEST_SUITE_P(All, GaussianDistributionTests,
386                          ::testing::ValuesIn(GenParams()), ParamName);
387 
388 // NOTE: absl::gaussian_distribution is not guaranteed to be stable.
TEST(GaussianDistributionTest,StabilityTest)389 TEST(GaussianDistributionTest, StabilityTest) {
390   // absl::gaussian_distribution stability relies on the underlying zignor
391   // data, absl::random_interna::RandU64ToDouble, std::exp, std::log, and
392   // std::abs.
393   absl::random_internal::sequence_urbg urbg(
394       {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull,
395        0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull,
396        0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull,
397        0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull});
398 
399   std::vector<int> output(11);
400 
401   {
402     absl::gaussian_distribution<double> dist;
403     std::generate(std::begin(output), std::end(output),
404                   [&] { return static_cast<int>(10000000.0 * dist(urbg)); });
405 
406     EXPECT_EQ(13, urbg.invocations());
407     EXPECT_THAT(output,  //
408                 testing::ElementsAre(1494, 25518841, 9991550, 1351856,
409                                      -20373238, 3456682, 333530, -6804981,
410                                      -15279580, -16459654, 1494));
411   }
412 
413   urbg.reset();
414   {
415     absl::gaussian_distribution<float> dist;
416     std::generate(std::begin(output), std::end(output),
417                   [&] { return static_cast<int>(1000000.0f * dist(urbg)); });
418 
419     EXPECT_EQ(13, urbg.invocations());
420     EXPECT_THAT(
421         output,  //
422         testing::ElementsAre(149, 2551884, 999155, 135185, -2037323, 345668,
423                              33353, -680498, -1527958, -1645965, 149));
424   }
425 }
426 
427 // This is an implementation-specific test. If any part of the implementation
428 // changes, then it is likely that this test will change as well.
429 // Also, if dependencies of the distribution change, such as RandU64ToDouble,
430 // then this is also likely to change.
TEST(GaussianDistributionTest,AlgorithmBounds)431 TEST(GaussianDistributionTest, AlgorithmBounds) {
432   absl::gaussian_distribution<double> dist;
433 
434   // In ~95% of cases, a single value is used to generate the output.
435   // for all inputs where |x| < 0.750461021389 this should be the case.
436   //
437   // The exact constraints are based on the ziggurat tables, and any
438   // changes to the ziggurat tables may require adjusting these bounds.
439   //
440   // for i in range(0, len(X)-1):
441   //   print i, X[i+1]/X[i], (X[i+1]/X[i] > 0.984375)
442   //
443   // 0.125 <= |values| <= 0.75
444   const uint64_t kValues[] = {
445       0x1000000000000100ull, 0x2000000000000100ull, 0x3000000000000100ull,
446       0x4000000000000100ull, 0x5000000000000100ull, 0x6000000000000100ull,
447       // negative values
448       0x9000000000000100ull, 0xa000000000000100ull, 0xb000000000000100ull,
449       0xc000000000000100ull, 0xd000000000000100ull, 0xe000000000000100ull};
450 
451   // 0.875 <= |values| <= 0.984375
452   const uint64_t kExtraValues[] = {
453       0x7000000000000100ull, 0x7800000000000100ull,  //
454       0x7c00000000000100ull, 0x7e00000000000100ull,  //
455       // negative values
456       0xf000000000000100ull, 0xf800000000000100ull,  //
457       0xfc00000000000100ull, 0xfe00000000000100ull};
458 
459   auto make_box = [](uint64_t v, uint64_t box) {
460     return (v & 0xffffffffffffff80ull) | box;
461   };
462 
463   // The box is the lower 7 bits of the value. When the box == 0, then
464   // the algorithm uses an escape hatch to select the result for large
465   // outputs.
466   for (uint64_t box = 0; box < 0x7f; box++) {
467     for (const uint64_t v : kValues) {
468       // Extra values are added to the sequence to attempt to avoid
469       // infinite loops from rejection sampling on bugs/errors.
470       absl::random_internal::sequence_urbg urbg(
471           {make_box(v, box), 0x0003eb76f6f7f755ull, 0x5FCEA50FDB2F953Bull});
472 
473       auto a = dist(urbg);
474       EXPECT_EQ(1, urbg.invocations()) << box << " " << std::hex << v;
475       if (v & 0x8000000000000000ull) {
476         EXPECT_LT(a, 0.0) << box << " " << std::hex << v;
477       } else {
478         EXPECT_GT(a, 0.0) << box << " " << std::hex << v;
479       }
480     }
481     if (box > 10 && box < 100) {
482       // The center boxes use the fast algorithm for more
483       // than 98.4375% of values.
484       for (const uint64_t v : kExtraValues) {
485         absl::random_internal::sequence_urbg urbg(
486             {make_box(v, box), 0x0003eb76f6f7f755ull, 0x5FCEA50FDB2F953Bull});
487 
488         auto a = dist(urbg);
489         EXPECT_EQ(1, urbg.invocations()) << box << " " << std::hex << v;
490         if (v & 0x8000000000000000ull) {
491           EXPECT_LT(a, 0.0) << box << " " << std::hex << v;
492         } else {
493           EXPECT_GT(a, 0.0) << box << " " << std::hex << v;
494         }
495       }
496     }
497   }
498 
499   // When the box == 0, the fallback algorithm uses a ratio of uniforms,
500   // which consumes 2 additional values from the urbg.
501   // Fallback also requires that the initial value be > 0.9271586026096681.
502   auto make_fallback = [](uint64_t v) { return (v & 0xffffffffffffff80ull); };
503 
504   double tail[2];
505   {
506     // 0.9375
507     absl::random_internal::sequence_urbg urbg(
508         {make_fallback(0x7800000000000000ull), 0x13CCA830EB61BD96ull,
509          0x00000076f6f7f755ull});
510     tail[0] = dist(urbg);
511     EXPECT_EQ(3, urbg.invocations());
512     EXPECT_GT(tail[0], 0);
513   }
514   {
515     // -0.9375
516     absl::random_internal::sequence_urbg urbg(
517         {make_fallback(0xf800000000000000ull), 0x13CCA830EB61BD96ull,
518          0x00000076f6f7f755ull});
519     tail[1] = dist(urbg);
520     EXPECT_EQ(3, urbg.invocations());
521     EXPECT_LT(tail[1], 0);
522   }
523   EXPECT_EQ(tail[0], -tail[1]);
524   EXPECT_EQ(418610, static_cast<int64_t>(tail[0] * 100000.0));
525 
526   // When the box != 0, the fallback algorithm computes a wedge function.
527   // Depending on the box, the threshold for varies as high as
528   // 0.991522480228.
529   {
530     // 0.9921875, 0.875
531     absl::random_internal::sequence_urbg urbg(
532         {make_box(0x7f00000000000000ull, 120), 0xe000000000000001ull,
533          0x13CCA830EB61BD96ull});
534     tail[0] = dist(urbg);
535     EXPECT_EQ(2, urbg.invocations());
536     EXPECT_GT(tail[0], 0);
537   }
538   {
539     // -0.9921875, 0.875
540     absl::random_internal::sequence_urbg urbg(
541         {make_box(0xff00000000000000ull, 120), 0xe000000000000001ull,
542          0x13CCA830EB61BD96ull});
543     tail[1] = dist(urbg);
544     EXPECT_EQ(2, urbg.invocations());
545     EXPECT_LT(tail[1], 0);
546   }
547   EXPECT_EQ(tail[0], -tail[1]);
548   EXPECT_EQ(61948, static_cast<int64_t>(tail[0] * 100000.0));
549 
550   // Fallback rejected, try again.
551   {
552     // -0.9921875, 0.0625
553     absl::random_internal::sequence_urbg urbg(
554         {make_box(0xff00000000000000ull, 120), 0x1000000000000001,
555          make_box(0x1000000000000100ull, 50), 0x13CCA830EB61BD96ull});
556     dist(urbg);
557     EXPECT_EQ(3, urbg.invocations());
558   }
559 }
560 
561 }  // namespace
562