From e9324d926a9189e222741fce6e676f0944661a72 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 21 Jun 2019 13:11:42 -0700 Subject: Export of internal Abseil changes. -- 7a6ff16a85beb730c172d5d25cf1b5e1be885c56 by Laramie Leavitt : Internal change. PiperOrigin-RevId: 254454546 -- ff8f9bafaefc26d451f576ea4a06d150aed63f6f by Andy Soffer : Internal changes PiperOrigin-RevId: 254451562 -- deefc5b651b479ce36f0b4ef203e119c0c8936f2 by CJ Johnson : Account for subtracting unsigned values from the size of InlinedVector PiperOrigin-RevId: 254450625 -- 3c677316a27bcadc17e41957c809ca472d5fef14 by Andy Soffer : Add C++17's std::make_from_tuple to absl/utility/utility.h PiperOrigin-RevId: 254411573 -- 4ee3536a918830eeec402a28fc31a62c7c90b940 by CJ Johnson : Adds benchmark for the rest of the InlinedVector public API PiperOrigin-RevId: 254408378 -- e5a21a00700ee83498ff1efbf649169756463ee4 by CJ Johnson : Updates the definition of InlinedVector::shrink_to_fit() to be exception safe and adds exception safety tests for it. PiperOrigin-RevId: 254401387 -- 2ea82e72b86d82d78b4e4712a63a55981b53c64b by Laramie Leavitt : Use absl::InsecureBitGen in place of std::mt19937 in tests absl/random/...distribution_test.cc PiperOrigin-RevId: 254289444 -- fa099e02c413a7ffda732415e8105cad26a90337 by Andy Soffer : Internal changes PiperOrigin-RevId: 254286334 -- ce34b7f36933b30cfa35b9c9a5697a792b5666e4 by Andy Soffer : Internal changes PiperOrigin-RevId: 254273059 -- 6f9c473da7c2090c2e85a37c5f00622e8a912a89 by Jorg Brown : Change absl::container_internal::CompressedTuple to instantiate its internal Storage class with the name of the type it's holding, rather than the name of the Tuple. This is not an externally-visible change, other than less compiler memory is used and less debug information is generated. PiperOrigin-RevId: 254269285 -- 8bd3c186bf2fc0c55d8a2dd6f28a5327502c9fba by Andy Soffer : Adding short-hand IntervalClosed for IntervalClosedClosed and IntervalOpen for IntervalOpenOpen. PiperOrigin-RevId: 254252419 -- ea957f99b6a04fccd42aa05605605f3b44b1ecfd by Abseil Team : Do not directly use __SIZEOF_INT128__. In order to avoid linker errors when building with clang-cl (__fixunsdfti, __udivti3 and __fixunssfti are undefined), this CL uses ABSL_HAVE_INTRINSIC_INT128 which is not defined for clang-cl. PiperOrigin-RevId: 254250739 -- 89ab385cd26b34d64130bce856253aaba96d2345 by Andy Soffer : Internal changes PiperOrigin-RevId: 254242321 -- cffc793d93eca6d6bdf7de733847b6ab4a255ae9 by CJ Johnson : Adds benchmark for InlinedVector::reserve(size_type) PiperOrigin-RevId: 254199226 -- c90c7a9fa3c8f0c9d5114036979548b055ea2f2a by Gennadiy Rozental : Import of CCTZ from GitHub. PiperOrigin-RevId: 254072387 -- c4c388beae016c9570ab54ffa1d52660e4a85b7b by Laramie Leavitt : Internal cleanup. PiperOrigin-RevId: 254062381 -- d3c992e221cc74e5372d0c8fa410170b6a43c062 by Tom Manshreck : Update distributions.h to Abseil standards PiperOrigin-RevId: 254054946 -- d15ad0035c34ef11b14fadc5a4a2d3ec415f5518 by CJ Johnson : Removes functions with only one caller from the implementation details of InlinedVector by manually inlining the definitions PiperOrigin-RevId: 254005427 -- 2f37e807efc3a8ef1f4b539bdd379917d4151520 by Andy Soffer : Initial release of Abseil Random PiperOrigin-RevId: 253999861 -- 24ed1694b6430791d781ed533a8f8ccf6cac5856 by CJ Johnson : Updates the definition of InlinedVector::assign(...)/InlinedVector::operator=(...) to new, exception-safe implementations with exception safety tests to boot PiperOrigin-RevId: 253993691 -- 5613d95f5a7e34a535cfaeadce801441e990843e by CJ Johnson : Adds benchmarks for InlinedVector::shrink_to_fit() PiperOrigin-RevId: 253989647 -- 2a96ddfdac40bbb8cb6a7f1aeab90917067c6e63 by Abseil Team : Initial release of Abseil Random PiperOrigin-RevId: 253927497 -- bf1aff8fc9ffa921ad74643e9525ecf25b0d8dc1 by Andy Soffer : Initial release of Abseil Random PiperOrigin-RevId: 253920512 -- bfc03f4a3dcda3cf3a4b84bdb84cda24e3394f41 by Laramie Leavitt : Internal change. PiperOrigin-RevId: 253886486 -- 05036cfcc078ca7c5f581a00dfb0daed568cbb69 by Eric Fiselier : Don't include `winsock2.h` because it drags in `windows.h` and friends, and they define awful macros like OPAQUE, ERROR, and more. This has the potential to break abseil users. Instead we only forward declare `timeval` and require Windows users include `winsock2.h` themselves. This is both inconsistent and poor QoI, but so including 'windows.h' is bad too. PiperOrigin-RevId: 253852615 GitOrigin-RevId: 7a6ff16a85beb730c172d5d25cf1b5e1be885c56 Change-Id: Icd6aff87da26f29ec8915da856f051129987cef6 --- absl/random/beta_distribution_test.cc | 614 ++++++++++++++++++++++++++++++++++ 1 file changed, 614 insertions(+) create mode 100644 absl/random/beta_distribution_test.cc (limited to 'absl/random/beta_distribution_test.cc') diff --git a/absl/random/beta_distribution_test.cc b/absl/random/beta_distribution_test.cc new file mode 100644 index 00000000..966ad08b --- /dev/null +++ b/absl/random/beta_distribution_test.cc @@ -0,0 +1,614 @@ +// 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/beta_distribution.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/internal/raw_logging.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 { + +template +class BetaDistributionInterfaceTest : public ::testing::Test {}; + +using RealTypes = ::testing::Types; +TYPED_TEST_CASE(BetaDistributionInterfaceTest, RealTypes); + +TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { + // The threshold for whether std::exp(1/a) is finite. + const TypeParam kSmallA = + 1.0f / std::log((std::numeric_limits::max)()); + // The threshold for whether a * std::log(a) is finite. + const TypeParam kLargeA = + std::exp(std::log((std::numeric_limits::max)()) - + std::log(std::log((std::numeric_limits::max)()))); + const TypeParam kLargeAPPC = std::exp( + std::log((std::numeric_limits::max)()) - + std::log(std::log((std::numeric_limits::max)())) - 10.0f); + using param_type = typename absl::beta_distribution::param_type; + + constexpr int kCount = 1000; + absl::InsecureBitGen gen; + const TypeParam kValues[] = { + TypeParam(1e-20), TypeParam(1e-12), TypeParam(1e-8), TypeParam(1e-4), + TypeParam(1e-3), TypeParam(0.1), TypeParam(0.25), + std::nextafter(TypeParam(0.5), TypeParam(0)), // 0.5 - epsilon + std::nextafter(TypeParam(0.5), TypeParam(1)), // 0.5 + epsilon + TypeParam(0.5), TypeParam(1.0), // + std::nextafter(TypeParam(1), TypeParam(0)), // 1 - epsilon + std::nextafter(TypeParam(1), TypeParam(2)), // 1 + epsilon + TypeParam(12.5), TypeParam(1e2), TypeParam(1e8), TypeParam(1e12), + TypeParam(1e20), // + kSmallA, // + std::nextafter(kSmallA, TypeParam(0)), // + std::nextafter(kSmallA, TypeParam(1)), // + kLargeA, // + std::nextafter(kLargeA, TypeParam(0)), // + std::nextafter(kLargeA, std::numeric_limits::max()), + kLargeAPPC, // + std::nextafter(kLargeAPPC, TypeParam(0)), + std::nextafter(kLargeAPPC, std::numeric_limits::max()), + // Boundary cases. + std::numeric_limits::max(), + std::numeric_limits::epsilon(), + std::nextafter(std::numeric_limits::min(), + TypeParam(1)), // min + epsilon + std::numeric_limits::min(), // smallest normal + std::numeric_limits::denorm_min(), // smallest denorm + std::numeric_limits::min() / 2, // denorm + std::nextafter(std::numeric_limits::min(), + TypeParam(0)), // denorm_max + }; + for (TypeParam alpha : kValues) { + for (TypeParam beta : kValues) { + ABSL_INTERNAL_LOG( + INFO, absl::StrFormat("Smoke test for Beta(%f, %f)", alpha, beta)); + + param_type param(alpha, beta); + absl::beta_distribution before(alpha, beta); + EXPECT_EQ(before.alpha(), param.alpha()); + EXPECT_EQ(before.beta(), param.beta()); + + { + absl::beta_distribution via_param(param); + EXPECT_EQ(via_param, before); + EXPECT_EQ(via_param.param(), before.param()); + } + + // Smoke test. + for (int i = 0; i < kCount; ++i) { + auto sample = before(gen); + EXPECT_TRUE(std::isfinite(sample)); + EXPECT_GE(sample, before.min()); + EXPECT_LE(sample, before.max()); + } + + // Validate stream serialization. + std::stringstream ss; + ss << before; + absl::beta_distribution after(3.8f, 1.43f); + EXPECT_NE(before.alpha(), after.alpha()); + EXPECT_NE(before.beta(), after.beta()); + EXPECT_NE(before.param(), after.param()); + EXPECT_NE(before, after); + + ss >> after; + +#if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ + defined(__ppc__) || defined(__PPC__) + if (std::is_same::value) { + // Roundtripping floating point values requires sufficient precision + // to reconstruct the exact value. It turns out that long double + // has some errors doing this on ppc. + if (alpha <= std::numeric_limits::max() && + alpha >= std::numeric_limits::lowest()) { + EXPECT_EQ(static_cast(before.alpha()), + static_cast(after.alpha())) + << ss.str(); + } + if (beta <= std::numeric_limits::max() && + beta >= std::numeric_limits::lowest()) { + EXPECT_EQ(static_cast(before.beta()), + static_cast(after.beta())) + << ss.str(); + } + continue; + } +#endif + + EXPECT_EQ(before.alpha(), after.alpha()); + EXPECT_EQ(before.beta(), after.beta()); + EXPECT_EQ(before, after) // + << ss.str() << " " // + << (ss.good() ? "good " : "") // + << (ss.bad() ? "bad " : "") // + << (ss.eof() ? "eof " : "") // + << (ss.fail() ? "fail " : ""); + } + } +} + +TYPED_TEST(BetaDistributionInterfaceTest, DegenerateCases) { + // Extreme cases when the params are abnormal. + absl::InsecureBitGen gen; + constexpr int kCount = 1000; + const TypeParam kSmallValues[] = { + std::numeric_limits::min(), + std::numeric_limits::denorm_min(), + std::nextafter(std::numeric_limits::min(), + TypeParam(0)), // denorm_max + std::numeric_limits::epsilon(), + }; + const TypeParam kLargeValues[] = { + std::numeric_limits::max() * static_cast(0.9999), + std::numeric_limits::max() - 1, + std::numeric_limits::max(), + }; + { + // Small alpha and beta. + // Useful WolframAlpha plots: + // * plot InverseBetaRegularized[x, 0.0001, 0.0001] from 0.495 to 0.505 + // * Beta[1.0, 0.0000001, 0.0000001] + // * Beta[0.9999, 0.0000001, 0.0000001] + for (TypeParam alpha : kSmallValues) { + for (TypeParam beta : kSmallValues) { + int zeros = 0; + int ones = 0; + absl::beta_distribution d(alpha, beta); + for (int i = 0; i < kCount; ++i) { + TypeParam x = d(gen); + if (x == 0.0) { + zeros++; + } else if (x == 1.0) { + ones++; + } + } + EXPECT_EQ(ones + zeros, kCount); + if (alpha == beta) { + EXPECT_NE(ones, 0); + EXPECT_NE(zeros, 0); + } + } + } + } + { + // Small alpha, large beta. + // Useful WolframAlpha plots: + // * plot InverseBetaRegularized[x, 0.0001, 10000] from 0.995 to 1 + // * Beta[0, 0.0000001, 1000000] + // * Beta[0.001, 0.0000001, 1000000] + // * Beta[1, 0.0000001, 1000000] + for (TypeParam alpha : kSmallValues) { + for (TypeParam beta : kLargeValues) { + absl::beta_distribution d(alpha, beta); + for (int i = 0; i < kCount; ++i) { + EXPECT_EQ(d(gen), 0.0); + } + } + } + } + { + // Large alpha, small beta. + // Useful WolframAlpha plots: + // * plot InverseBetaRegularized[x, 10000, 0.0001] from 0 to 0.001 + // * Beta[0.99, 1000000, 0.0000001] + // * Beta[1, 1000000, 0.0000001] + for (TypeParam alpha : kLargeValues) { + for (TypeParam beta : kSmallValues) { + absl::beta_distribution d(alpha, beta); + for (int i = 0; i < kCount; ++i) { + EXPECT_EQ(d(gen), 1.0); + } + } + } + } + { + // Large alpha and beta. + absl::beta_distribution d(std::numeric_limits::max(), + std::numeric_limits::max()); + for (int i = 0; i < kCount; ++i) { + EXPECT_EQ(d(gen), 0.5); + } + } + { + // Large alpha and beta but unequal. + absl::beta_distribution d( + std::numeric_limits::max(), + std::numeric_limits::max() * 0.9999); + for (int i = 0; i < kCount; ++i) { + TypeParam x = d(gen); + EXPECT_NE(x, 0.5f); + EXPECT_FLOAT_EQ(x, 0.500025f); + } + } +} + +class BetaDistributionModel { + public: + explicit BetaDistributionModel(::testing::tuple p) + : alpha_(::testing::get<0>(p)), beta_(::testing::get<1>(p)) {} + + double Mean() const { return alpha_ / (alpha_ + beta_); } + + double Variance() const { + return alpha_ * beta_ / (alpha_ + beta_ + 1) / (alpha_ + beta_) / + (alpha_ + beta_); + } + + double Kurtosis() const { + return 3 + 6 * + ((alpha_ - beta_) * (alpha_ - beta_) * (alpha_ + beta_ + 1) - + alpha_ * beta_ * (2 + alpha_ + beta_)) / + alpha_ / beta_ / (alpha_ + beta_ + 2) / (alpha_ + beta_ + 3); + } + + protected: + const double alpha_; + const double beta_; +}; + +class BetaDistributionTest + : public ::testing::TestWithParam<::testing::tuple>, + public BetaDistributionModel { + public: + BetaDistributionTest() : BetaDistributionModel(GetParam()) {} + + protected: + template + bool SingleZTestOnMeanAndVariance(double p, size_t samples); + + template + bool SingleChiSquaredTest(double p, size_t samples, size_t buckets); + + absl::InsecureBitGen rng_; +}; + +template +bool BetaDistributionTest::SingleZTestOnMeanAndVariance(double p, + size_t samples) { + D dis(alpha_, beta_); + + std::vector data; + data.reserve(samples); + for (size_t i = 0; i < samples; i++) { + const double variate = dis(rng_); + EXPECT_FALSE(std::isnan(variate)); + // Note that equality is allowed on both sides. + EXPECT_GE(variate, 0.0); + EXPECT_LE(variate, 1.0); + data.push_back(variate); + } + + // We validate that the sample mean and sample variance are indeed from a + // Beta distribution with the given shape parameters. + const auto m = absl::random_internal::ComputeDistributionMoments(data); + + // The variance of the sample mean is variance / n. + const double mean_stddev = std::sqrt(Variance() / static_cast(m.n)); + + // The variance of the sample variance is (approximately): + // (kurtosis - 1) * variance^2 / n + const double variance_stddev = std::sqrt( + (Kurtosis() - 1) * Variance() * Variance() / static_cast(m.n)); + // z score for the sample variance. + const double z_variance = (m.variance - Variance()) / variance_stddev; + + const double max_err = absl::random_internal::MaxErrorTolerance(p); + const double z_mean = absl::random_internal::ZScore(Mean(), m); + const bool pass = + absl::random_internal::Near("z", z_mean, 0.0, max_err) && + absl::random_internal::Near("z_variance", z_variance, 0.0, max_err); + if (!pass) { + ABSL_INTERNAL_LOG( + INFO, + absl::StrFormat( + "Beta(%f, %f), " + "mean: sample %f, expect %f, which is %f stddevs away, " + "variance: sample %f, expect %f, which is %f stddevs away.", + alpha_, beta_, m.mean, Mean(), + std::abs(m.mean - Mean()) / mean_stddev, m.variance, Variance(), + std::abs(m.variance - Variance()) / variance_stddev)); + } + return pass; +} + +template +bool BetaDistributionTest::SingleChiSquaredTest(double p, size_t samples, + size_t buckets) { + constexpr double kErr = 1e-7; + std::vector cutoffs, expected; + const double bucket_width = 1.0 / static_cast(buckets); + int i = 1; + int unmerged_buckets = 0; + for (; i < buckets; ++i) { + const double p = bucket_width * static_cast(i); + const double boundary = + absl::random_internal::BetaIncompleteInv(alpha_, beta_, p); + // The intention is to add `boundary` to the list of `cutoffs`. It becomes + // problematic, however, when the boundary values are not monotone, due to + // numerical issues when computing the inverse regularized incomplete + // Beta function. In these cases, we merge that bucket with its previous + // neighbor and merge their expected counts. + if ((cutoffs.empty() && boundary < kErr) || + (!cutoffs.empty() && boundary <= cutoffs.back())) { + unmerged_buckets++; + continue; + } + if (boundary >= 1.0 - 1e-10) { + break; + } + cutoffs.push_back(boundary); + expected.push_back(static_cast(1 + unmerged_buckets) * + bucket_width * static_cast(samples)); + unmerged_buckets = 0; + } + cutoffs.push_back(std::numeric_limits::infinity()); + // Merge all remaining buckets. + expected.push_back(static_cast(buckets - i + 1) * bucket_width * + static_cast(samples)); + // Make sure that we don't merge all the buckets, making this test + // meaningless. + EXPECT_GE(cutoffs.size(), 3) << alpha_ << ", " << beta_; + + D dis(alpha_, beta_); + + std::vector counts(cutoffs.size(), 0); + for (int i = 0; i < samples; i++) { + 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 beta distributed with the + // provided alpha, beta params (not estimated from the data). + const int dof = cutoffs.size() - 1; + + const double chi_square = absl::random_internal::ChiSquare( + counts.begin(), counts.end(), expected.begin(), expected.end()); + const bool pass = + (absl::random_internal::ChiSquarePValue(chi_square, dof) >= p); + if (!pass) { + for (int i = 0; i < cutoffs.size(); i++) { + ABSL_INTERNAL_LOG( + INFO, absl::StrFormat("cutoff[%d] = %f, actual count %d, expected %d", + i, cutoffs[i], counts[i], + static_cast(expected[i]))); + } + + ABSL_INTERNAL_LOG( + INFO, absl::StrFormat( + "Beta(%f, %f) %s %f, p = %f", alpha_, beta_, + absl::random_internal::kChiSquared, chi_square, + absl::random_internal::ChiSquarePValue(chi_square, dof))); + } + return pass; +} + +TEST_P(BetaDistributionTest, TestSampleStatistics) { + static constexpr int kRuns = 20; + static constexpr double kPFail = 0.02; + const double p = + absl::random_internal::RequiredSuccessProbability(kPFail, kRuns); + static constexpr int kSampleCount = 10000; + static constexpr int kBucketCount = 100; + int failed = 0; + for (int i = 0; i < kRuns; ++i) { + if (!SingleZTestOnMeanAndVariance>( + p, kSampleCount)) { + failed++; + } + if (!SingleChiSquaredTest>( + 0.005, kSampleCount, kBucketCount)) { + failed++; + } + } + // Set so that the test is not flaky at --runs_per_test=10000 + EXPECT_LE(failed, 5); +} + +std::string ParamName( + const ::testing::TestParamInfo<::testing::tuple>& info) { + std::string name = absl::StrCat("alpha_", ::testing::get<0>(info.param), + "__beta_", ::testing::get<1>(info.param)); + return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}}); +} + +INSTANTIATE_TEST_CASE_P( + TestSampleStatisticsCombinations, BetaDistributionTest, + ::testing::Combine(::testing::Values(0.1, 0.2, 0.9, 1.1, 2.5, 10.0, 123.4), + ::testing::Values(0.1, 0.2, 0.9, 1.1, 2.5, 10.0, 123.4)), + ParamName); + +INSTANTIATE_TEST_CASE_P( + TestSampleStatistics_SelectedPairs, BetaDistributionTest, + ::testing::Values(std::make_pair(0.5, 1000), std::make_pair(1000, 0.5), + std::make_pair(900, 1000), std::make_pair(10000, 20000), + std::make_pair(4e5, 2e7), std::make_pair(1e7, 1e5)), + ParamName); + +// NOTE: absl::beta_distribution is not guaranteed to be stable. +TEST(BetaDistributionTest, StabilityTest) { + // absl::beta_distribution stability relies on the stability of + // absl::random_interna::RandU64ToDouble, std::exp, std::log, std::pow, + // and std::sqrt. + // + // This test also depends on the stability of std::frexp. + using testing::ElementsAre; + absl::random_internal::sequence_urbg urbg({ + 0xffff00000000e6c8ull, 0xffff0000000006c8ull, 0x800003766295CFA9ull, + 0x11C819684E734A41ull, 0x832603766295CFA9ull, 0x7fbe76c8b4395800ull, + 0xB3472DCA7B14A94Aull, 0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, + 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull, 0x00035C904C70A239ull, + 0x00009E0BCBAADE14ull, 0x0000000000622CA7ull, 0x4864f22c059bf29eull, + 0x247856d8b862665cull, 0xe46e86e9a1337e10ull, 0xd8c8541f3519b133ull, + 0xffe75b52c567b9e4ull, 0xfffff732e5709c5bull, 0xff1f7f0b983532acull, + 0x1ec2e8986d2362caull, 0xC332DDEFBE6C5AA5ull, 0x6558218568AB9702ull, + 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, 0xECDD4775619F1510ull, + 0x814c8e35fe9a961aull, 0x0c3cd59c9b638a02ull, 0xcb3bb6478a07715cull, + 0x1224e62c978bbc7full, 0x671ef2cb04e81f6eull, 0x3c1cbd811eaf1808ull, + 0x1bbc23cfa8fac721ull, 0xa4c2cda65e596a51ull, 0xb77216fad37adf91ull, + 0x836d794457c08849ull, 0xe083df03475f49d7ull, 0xbc9feb512e6b0d6cull, + 0xb12d74fdd718c8c5ull, 0x12ff09653bfbe4caull, 0x8dd03a105bc4ee7eull, + 0x5738341045ba0d85ull, 0xf3fd722dc65ad09eull, 0xfa14fd21ea2a5705ull, + 0xffe6ea4d6edb0c73ull, 0xD07E9EFE2BF11FB4ull, 0x95DBDA4DAE909198ull, + 0xEAAD8E716B93D5A0ull, 0xD08ED1D0AFC725E0ull, 0x8E3C5B2F8E7594B7ull, + 0x8FF6E2FBF2122B64ull, 0x8888B812900DF01Cull, 0x4FAD5EA0688FC31Cull, + 0xD1CFF191B3A8C1ADull, 0x2F2F2218BE0E1777ull, 0xEA752DFE8B021FA1ull, + }); + + // Convert the real-valued result into a unit64 where we compare + // 5 (float) or 10 (double) decimal digits plus the base-2 exponent. + auto float_to_u64 = [](float d) { + int exp = 0; + auto f = std::frexp(d, &exp); + return (static_cast(1e5 * f) * 10000) + std::abs(exp); + }; + auto double_to_u64 = [](double d) { + int exp = 0; + auto f = std::frexp(d, &exp); + return (static_cast(1e10 * f) * 10000) + std::abs(exp); + }; + + std::vector output(20); + { + // Algorithm Joehnk (float) + absl::beta_distribution dist(0.1f, 0.2f); + std::generate(std::begin(output), std::end(output), + [&] { return float_to_u64(dist(urbg)); }); + EXPECT_EQ(44, urbg.invocations()); + EXPECT_THAT(output, // + testing::ElementsAre( + 998340000, 619030004, 500000001, 999990000, 996280000, + 500000001, 844740004, 847210001, 999970000, 872320000, + 585480007, 933280000, 869080042, 647670031, 528240004, + 969980004, 626050008, 915930002, 833440033, 878040015)); + } + + urbg.reset(); + { + // Algorithm Joehnk (double) + absl::beta_distribution dist(0.1, 0.2); + std::generate(std::begin(output), std::end(output), + [&] { return double_to_u64(dist(urbg)); }); + EXPECT_EQ(44, urbg.invocations()); + EXPECT_THAT( + output, // + testing::ElementsAre( + 99834713000000, 61903356870004, 50000000000001, 99999721170000, + 99628374770000, 99999999990000, 84474397860004, 84721276240001, + 99997407490000, 87232528120000, 58548364780007, 93328932910000, + 86908237770042, 64767917930031, 52824581970004, 96998544140004, + 62605946270008, 91593604380002, 83345031740033, 87804397230015)); + } + + urbg.reset(); + { + // Algorithm Cheng 1 + absl::beta_distribution dist(0.9, 2.0); + std::generate(std::begin(output), std::end(output), + [&] { return double_to_u64(dist(urbg)); }); + EXPECT_EQ(62, urbg.invocations()); + EXPECT_THAT( + output, // + testing::ElementsAre( + 62069004780001, 64433204450001, 53607416560000, 89644295430008, + 61434586310019, 55172615890002, 62187161490000, 56433684810003, + 80454622050005, 86418558710003, 92920514700001, 64645184680001, + 58549183380000, 84881283650005, 71078728590002, 69949694970000, + 73157461710001, 68592191300001, 70747623900000, 78584696930005)); + } + + urbg.reset(); + { + // Algorithm Cheng 2 + absl::beta_distribution dist(1.5, 2.5); + std::generate(std::begin(output), std::end(output), + [&] { return double_to_u64(dist(urbg)); }); + EXPECT_EQ(54, urbg.invocations()); + EXPECT_THAT( + output, // + testing::ElementsAre( + 75000029250001, 76751482860001, 53264575220000, 69193133650005, + 78028324470013, 91573587560002, 59167523770000, 60658618560002, + 80075870540000, 94141320460004, 63196592770003, 78883906300002, + 96797992590001, 76907587800001, 56645167560000, 65408302280003, + 53401156320001, 64731238570000, 83065573750001, 79788333820001)); + } +} + +// 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(BetaDistributionTest, AlgorithmBounds) { + { + absl::random_internal::sequence_urbg urbg( + {0x7fbe76c8b4395800ull, 0x8000000000000000ull}); + // u=0.499, v=0.5 + absl::beta_distribution dist(1e-4, 1e-4); + double a = dist(urbg); + EXPECT_EQ(a, 2.0202860861567108529e-09); + EXPECT_EQ(2, urbg.invocations()); + } + + // Test that both the float & double algorithms appropriately reject the + // initial draw. + { + // 1/alpha = 1/beta = 2. + absl::beta_distribution dist(0.5, 0.5); + + // first two outputs are close to 1.0 - epsilon, + // thus: (u ^ 2 + v ^ 2) > 1.0 + absl::random_internal::sequence_urbg urbg( + {0xffff00000006e6c8ull, 0xffff00000007c7c8ull, 0x800003766295CFA9ull, + 0x11C819684E734A41ull}); + { + double y = absl::beta_distribution(0.5, 0.5)(urbg); + EXPECT_EQ(4, urbg.invocations()); + EXPECT_EQ(y, 0.9810668952633862) << y; + } + + // ...and: log(u) * a ~= log(v) * b ~= -0.02 + // thus z ~= -0.02 + log(1 + e(~0)) + // ~= -0.02 + 0.69 + // thus z > 0 + urbg.reset(); + { + float x = absl::beta_distribution(0.5, 0.5)(urbg); + EXPECT_EQ(4, urbg.invocations()); + EXPECT_NEAR(0.98106688261032104, x, 0.0000005) << x << "f"; + } + } +} + +} // namespace -- cgit v1.2.3