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