absl/random/gaussian_distribution_test.cc - third_party/github/abseil/abseil-cpp - Git at Google

 // Copyright 2017 The Abseil Authors.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //      https://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include "absl/random/gaussian_distribution.h"

 #include <algorithm>
 #include <cmath>
 #include <cstddef>
 #include <ios>
 #include <iterator>
 #include <random>
 #include <string>
 #include <type_traits>
 #include <vector>

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include "absl/base/macros.h"
 #include "absl/log/log.h"
 #include "absl/numeric/internal/representation.h"
 #include "absl/random/internal/chi_square.h"
 #include "absl/random/internal/distribution_test_util.h"
 #include "absl/random/internal/sequence_urbg.h"
 #include "absl/random/random.h"
 #include "absl/strings/str_cat.h"
 #include "absl/strings/str_format.h"
 #include "absl/strings/str_replace.h"
 #include "absl/strings/strip.h"

 namespace {

 using absl::random_internal::kChiSquared;

 template <typename RealType>
 class GaussianDistributionInterfaceTest : public ::testing::Test {};

 // double-double arithmetic is not supported well by either GCC or Clang; see
 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048,
 // https://bugs.llvm.org/show_bug.cgi?id=49131, and
 // https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests
 // with double doubles until compiler support is better.
 using RealTypes =
     std::conditional<absl::numeric_internal::IsDoubleDouble(),
                      ::testing::Types<float, double>,
                      ::testing::Types<float, double, long double>>::type;
 TYPED_TEST_SUITE(GaussianDistributionInterfaceTest, RealTypes);

 TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) {
   using param_type =
       typename absl::gaussian_distribution<TypeParam>::param_type;

   const TypeParam kParams[] = {
       // Cases around 1.
       1,                                           //
       std::nextafter(TypeParam(1), TypeParam(0)),  // 1 - epsilon
       std::nextafter(TypeParam(1), TypeParam(2)),  // 1 + epsilon
       // Arbitrary values.
       TypeParam(1e-8), TypeParam(1e-4), TypeParam(2), TypeParam(1e4),
       TypeParam(1e8), TypeParam(1e20), TypeParam(2.5),
       // Boundary cases.
       std::numeric_limits<TypeParam>::infinity(),
       std::numeric_limits<TypeParam>::max(),
       std::numeric_limits<TypeParam>::epsilon(),
       std::nextafter(std::numeric_limits<TypeParam>::min(),
                      TypeParam(1)),           // min + epsilon
       std::numeric_limits<TypeParam>::min(),  // smallest normal
       // There are some errors dealing with denorms on apple platforms.
       std::numeric_limits<TypeParam>::denorm_min(),  // smallest denorm
       std::numeric_limits<TypeParam>::min() / 2,
       std::nextafter(std::numeric_limits<TypeParam>::min(),
                      TypeParam(0)),  // denorm_max
   };

   constexpr int kCount = 1000;
   absl::InsecureBitGen gen;

   // Use a loop to generate the combinations of {+/-x, +/-y}, and assign x, y to
   // all values in kParams,
   for (const auto mod : {0, 1, 2, 3}) {
     for (const auto x : kParams) {
       if (!std::isfinite(x)) continue;
       for (const auto y : kParams) {
         const TypeParam mean = (mod & 0x1) ? -x : x;
         const TypeParam stddev = (mod & 0x2) ? -y : y;
         const param_type param(mean, stddev);

         absl::gaussian_distribution<TypeParam> before(mean, stddev);
         EXPECT_EQ(before.mean(), param.mean());
         EXPECT_EQ(before.stddev(), param.stddev());

         {
           absl::gaussian_distribution<TypeParam> via_param(param);
           EXPECT_EQ(via_param, before);
           EXPECT_EQ(via_param.param(), before.param());
         }

         // Smoke test.
         auto sample_min = before.max();
         auto sample_max = before.min();
         for (int i = 0; i < kCount; i++) {
           auto sample = before(gen);
           if (sample > sample_max) sample_max = sample;
           if (sample < sample_min) sample_min = sample;
           EXPECT_GE(sample, before.min()) << before;
           EXPECT_LE(sample, before.max()) << before;
         }
         if (!std::is_same<TypeParam, long double>::value) {
           LOG(INFO) << "Range{" << mean << ", " << stddev << "}: " << sample_min
                     << ", " << sample_max;
         }

         std::stringstream ss;
         ss << before;

         if (!std::isfinite(mean) || !std::isfinite(stddev)) {
           // Streams do not parse inf/nan.
           continue;
         }

         // Validate stream serialization.
         absl::gaussian_distribution<TypeParam> after(-0.53f, 2.3456f);

         EXPECT_NE(before.mean(), after.mean());
         EXPECT_NE(before.stddev(), after.stddev());
         EXPECT_NE(before.param(), after.param());
         EXPECT_NE(before, after);

         ss >> after;

         EXPECT_EQ(before.mean(), after.mean());
         EXPECT_EQ(before.stddev(), after.stddev())  //
             << ss.str() << " "                      //
             << (ss.good() ? "good " : "")           //
             << (ss.bad() ? "bad " : "")             //
             << (ss.eof() ? "eof " : "")             //
             << (ss.fail() ? "fail " : "");
       }
     }
   }
 }

 // http://www.itl.nist.gov/div898/handbook/eda/section3/eda3661.htm

 class GaussianModel {
  public:
   GaussianModel(double mean, double stddev) : mean_(mean), stddev_(stddev) {}

   double mean() const { return mean_; }
   double variance() const { return stddev() * stddev(); }
   double stddev() const { return stddev_; }
   double skew() const { return 0; }
   double kurtosis() const { return 3.0; }

   // The inverse CDF, or PercentPoint function.
   double InverseCDF(double p) {
     ABSL_ASSERT(p >= 0.0);
     ABSL_ASSERT(p < 1.0);
     return mean() + stddev() * -absl::random_internal::InverseNormalSurvival(p);
   }

  private:
   const double mean_;
   const double stddev_;
 };

 struct Param {
   double mean;
   double stddev;
   double p_fail;  // Z-Test probability of failure.
   int trials;     // Z-Test trials.
 };

 // GaussianDistributionTests implements a z-test for the gaussian
 // distribution.
 class GaussianDistributionTests : public testing::TestWithParam<Param>,
                                   public GaussianModel {
  public:
   GaussianDistributionTests()
       : GaussianModel(GetParam().mean, GetParam().stddev) {}

   // SingleZTest provides a basic z-squared test of the mean vs. expected
   // mean for data generated by the poisson distribution.
   template <typename D>
   bool SingleZTest(const double p, const size_t samples);

   // SingleChiSquaredTest provides a basic chi-squared test of the normal
   // distribution.
   template <typename D>
   double SingleChiSquaredTest();

   // We use a fixed bit generator for distribution accuracy tests.  This allows
   // these tests to be deterministic, while still testing the qualify of the
   // implementation.
   absl::random_internal::pcg64_2018_engine rng_{0x2B7E151628AED2A6};
 };

 template <typename D>
 bool GaussianDistributionTests::SingleZTest(const double p,
                                             const size_t samples) {
   D dis(mean(), stddev());

   std::vector<double> data;
   data.reserve(samples);
   for (size_t i = 0; i < samples; i++) {
     const double x = dis(rng_);
     data.push_back(x);
   }

   const double max_err = absl::random_internal::MaxErrorTolerance(p);
   const auto m = absl::random_internal::ComputeDistributionMoments(data);
   const double z = absl::random_internal::ZScore(mean(), m);
   const bool pass = absl::random_internal::Near("z", z, 0.0, max_err);

   // NOTE: Informational statistical test:
   //
   // Compute the Jarque-Bera test statistic given the excess skewness
   // and kurtosis. The statistic is drawn from a chi-square(2) distribution.
   // https://en.wikipedia.org/wiki/Jarque%E2%80%93Bera_test
   //
   // The null-hypothesis (normal distribution) is rejected when
   // (p = 0.05 => jb > 5.99)
   // (p = 0.01 => jb > 9.21)
   // NOTE: JB has a large type-I error rate, so it will reject the
   // null-hypothesis even when it is true more often than the z-test.
   //
   const double jb =
       static_cast<double>(m.n) / 6.0 *
       (std::pow(m.skewness, 2.0) + std::pow(m.kurtosis - 3.0, 2.0) / 4.0);

   if (!pass || jb > 9.21) {
     // clang-format off
     LOG(INFO)
         << "p=" << p << " max_err=" << max_err << "\n"
            " mean=" << m.mean << " vs. " << mean() << "\n"
            " stddev=" << std::sqrt(m.variance) << " vs. " << stddev() << "\n"
            " skewness=" << m.skewness << " vs. " << skew() << "\n"
            " kurtosis=" << m.kurtosis << " vs. " << kurtosis() << "\n"
            " z=" << z << " vs. 0\n"
            " jb=" << jb << " vs. 9.21";
     // clang-format on
   }
   return pass;
 }

 template <typename D>
 double GaussianDistributionTests::SingleChiSquaredTest() {
   const size_t kSamples = 10000;
   const int kBuckets = 50;

   // The InverseCDF is the percent point function of the
   // distribution, and can be used to assign buckets
   // roughly uniformly.
   std::vector<double> cutoffs;
   const double kInc = 1.0 / static_cast<double>(kBuckets);
   for (double p = kInc; p < 1.0; p += kInc) {
     cutoffs.push_back(InverseCDF(p));
   }
   if (cutoffs.back() != std::numeric_limits<double>::infinity()) {
     cutoffs.push_back(std::numeric_limits<double>::infinity());
   }

   D dis(mean(), stddev());

   std::vector<int32_t> counts(cutoffs.size(), 0);
   for (int j = 0; j < kSamples; j++) {
     const double x = dis(rng_);
     auto it = std::upper_bound(cutoffs.begin(), cutoffs.end(), x);
     counts[std::distance(cutoffs.begin(), it)]++;
   }

   // Null-hypothesis is that the distribution is a gaussian distribution
   // with the provided mean and stddev (not estimated from the data).
   const int dof = static_cast<int>(counts.size()) - 1;

   // Our threshold for logging is 1-in-50.
   const double threshold = absl::random_internal::ChiSquareValue(dof, 0.98);

   const double expected =
       static_cast<double>(kSamples) / static_cast<double>(counts.size());

   double chi_square = absl::random_internal::ChiSquareWithExpected(
       std::begin(counts), std::end(counts), expected);
   double p = absl::random_internal::ChiSquarePValue(chi_square, dof);

   // Log if the chi_square value is above the threshold.
   if (chi_square > threshold) {
     for (size_t i = 0; i < cutoffs.size(); i++) {
       LOG(INFO) << i << " : (" << cutoffs[i] << ") = " << counts[i];
     }

     // clang-format off
     LOG(INFO) << "mean=" << mean() << " stddev=" << stddev() << "\n"
                  " expected " << expected << "\n"
               << kChiSquared << " " << chi_square << " (" << p << ")\n"
               << kChiSquared << " @ 0.98 = " << threshold;
     // clang-format on
   }
   return p;
 }

 TEST_P(GaussianDistributionTests, ZTest) {
   // TODO(absl-team): Run these tests against std::normal_distribution<double>
   // to validate outcomes are similar.
   const size_t kSamples = 10000;
   const auto& param = GetParam();
   const int expected_failures =
       std::max(1, static_cast<int>(std::ceil(param.trials * param.p_fail)));
   const double p = absl::random_internal::RequiredSuccessProbability(
       param.p_fail, param.trials);

   int failures = 0;
   for (int i = 0; i < param.trials; i++) {
     failures +=
         SingleZTest<absl::gaussian_distribution<double>>(p, kSamples) ? 0 : 1;
   }
   EXPECT_LE(failures, expected_failures);
 }

 TEST_P(GaussianDistributionTests, ChiSquaredTest) {
   const int kTrials = 20;
   int failures = 0;

   for (int i = 0; i < kTrials; i++) {
     double p_value =
         SingleChiSquaredTest<absl::gaussian_distribution<double>>();
     if (p_value < 0.0025) {  // 1/400
       failures++;
     }
   }
   // There is a 0.05% chance of producing at least one failure, so raise the
   // failure threshold high enough to allow for a flake rate of less than one in
   // 10,000.
   EXPECT_LE(failures, 4);
 }

 std::vector<Param> GenParams() {
   return {
       // Mean around 0.
       Param{0.0, 1.0, 0.01, 100},
       Param{0.0, 1e2, 0.01, 100},
       Param{0.0, 1e4, 0.01, 100},
       Param{0.0, 1e8, 0.01, 100},
       Param{0.0, 1e16, 0.01, 100},
       Param{0.0, 1e-3, 0.01, 100},
       Param{0.0, 1e-5, 0.01, 100},
       Param{0.0, 1e-9, 0.01, 100},
       Param{0.0, 1e-17, 0.01, 100},

       // Mean around 1.
       Param{1.0, 1.0, 0.01, 100},
       Param{1.0, 1e2, 0.01, 100},
       Param{1.0, 1e-2, 0.01, 100},

       // Mean around 100 / -100
       Param{1e2, 1.0, 0.01, 100},
       Param{-1e2, 1.0, 0.01, 100},
       Param{1e2, 1e6, 0.01, 100},
       Param{-1e2, 1e6, 0.01, 100},

       // More extreme
       Param{1e4, 1e4, 0.01, 100},
       Param{1e8, 1e4, 0.01, 100},
       Param{1e12, 1e4, 0.01, 100},
   };
 }

 std::string ParamName(const ::testing::TestParamInfo<Param>& info) {
   const auto& p = info.param;
   std::string name = absl::StrCat("mean_", absl::SixDigits(p.mean), "__stddev_",
                                   absl::SixDigits(p.stddev));
   return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}});
 }

 INSTANTIATE_TEST_SUITE_P(All, GaussianDistributionTests,
                          ::testing::ValuesIn(GenParams()), ParamName);

 // NOTE: absl::gaussian_distribution is not guaranteed to be stable.
 TEST(GaussianDistributionTest, StabilityTest) {
   // absl::gaussian_distribution stability relies on the underlying zignor
   // data, absl::random_interna::RandU64ToDouble, std::exp, std::log, and
   // std::abs.
   absl::random_internal::sequence_urbg urbg(
       {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull,
        0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull,
        0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull,
        0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull});

   std::vector<int> output(11);

   {
     absl::gaussian_distribution<double> dist;
     std::generate(std::begin(output), std::end(output),
                   [&] { return static_cast<int>(10000000.0 * dist(urbg)); });

     EXPECT_EQ(13, urbg.invocations());
     EXPECT_THAT(output,  //
                 testing::ElementsAre(1494, 25518841, 9991550, 1351856,
                                      -20373238, 3456682, 333530, -6804981,
                                      -15279580, -16459654, 1494));
   }

   urbg.reset();
   {
     absl::gaussian_distribution<float> dist;
     std::generate(std::begin(output), std::end(output),
                   [&] { return static_cast<int>(1000000.0f * dist(urbg)); });

     EXPECT_EQ(13, urbg.invocations());
     EXPECT_THAT(
         output,  //
         testing::ElementsAre(149, 2551884, 999155, 135185, -2037323, 345668,
                              33353, -680498, -1527958, -1645965, 149));
   }
 }

 // This is an implementation-specific test. If any part of the implementation
 // changes, then it is likely that this test will change as well.
 // Also, if dependencies of the distribution change, such as RandU64ToDouble,
 // then this is also likely to change.
 TEST(GaussianDistributionTest, AlgorithmBounds) {
   absl::gaussian_distribution<double> dist;

   // In ~95% of cases, a single value is used to generate the output.
   // for all inputs where |x| < 0.750461021389 this should be the case.
   //
   // The exact constraints are based on the ziggurat tables, and any
   // changes to the ziggurat tables may require adjusting these bounds.
   //
   // for i in range(0, len(X)-1):
   //   print i, X[i+1]/X[i], (X[i+1]/X[i] > 0.984375)
   //
   // 0.125 <= |values| <= 0.75
   const uint64_t kValues[] = {
       0x1000000000000100ull, 0x2000000000000100ull, 0x3000000000000100ull,
       0x4000000000000100ull, 0x5000000000000100ull, 0x6000000000000100ull,
       // negative values
       0x9000000000000100ull, 0xa000000000000100ull, 0xb000000000000100ull,
       0xc000000000000100ull, 0xd000000000000100ull, 0xe000000000000100ull};

   // 0.875 <= |values| <= 0.984375
   const uint64_t kExtraValues[] = {
       0x7000000000000100ull, 0x7800000000000100ull,  //
       0x7c00000000000100ull, 0x7e00000000000100ull,  //
       // negative values
       0xf000000000000100ull, 0xf800000000000100ull,  //
       0xfc00000000000100ull, 0xfe00000000000100ull};

   auto make_box = [](uint64_t v, uint64_t box) {
     return (v & 0xffffffffffffff80ull) | box;
   };

   // The box is the lower 7 bits of the value. When the box == 0, then
   // the algorithm uses an escape hatch to select the result for large
   // outputs.
   for (uint64_t box = 0; box < 0x7f; box++) {
     for (const uint64_t v : kValues) {
       // Extra values are added to the sequence to attempt to avoid
       // infinite loops from rejection sampling on bugs/errors.
       absl::random_internal::sequence_urbg urbg(
           {make_box(v, box), 0x0003eb76f6f7f755ull, 0x5FCEA50FDB2F953Bull});

       auto a = dist(urbg);
       EXPECT_EQ(1, urbg.invocations()) << box << " " << std::hex << v;
       if (v & 0x8000000000000000ull) {
         EXPECT_LT(a, 0.0) << box << " " << std::hex << v;
       } else {
         EXPECT_GT(a, 0.0) << box << " " << std::hex << v;
       }
     }
     if (box > 10 && box < 100) {
       // The center boxes use the fast algorithm for more
       // than 98.4375% of values.
       for (const uint64_t v : kExtraValues) {
         absl::random_internal::sequence_urbg urbg(
             {make_box(v, box), 0x0003eb76f6f7f755ull, 0x5FCEA50FDB2F953Bull});

         auto a = dist(urbg);
         EXPECT_EQ(1, urbg.invocations()) << box << " " << std::hex << v;
         if (v & 0x8000000000000000ull) {
           EXPECT_LT(a, 0.0) << box << " " << std::hex << v;
         } else {
           EXPECT_GT(a, 0.0) << box << " " << std::hex << v;
         }
       }
     }
   }

   // When the box == 0, the fallback algorithm uses a ratio of uniforms,
   // which consumes 2 additional values from the urbg.
   // Fallback also requires that the initial value be > 0.9271586026096681.
   auto make_fallback = [](uint64_t v) { return (v & 0xffffffffffffff80ull); };

   double tail[2];
   {
     // 0.9375
     absl::random_internal::sequence_urbg urbg(
         {make_fallback(0x7800000000000000ull), 0x13CCA830EB61BD96ull,
          0x00000076f6f7f755ull});
     tail[0] = dist(urbg);
     EXPECT_EQ(3, urbg.invocations());
     EXPECT_GT(tail[0], 0);
   }
   {
     // -0.9375
     absl::random_internal::sequence_urbg urbg(
         {make_fallback(0xf800000000000000ull), 0x13CCA830EB61BD96ull,
          0x00000076f6f7f755ull});
     tail[1] = dist(urbg);
     EXPECT_EQ(3, urbg.invocations());
     EXPECT_LT(tail[1], 0);
   }
   EXPECT_EQ(tail[0], -tail[1]);
   EXPECT_EQ(418610, static_cast<int64_t>(tail[0] * 100000.0));

   // When the box != 0, the fallback algorithm computes a wedge function.
   // Depending on the box, the threshold for varies as high as
   // 0.991522480228.
   {
     // 0.9921875, 0.875
     absl::random_internal::sequence_urbg urbg(
         {make_box(0x7f00000000000000ull, 120), 0xe000000000000001ull,
          0x13CCA830EB61BD96ull});
     tail[0] = dist(urbg);
     EXPECT_EQ(2, urbg.invocations());
     EXPECT_GT(tail[0], 0);
   }
   {
     // -0.9921875, 0.875
     absl::random_internal::sequence_urbg urbg(
         {make_box(0xff00000000000000ull, 120), 0xe000000000000001ull,
          0x13CCA830EB61BD96ull});
     tail[1] = dist(urbg);
     EXPECT_EQ(2, urbg.invocations());
     EXPECT_LT(tail[1], 0);
   }
   EXPECT_EQ(tail[0], -tail[1]);
   EXPECT_EQ(61948, static_cast<int64_t>(tail[0] * 100000.0));

   // Fallback rejected, try again.
   {
     // -0.9921875, 0.0625
     absl::random_internal::sequence_urbg urbg(
         {make_box(0xff00000000000000ull, 120), 0x1000000000000001,
          make_box(0x1000000000000100ull, 50), 0x13CCA830EB61BD96ull});
     dist(urbg);
     EXPECT_EQ(3, urbg.invocations());
   }
 }

 }  // namespace
	// Copyright 2017 The Abseil Authors.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// https://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include "absl/random/gaussian_distribution.h"

	#include <algorithm>
	#include <cmath>
	#include <cstddef>
	#include <ios>
	#include <iterator>
	#include <random>
	#include <string>
	#include <type_traits>
	#include <vector>

	#include "gmock/gmock.h"
	#include "gtest/gtest.h"
	#include "absl/base/macros.h"
	#include "absl/log/log.h"
	#include "absl/numeric/internal/representation.h"
	#include "absl/random/internal/chi_square.h"
	#include "absl/random/internal/distribution_test_util.h"
	#include "absl/random/internal/sequence_urbg.h"
	#include "absl/random/random.h"
	#include "absl/strings/str_cat.h"
	#include "absl/strings/str_format.h"
	#include "absl/strings/str_replace.h"
	#include "absl/strings/strip.h"

	namespace {

	using absl::random_internal::kChiSquared;

	template <typename RealType>
	class GaussianDistributionInterfaceTest : public ::testing::Test {};

	// double-double arithmetic is not supported well by either GCC or Clang; see
	// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048,
	// https://bugs.llvm.org/show_bug.cgi?id=49131, and
	// https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests
	// with double doubles until compiler support is better.
	using RealTypes =
	std::conditional<absl::numeric_internal::IsDoubleDouble(),
	::testing::Types<float, double>,
	::testing::Types<float, double, long double>>::type;
	TYPED_TEST_SUITE(GaussianDistributionInterfaceTest, RealTypes);

	TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) {
	using param_type =
	typename absl::gaussian_distribution<TypeParam>::param_type;

	const TypeParam kParams[] = {
	// Cases around 1.
	1, //
	std::nextafter(TypeParam(1), TypeParam(0)), // 1 - epsilon
	std::nextafter(TypeParam(1), TypeParam(2)), // 1 + epsilon
	// Arbitrary values.
	TypeParam(1e-8), TypeParam(1e-4), TypeParam(2), TypeParam(1e4),
	TypeParam(1e8), TypeParam(1e20), TypeParam(2.5),
	// Boundary cases.
	std::numeric_limits<TypeParam>::infinity(),
	std::numeric_limits<TypeParam>::max(),
	std::numeric_limits<TypeParam>::epsilon(),
	std::nextafter(std::numeric_limits<TypeParam>::min(),
	TypeParam(1)), // min + epsilon
	std::numeric_limits<TypeParam>::min(), // smallest normal
	// There are some errors dealing with denorms on apple platforms.
	std::numeric_limits<TypeParam>::denorm_min(), // smallest denorm
	std::numeric_limits<TypeParam>::min() / 2,
	std::nextafter(std::numeric_limits<TypeParam>::min(),
	TypeParam(0)), // denorm_max
	};

	constexpr int kCount = 1000;
	absl::InsecureBitGen gen;

	// Use a loop to generate the combinations of {+/-x, +/-y}, and assign x, y to
	// all values in kParams,
	for (const auto mod : {0, 1, 2, 3}) {
	for (const auto x : kParams) {
	if (!std::isfinite(x)) continue;
	for (const auto y : kParams) {
	const TypeParam mean = (mod & 0x1) ? -x : x;
	const TypeParam stddev = (mod & 0x2) ? -y : y;
	const param_type param(mean, stddev);

	absl::gaussian_distribution<TypeParam> before(mean, stddev);
	EXPECT_EQ(before.mean(), param.mean());
	EXPECT_EQ(before.stddev(), param.stddev());

	{
	absl::gaussian_distribution<TypeParam> via_param(param);
	EXPECT_EQ(via_param, before);
	EXPECT_EQ(via_param.param(), before.param());
	}

	// Smoke test.
	auto sample_min = before.max();
	auto sample_max = before.min();
	for (int i = 0; i < kCount; i++) {
	auto sample = before(gen);
	if (sample > sample_max) sample_max = sample;
	if (sample < sample_min) sample_min = sample;
	EXPECT_GE(sample, before.min()) << before;
	EXPECT_LE(sample, before.max()) << before;
	}
	if (!std::is_same<TypeParam, long double>::value) {
	LOG(INFO) << "Range{" << mean << ", " << stddev << "}: " << sample_min
	<< ", " << sample_max;
	}

	std::stringstream ss;
	ss << before;

	if (!std::isfinite(mean) \|\| !std::isfinite(stddev)) {
	// Streams do not parse inf/nan.
	continue;
	}

	// Validate stream serialization.
	absl::gaussian_distribution<TypeParam> after(-0.53f, 2.3456f);

	EXPECT_NE(before.mean(), after.mean());
	EXPECT_NE(before.stddev(), after.stddev());
	EXPECT_NE(before.param(), after.param());
	EXPECT_NE(before, after);

	ss >> after;

	EXPECT_EQ(before.mean(), after.mean());
	EXPECT_EQ(before.stddev(), after.stddev()) //
	<< ss.str() << " " //
	<< (ss.good() ? "good " : "") //
	<< (ss.bad() ? "bad " : "") //
	<< (ss.eof() ? "eof " : "") //
	<< (ss.fail() ? "fail " : "");
	}
	}
	}
	}

	// http://www.itl.nist.gov/div898/handbook/eda/section3/eda3661.htm

	class GaussianModel {
	public:
	GaussianModel(double mean, double stddev) : mean_(mean), stddev_(stddev) {}

	double mean() const { return mean_; }
	double variance() const { return stddev() * stddev(); }
	double stddev() const { return stddev_; }
	double skew() const { return 0; }
	double kurtosis() const { return 3.0; }

	// The inverse CDF, or PercentPoint function.
	double InverseCDF(double p) {
	ABSL_ASSERT(p >= 0.0);
	ABSL_ASSERT(p < 1.0);
	return mean() + stddev() * -absl::random_internal::InverseNormalSurvival(p);
	}

	private:
	const double mean_;
	const double stddev_;
	};

	struct Param {
	double mean;
	double stddev;
	double p_fail; // Z-Test probability of failure.
	int trials; // Z-Test trials.
	};

	// GaussianDistributionTests implements a z-test for the gaussian
	// distribution.
	class GaussianDistributionTests : public testing::TestWithParam<Param>,
	public GaussianModel {
	public:
	GaussianDistributionTests()
	: GaussianModel(GetParam().mean, GetParam().stddev) {}

	// SingleZTest provides a basic z-squared test of the mean vs. expected
	// mean for data generated by the poisson distribution.
	template <typename D>
	bool SingleZTest(const double p, const size_t samples);

	// SingleChiSquaredTest provides a basic chi-squared test of the normal
	// distribution.
	template <typename D>
	double SingleChiSquaredTest();

	// We use a fixed bit generator for distribution accuracy tests. This allows
	// these tests to be deterministic, while still testing the qualify of the
	// implementation.
	absl::random_internal::pcg64_2018_engine rng_{0x2B7E151628AED2A6};
	};

	template <typename D>
	bool GaussianDistributionTests::SingleZTest(const double p,
	const size_t samples) {
	D dis(mean(), stddev());

	std::vector<double> data;
	data.reserve(samples);
	for (size_t i = 0; i < samples; i++) {
	const double x = dis(rng_);
	data.push_back(x);
	}

	const double max_err = absl::random_internal::MaxErrorTolerance(p);
	const auto m = absl::random_internal::ComputeDistributionMoments(data);
	const double z = absl::random_internal::ZScore(mean(), m);
	const bool pass = absl::random_internal::Near("z", z, 0.0, max_err);

	// NOTE: Informational statistical test:
	//
	// Compute the Jarque-Bera test statistic given the excess skewness
	// and kurtosis. The statistic is drawn from a chi-square(2) distribution.
	// https://en.wikipedia.org/wiki/Jarque%E2%80%93Bera_test
	//
	// The null-hypothesis (normal distribution) is rejected when
	// (p = 0.05 => jb > 5.99)
	// (p = 0.01 => jb > 9.21)
	// NOTE: JB has a large type-I error rate, so it will reject the
	// null-hypothesis even when it is true more often than the z-test.
	//
	const double jb =
	static_cast<double>(m.n) / 6.0 *
	(std::pow(m.skewness, 2.0) + std::pow(m.kurtosis - 3.0, 2.0) / 4.0);

	if (!pass \|\| jb > 9.21) {
	// clang-format off
	LOG(INFO)
	<< "p=" << p << " max_err=" << max_err << "\n"
	" mean=" << m.mean << " vs. " << mean() << "\n"
	" stddev=" << std::sqrt(m.variance) << " vs. " << stddev() << "\n"
	" skewness=" << m.skewness << " vs. " << skew() << "\n"
	" kurtosis=" << m.kurtosis << " vs. " << kurtosis() << "\n"
	" z=" << z << " vs. 0\n"
	" jb=" << jb << " vs. 9.21";
	// clang-format on
	}
	return pass;
	}

	template <typename D>
	double GaussianDistributionTests::SingleChiSquaredTest() {
	const size_t kSamples = 10000;
	const int kBuckets = 50;

	// The InverseCDF is the percent point function of the
	// distribution, and can be used to assign buckets
	// roughly uniformly.
	std::vector<double> cutoffs;
	const double kInc = 1.0 / static_cast<double>(kBuckets);
	for (double p = kInc; p < 1.0; p += kInc) {
	cutoffs.push_back(InverseCDF(p));
	}
	if (cutoffs.back() != std::numeric_limits<double>::infinity()) {
	cutoffs.push_back(std::numeric_limits<double>::infinity());
	}

	D dis(mean(), stddev());

	std::vector<int32_t> counts(cutoffs.size(), 0);
	for (int j = 0; j < kSamples; j++) {
	const double x = dis(rng_);
	auto it = std::upper_bound(cutoffs.begin(), cutoffs.end(), x);
	counts[std::distance(cutoffs.begin(), it)]++;
	}

	// Null-hypothesis is that the distribution is a gaussian distribution
	// with the provided mean and stddev (not estimated from the data).
	const int dof = static_cast<int>(counts.size()) - 1;

	// Our threshold for logging is 1-in-50.
	const double threshold = absl::random_internal::ChiSquareValue(dof, 0.98);

	const double expected =
	static_cast<double>(kSamples) / static_cast<double>(counts.size());

	double chi_square = absl::random_internal::ChiSquareWithExpected(
	std::begin(counts), std::end(counts), expected);
	double p = absl::random_internal::ChiSquarePValue(chi_square, dof);

	// Log if the chi_square value is above the threshold.
	if (chi_square > threshold) {
	for (size_t i = 0; i < cutoffs.size(); i++) {
	LOG(INFO) << i << " : (" << cutoffs[i] << ") = " << counts[i];
	}

	// clang-format off
	LOG(INFO) << "mean=" << mean() << " stddev=" << stddev() << "\n"
	" expected " << expected << "\n"
	<< kChiSquared << " " << chi_square << " (" << p << ")\n"
	<< kChiSquared << " @ 0.98 = " << threshold;
	// clang-format on
	}
	return p;
	}

	TEST_P(GaussianDistributionTests, ZTest) {
	// TODO(absl-team): Run these tests against std::normal_distribution<double>
	// to validate outcomes are similar.
	const size_t kSamples = 10000;
	const auto& param = GetParam();
	const int expected_failures =
	std::max(1, static_cast<int>(std::ceil(param.trials * param.p_fail)));
	const double p = absl::random_internal::RequiredSuccessProbability(
	param.p_fail, param.trials);

	int failures = 0;
	for (int i = 0; i < param.trials; i++) {
	failures +=
	SingleZTest<absl::gaussian_distribution<double>>(p, kSamples) ? 0 : 1;
	}
	EXPECT_LE(failures, expected_failures);
	}

	TEST_P(GaussianDistributionTests, ChiSquaredTest) {
	const int kTrials = 20;
	int failures = 0;

	for (int i = 0; i < kTrials; i++) {
	double p_value =
	SingleChiSquaredTest<absl::gaussian_distribution<double>>();
	if (p_value < 0.0025) { // 1/400
	failures++;
	}
	}
	// There is a 0.05% chance of producing at least one failure, so raise the
	// failure threshold high enough to allow for a flake rate of less than one in
	// 10,000.
	EXPECT_LE(failures, 4);
	}

	std::vector<Param> GenParams() {
	return {
	// Mean around 0.
	Param{0.0, 1.0, 0.01, 100},
	Param{0.0, 1e2, 0.01, 100},
	Param{0.0, 1e4, 0.01, 100},
	Param{0.0, 1e8, 0.01, 100},
	Param{0.0, 1e16, 0.01, 100},
	Param{0.0, 1e-3, 0.01, 100},
	Param{0.0, 1e-5, 0.01, 100},
	Param{0.0, 1e-9, 0.01, 100},
	Param{0.0, 1e-17, 0.01, 100},

	// Mean around 1.
	Param{1.0, 1.0, 0.01, 100},
	Param{1.0, 1e2, 0.01, 100},
	Param{1.0, 1e-2, 0.01, 100},

	// Mean around 100 / -100
	Param{1e2, 1.0, 0.01, 100},
	Param{-1e2, 1.0, 0.01, 100},
	Param{1e2, 1e6, 0.01, 100},
	Param{-1e2, 1e6, 0.01, 100},

	// More extreme
	Param{1e4, 1e4, 0.01, 100},
	Param{1e8, 1e4, 0.01, 100},
	Param{1e12, 1e4, 0.01, 100},
	};
	}

	std::string ParamName(const ::testing::TestParamInfo<Param>& info) {
	const auto& p = info.param;
	std::string name = absl::StrCat("mean_", absl::SixDigits(p.mean), "__stddev_",
	absl::SixDigits(p.stddev));
	return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}});
	}

	INSTANTIATE_TEST_SUITE_P(All, GaussianDistributionTests,
	::testing::ValuesIn(GenParams()), ParamName);

	// NOTE: absl::gaussian_distribution is not guaranteed to be stable.
	TEST(GaussianDistributionTest, StabilityTest) {
	// absl::gaussian_distribution stability relies on the underlying zignor
	// data, absl::random_interna::RandU64ToDouble, std::exp, std::log, and
	// std::abs.
	absl::random_internal::sequence_urbg urbg(
	{0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull,
	0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull,
	0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull,
	0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull});

	std::vector<int> output(11);

	{
	absl::gaussian_distribution<double> dist;
	std::generate(std::begin(output), std::end(output),
	[&] { return static_cast<int>(10000000.0 * dist(urbg)); });

	EXPECT_EQ(13, urbg.invocations());
	EXPECT_THAT(output, //
	testing::ElementsAre(1494, 25518841, 9991550, 1351856,
	-20373238, 3456682, 333530, -6804981,
	-15279580, -16459654, 1494));
	}

	urbg.reset();
	{
	absl::gaussian_distribution<float> dist;
	std::generate(std::begin(output), std::end(output),
	[&] { return static_cast<int>(1000000.0f * dist(urbg)); });

	EXPECT_EQ(13, urbg.invocations());
	EXPECT_THAT(
	output, //
	testing::ElementsAre(149, 2551884, 999155, 135185, -2037323, 345668,
	33353, -680498, -1527958, -1645965, 149));
	}
	}

	// This is an implementation-specific test. If any part of the implementation
	// changes, then it is likely that this test will change as well.
	// Also, if dependencies of the distribution change, such as RandU64ToDouble,
	// then this is also likely to change.
	TEST(GaussianDistributionTest, AlgorithmBounds) {
	absl::gaussian_distribution<double> dist;

	// In ~95% of cases, a single value is used to generate the output.
	// for all inputs where \|x\| < 0.750461021389 this should be the case.
	//
	// The exact constraints are based on the ziggurat tables, and any
	// changes to the ziggurat tables may require adjusting these bounds.
	//
	// for i in range(0, len(X)-1):
	// print i, X[i+1]/X[i], (X[i+1]/X[i] > 0.984375)
	//
	// 0.125 <= \|values\| <= 0.75
	const uint64_t kValues[] = {
	0x1000000000000100ull, 0x2000000000000100ull, 0x3000000000000100ull,
	0x4000000000000100ull, 0x5000000000000100ull, 0x6000000000000100ull,
	// negative values
	0x9000000000000100ull, 0xa000000000000100ull, 0xb000000000000100ull,
	0xc000000000000100ull, 0xd000000000000100ull, 0xe000000000000100ull};

	// 0.875 <= \|values\| <= 0.984375
	const uint64_t kExtraValues[] = {
	0x7000000000000100ull, 0x7800000000000100ull, //
	0x7c00000000000100ull, 0x7e00000000000100ull, //
	// negative values
	0xf000000000000100ull, 0xf800000000000100ull, //
	0xfc00000000000100ull, 0xfe00000000000100ull};

	auto make_box = [](uint64_t v, uint64_t box) {
	return (v & 0xffffffffffffff80ull) \| box;
	};

	// The box is the lower 7 bits of the value. When the box == 0, then
	// the algorithm uses an escape hatch to select the result for large
	// outputs.
	for (uint64_t box = 0; box < 0x7f; box++) {
	for (const uint64_t v : kValues) {
	// Extra values are added to the sequence to attempt to avoid
	// infinite loops from rejection sampling on bugs/errors.
	absl::random_internal::sequence_urbg urbg(
	{make_box(v, box), 0x0003eb76f6f7f755ull, 0x5FCEA50FDB2F953Bull});

	auto a = dist(urbg);
	EXPECT_EQ(1, urbg.invocations()) << box << " " << std::hex << v;
	if (v & 0x8000000000000000ull) {
	EXPECT_LT(a, 0.0) << box << " " << std::hex << v;
	} else {
	EXPECT_GT(a, 0.0) << box << " " << std::hex << v;
	}
	}
	if (box > 10 && box < 100) {
	// The center boxes use the fast algorithm for more
	// than 98.4375% of values.
	for (const uint64_t v : kExtraValues) {
	absl::random_internal::sequence_urbg urbg(
	{make_box(v, box), 0x0003eb76f6f7f755ull, 0x5FCEA50FDB2F953Bull});

	auto a = dist(urbg);
	EXPECT_EQ(1, urbg.invocations()) << box << " " << std::hex << v;
	if (v & 0x8000000000000000ull) {
	EXPECT_LT(a, 0.0) << box << " " << std::hex << v;
	} else {
	EXPECT_GT(a, 0.0) << box << " " << std::hex << v;
	}
	}
	}
	}

	// When the box == 0, the fallback algorithm uses a ratio of uniforms,
	// which consumes 2 additional values from the urbg.
	// Fallback also requires that the initial value be > 0.9271586026096681.
	auto make_fallback = [](uint64_t v) { return (v & 0xffffffffffffff80ull); };

	double tail[2];
	{
	// 0.9375
	absl::random_internal::sequence_urbg urbg(
	{make_fallback(0x7800000000000000ull), 0x13CCA830EB61BD96ull,
	0x00000076f6f7f755ull});
	tail[0] = dist(urbg);
	EXPECT_EQ(3, urbg.invocations());
	EXPECT_GT(tail[0], 0);
	}
	{
	// -0.9375
	absl::random_internal::sequence_urbg urbg(
	{make_fallback(0xf800000000000000ull), 0x13CCA830EB61BD96ull,
	0x00000076f6f7f755ull});
	tail[1] = dist(urbg);
	EXPECT_EQ(3, urbg.invocations());
	EXPECT_LT(tail[1], 0);
	}
	EXPECT_EQ(tail[0], -tail[1]);
	EXPECT_EQ(418610, static_cast<int64_t>(tail[0] * 100000.0));

	// When the box != 0, the fallback algorithm computes a wedge function.
	// Depending on the box, the threshold for varies as high as
	// 0.991522480228.
	{
	// 0.9921875, 0.875
	absl::random_internal::sequence_urbg urbg(
	{make_box(0x7f00000000000000ull, 120), 0xe000000000000001ull,
	0x13CCA830EB61BD96ull});
	tail[0] = dist(urbg);
	EXPECT_EQ(2, urbg.invocations());
	EXPECT_GT(tail[0], 0);
	}
	{
	// -0.9921875, 0.875
	absl::random_internal::sequence_urbg urbg(
	{make_box(0xff00000000000000ull, 120), 0xe000000000000001ull,
	0x13CCA830EB61BD96ull});
	tail[1] = dist(urbg);
	EXPECT_EQ(2, urbg.invocations());
	EXPECT_LT(tail[1], 0);
	}
	EXPECT_EQ(tail[0], -tail[1]);
	EXPECT_EQ(61948, static_cast<int64_t>(tail[0] * 100000.0));

	// Fallback rejected, try again.
	{
	// -0.9921875, 0.0625
	absl::random_internal::sequence_urbg urbg(
	{make_box(0xff00000000000000ull, 120), 0x1000000000000001,
	make_box(0x1000000000000100ull, 50), 0x13CCA830EB61BD96ull});
	dist(urbg);
	EXPECT_EQ(3, urbg.invocations());
	}
	}

	} // namespace