Fix numerical defects in absl::random_internal test utilities.
* Replace `chi_square`'s low-accuracy `normal_survival`, `POZ`, and
`capped_exp` approximations with `std::erfc` and `std::exp`, cast unsigned
counts to `double` before subtracting in `ChiSquare`, and guard
`p_value >= 1.0`, infinite/subnormal inputs, and `9.0 * dof` overflow.
* Fix `BetaIncomplete{,Inv}` AS109 symmetry (`alpha > 0.5`),
initial-estimate typos, subnormal clamping, step-limit tracking, and
invalid-shape handling, and guard `std::fma` on hardware FMA availability.
* Avoid `1 - p_fail` and `2x - 1` cancellation in
`RequiredSuccessProbability`, `InverseNormalSurvival` (adding extreme-tail
Halley refinement), and `MaxErrorTolerance`, and handle `erfinv(+-1)`
boundaries.
PiperOrigin-RevId: 1022885461
diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt
index b2c3fa2..700c271 100644
--- a/absl/random/CMakeLists.txt
+++ b/absl/random/CMakeLists.txt
@@ -971,6 +971,7 @@
${ABSL_DEFAULT_LINKOPTS}
DEPS
absl::random_internal_distribution_test_util
+ GTest::gmock
GTest::gtest_main
)
@@ -1035,6 +1036,7 @@
DEPS
absl::core_headers
absl::random_internal_distribution_test_util
+ GTest::gmock
GTest::gtest_main
)
diff --git a/absl/random/internal/chi_square.cc b/absl/random/internal/chi_square.cc
index 481c1c3..2dd4a71 100644
--- a/absl/random/internal/chi_square.cc
+++ b/absl/random/internal/chi_square.cc
@@ -14,6 +14,7 @@
#include "absl/random/internal/chi_square.h"
+#include <algorithm>
#include <cmath>
#include "absl/base/config.h"
@@ -24,103 +25,40 @@
namespace random_internal {
namespace {
-#if defined(__EMSCRIPTEN__)
-// Workaround __EMSCRIPTEN__ error: llvm_fma_f64 not found.
-inline double fma(double x, double y, double z) { return (x * y) + z; }
-#endif
+constexpr int kLargeDOF = 150;
-// Use Horner's method to evaluate a polynomial.
-template <typename T, unsigned N>
-inline T EvaluatePolynomial(T x, const T (&poly)[N]) {
-#if !defined(__EMSCRIPTEN__)
- using std::fma;
-#endif
- T p = poly[N - 1];
- for (unsigned i = 2; i <= N; i++) {
- p = fma(p, x, poly[N - i]);
- }
- return p;
-}
+// 1 / sqrt(2). Defined explicitly instead of non-standard M_SQRT1_2 for
+// portability (e.g. Windows/MSVC).
+constexpr double kSqrt1_2 = 0.70710678118654752440084436210485;
-static constexpr int kLargeDOF = 150;
-
-// Returns the probability of a normal z-value.
-//
-// Adapted from the POZ function in:
-// Ibbetson D, Algorithm 209
-// Collected Algorithms of the CACM 1963 p. 616
-//
-double POZ(double z) {
- static constexpr double kP1[] = {
- 0.797884560593, -0.531923007300, 0.319152932694,
- -0.151968751364, 0.059054035642, -0.019198292004,
- 0.005198775019, -0.001075204047, 0.000124818987,
- };
- static constexpr double kP2[] = {
- 0.999936657524, 0.000535310849, -0.002141268741, 0.005353579108,
- -0.009279453341, 0.011630447319, -0.010557625006, 0.006549791214,
- -0.002034254874, -0.000794620820, 0.001390604284, -0.000676904986,
- -0.000019538132, 0.000152529290, -0.000045255659,
- };
-
- const double kZMax = 6.0; // Maximum meaningful z-value.
- if (z == 0.0) {
- return 0.5;
- }
- double x;
- double y = 0.5 * std::fabs(z);
- if (y >= (kZMax * 0.5)) {
- x = 1.0;
- } else if (y < 1.0) {
- double w = y * y;
- x = EvaluatePolynomial(w, kP1) * y * 2.0;
- } else {
- y -= 2.0;
- x = EvaluatePolynomial(y, kP2);
- }
- return z > 0.0 ? ((x + 1.0) * 0.5) : ((1.0 - x) * 0.5);
-}
-
-// Approximates the survival function of the normal distribution.
-//
-// Algorithm 26.2.18, from:
-// [Abramowitz and Stegun, Handbook of Mathematical Functions,p.932]
-// http://people.math.sfu.ca/~cbm/aands/abramowitz_and_stegun.pdf
-//
-double normal_survival(double z) {
- // Maybe replace with the alternate formulation.
- // 0.5 * erfc((x - mean)/(sqrt(2) * sigma))
- static constexpr double kR[] = {
- 1.0, 0.196854, 0.115194, 0.000344, 0.019527,
- };
- double r = EvaluatePolynomial(z, kR);
- r *= r;
- return 0.5 / (r * r);
-}
+// Returns the survival function of the standard normal distribution:
+// P(Z > z) = 1 - Phi(z) = 0.5 * erfc(z / sqrt(2)).
+double normal_survival(double z) { return 0.5 * std::erfc(z * kSqrt1_2); }
} // namespace
-// Calculates the critical chi-square value given degrees-of-freedom and a
-// p-value, usually using bisection. Also known by the name CRITCHI.
+// Calculates the critical chi-square value x given degrees of freedom and
+// cumulative probability p = P(X <= x) (upper-tail p-value 1 - p), using
+// Wilson-Hilferty for large dof and bisection otherwise. Also known as CRITCHI.
double ChiSquareValue(int dof, double p) {
static constexpr double kChiEpsilon =
0.000001; // Accuracy of the approximation.
static constexpr double kChiMax = 99999.0; // Maximum chi-squared value.
const double p_value = 1.0 - p;
- if (dof < 1 || p_value > 1.0) {
+ if (dof < 1 || p_value >= 1.0) {
return 0.0;
}
if (dof > kLargeDOF) {
- // For large degrees of freedom, use the normal approximation by
- // Wilson, E. B. and Hilferty, M. M. (1931)
- // chi^2 - mean
- // Z = --------------
- // stddev
+ // For large degrees of freedom, use the Wilson-Hilferty (1931) cube-root
+ // normal approximation:
+ // (chi^2 / dof)^(1/3) - mean
+ // Z = ----------------------------
+ // stddev
const double z = InverseNormalSurvival(p_value);
- const double mean = 1 - 2.0 / (9 * dof);
- const double variance = 2.0 / (9 * dof);
+ const double mean = 1 - 2.0 / (9.0 * dof);
+ const double variance = 2.0 / (9.0 * dof);
// Cannot use this method if the variance is 0.
if (variance != 0) {
double term = z * std::sqrt(variance) + mean;
@@ -133,7 +71,7 @@
// Otherwise search for the p value by bisection
double min_chisq = 0.0;
double max_chisq = kChiMax;
- double current = dof / std::sqrt(p_value);
+ double current = std::min(dof / std::sqrt(p_value), max_chisq);
while ((max_chisq - min_chisq) > kChiEpsilon) {
if (ChiSquarePValue(current, dof) < p_value) {
max_chisq = current;
@@ -158,30 +96,6 @@
static constexpr double kInverseSqrtPi =
0.5641895835477562869480795; // 1/(Sqrt[Pi])
- // For large degrees of freedom, use the normal approximation by
- // Wilson, E. B. and Hilferty, M. M. (1931)
- // Via Wikipedia:
- // By the Central Limit Theorem, because the chi-square distribution is the
- // sum of k independent random variables with finite mean and variance, it
- // converges to a normal distribution for large k.
- if (dof > kLargeDOF) {
- // Re-scale everything.
- const double chi_square_scaled = std::pow(chi_square / dof, 1.0 / 3);
- const double mean = 1 - 2.0 / (9 * dof);
- const double variance = 2.0 / (9 * dof);
- // If variance is 0, this method cannot be used.
- if (variance != 0) {
- const double z = (chi_square_scaled - mean) / std::sqrt(variance);
- if (z > 0) {
- return normal_survival(z);
- } else if (z < 0) {
- return 1.0 - normal_survival(-z);
- } else {
- return 0.5;
- }
- }
- }
-
// The chi square function is >= 0 for any degrees of freedom.
// In other words, probability that the chi square function >= 0 is 1.
if (chi_square <= 0.0) return 1.0;
@@ -189,15 +103,34 @@
// If the degrees of freedom is zero, the chi square function is always 0 by
// definition. In other words, the probability that the chi square function
// is > 0 is zero (chi square values <= 0 have been filtered above).
- if (dof < 1) return 0;
+ if (dof < 1) return 0.0;
- auto capped_exp = [](double x) { return x < -20 ? 0.0 : std::exp(x); };
+ // For large degrees of freedom, use the Wilson-Hilferty (1931) cube-root
+ // normal approximation: (chi^2 / dof)^(1/3) ~ N(1 - 2/(9*dof), 2/(9*dof)).
+ if (dof > kLargeDOF) {
+ // Re-scale everything.
+ const double chi_square_scaled = std::pow(chi_square / dof, 1.0 / 3);
+ const double mean = 1 - 2.0 / (9.0 * dof);
+ const double variance = 2.0 / (9.0 * dof);
+ // If variance is 0, this method cannot be used.
+ if (variance != 0) {
+ const double z = (chi_square_scaled - mean) / std::sqrt(variance);
+ return normal_survival(z);
+ }
+ }
+
+ if (std::isinf(chi_square)) return 0.0;
+
+ // Above kBigX, sum terms in log-space to avoid a^k / k! overflow in the
+ // direct recurrence below.
static constexpr double kBigX = 20;
double a = 0.5 * chi_square;
+ if (a == 0.0) return 1.0;
const bool even = !(dof & 1); // True if dof is an even number.
- const double y = capped_exp(-a);
- double s = even ? y : (2.0 * POZ(-std::sqrt(chi_square)));
+ const double y = std::exp(-a);
+ // For odd dof, P(chi^2_1 > chi_square) = erfc(sqrt(chi_square / 2)).
+ double s = even ? y : std::erfc(std::sqrt(a));
if (dof <= 2) {
return s;
@@ -210,7 +143,7 @@
double c = std::log(a);
while (z <= chi_square) {
e = std::log(z) + e;
- s += capped_exp(c * z - a - e);
+ s += std::exp(c * z - a - e);
z += 1.0;
}
return s;
diff --git a/absl/random/internal/chi_square.h b/absl/random/internal/chi_square.h
index 07f4fbe..bb0fa81 100644
--- a/absl/random/internal/chi_square.h
+++ b/absl/random/internal/chi_square.h
@@ -60,7 +60,7 @@
assert(*eit > 0);
}
double e = static_cast<double>(*eit);
- double d = static_cast<double>(*it - *eit);
+ double d = static_cast<double>(*it) - e;
if (d != 0) {
assert(e > 0);
chi_square += (d * d) / e;
@@ -74,9 +74,9 @@
// The following methods can be used for an arbitrary significance level.
//
-// Calculates critical chi-square values to produce the given p-value using a
-// bisection search for a value within epsilon, relying on the monotonicity of
-// ChiSquarePValue().
+// Calculates the critical chi-square value x such that P(X <= x) = p
+// (i.e., upper-tail p-value 1 - p), using Wilson-Hilferty for large dof
+// (> 150) and bisection over ChiSquarePValue() otherwise.
double ChiSquareValue(int dof, double p);
// Calculates the p-value (probability) of a given chi-square value.
diff --git a/absl/random/internal/chi_square_test.cc b/absl/random/internal/chi_square_test.cc
index 964cd22..b91ab6e 100644
--- a/absl/random/internal/chi_square_test.cc
+++ b/absl/random/internal/chi_square_test.cc
@@ -15,12 +15,15 @@
#include "absl/random/internal/chi_square.h"
#include <algorithm>
+#include <cmath>
#include <cstddef>
#include <cstdint>
#include <iterator>
+#include <limits>
#include <numeric>
#include <vector>
+#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/algorithm/container.h"
#include "absl/base/macros.h"
@@ -29,6 +32,8 @@
using absl::random_internal::ChiSquarePValue;
using absl::random_internal::ChiSquareValue;
using absl::random_internal::ChiSquareWithExpected;
+using ::testing::DoubleEq;
+using ::testing::DoubleNear;
namespace {
@@ -362,4 +367,121 @@
EXPECT_NEAR(p_b, 0.4528180, 1e-5); // Accept the null hypothesis.
}
+double WilsonHilfertyChiSquare(int dof, double z) {
+ const double mean = 1.0 - 2.0 / (9.0 * dof);
+ const double stddev = std::sqrt(2.0 / (9.0 * dof));
+ const double term = mean + z * stddev;
+ return dof * (term * term * term);
+}
+
+TEST(ChiSquareTest, LargeDofNormalSurvivalTails) {
+ constexpr int kDof = 200;
+ EXPECT_THAT(ChiSquarePValue(WilsonHilfertyChiSquare(kDof, -5.0), kDof),
+ DoubleNear(0.99999971334842808, 1e-12));
+ EXPECT_THAT(ChiSquarePValue(WilsonHilfertyChiSquare(kDof, -2.0), kDof),
+ DoubleNear(0.97724986805182079, 1e-12));
+ EXPECT_THAT(ChiSquarePValue(WilsonHilfertyChiSquare(kDof, 0.0), kDof),
+ DoubleNear(0.5, 1e-12));
+ // Extreme upper-tail z-scores (normal_survival uses std::erfc).
+ EXPECT_THAT(ChiSquarePValue(WilsonHilfertyChiSquare(kDof, 5.0), kDof),
+ DoubleNear(2.8665157187919455e-7, 1e-12));
+ EXPECT_THAT(ChiSquarePValue(WilsonHilfertyChiSquare(kDof, 8.0), kDof),
+ DoubleNear(6.2209605742718204e-16, 1e-20));
+ EXPECT_THAT(ChiSquarePValue(WilsonHilfertyChiSquare(kDof, 20.0), kDof),
+ DoubleNear(2.7536241186063318e-89, 1e-95));
+
+ EXPECT_THAT(ChiSquarePValue(std::numeric_limits<double>::infinity(), kDof),
+ DoubleEq(0.0));
+ EXPECT_THAT(ChiSquarePValue(-std::numeric_limits<double>::infinity(), kDof),
+ DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(-1.0, kDof), DoubleEq(1.0));
+}
+
+TEST(ChiSquareTest, ExtremeTailNoCliffs) {
+ // Extreme upper tails beyond |z| = 6 (dof = 1) and exp(-20) (dof = 2).
+ EXPECT_THAT(ChiSquareValue(1, 1.0 - 1e-10), DoubleNear(41.821456, 1e-4));
+ EXPECT_THAT(ChiSquareValue(1, 1.0 - 1e-12), DoubleNear(50.844128, 1e-4));
+ EXPECT_THAT(ChiSquareValue(2, 1.0 - 1e-10), DoubleNear(46.051702, 1e-4));
+ EXPECT_THAT(ChiSquareValue(5, 1.0 - 1e-10), DoubleNear(55.562399, 1e-4));
+
+ // Matching p-values in the extreme upper tail should not underflow to 0.0.
+ EXPECT_THAT(ChiSquarePValue(41.821456, 1), DoubleNear(1e-10, 1e-13));
+ EXPECT_THAT(ChiSquarePValue(41.61, 1), DoubleNear(1.11421889e-10, 1e-13));
+ EXPECT_THAT(ChiSquarePValue(46.051702, 2), DoubleNear(1e-10, 1e-13));
+ EXPECT_THAT(ChiSquarePValue(55.562399, 5), DoubleNear(1e-10, 1e-13));
+
+ // Large dof extreme tail round-trip.
+ const double large_dof_val = ChiSquareValue(200, 1.0 - 1e-10);
+ EXPECT_THAT(ChiSquarePValue(large_dof_val, 200), DoubleNear(1e-10, 1e-14));
+
+ // Infinite inputs for small dof.
+ EXPECT_THAT(ChiSquarePValue(std::numeric_limits<double>::infinity(), 1),
+ DoubleEq(0.0));
+ EXPECT_THAT(ChiSquarePValue(std::numeric_limits<double>::infinity(), 10),
+ DoubleEq(0.0));
+ EXPECT_THAT(ChiSquarePValue(-std::numeric_limits<double>::infinity(), 1),
+ DoubleEq(1.0));
+}
+
+TEST(ChiSquareTest, UnsignedIteratorsActualLessThanExpected) {
+ const std::vector<uint64_t> actual_u64 = {10, 20, 30};
+ const std::vector<uint64_t> expected_u64 = {20, 20, 20};
+ EXPECT_THAT(ChiSquare(actual_u64.begin(), actual_u64.end(),
+ expected_u64.begin(), expected_u64.end()),
+ DoubleNear(10.0, 1e-12));
+
+ const std::vector<size_t> actual_sz = {5, 10, 15};
+ const std::vector<size_t> expected_sz = {10, 20, 30};
+ EXPECT_THAT(ChiSquare(actual_sz.begin(), actual_sz.end(), expected_sz.begin(),
+ expected_sz.end()),
+ DoubleNear(15.0, 1e-12));
+
+ const std::vector<uint32_t> actual_u32 = {100, 999};
+ const std::vector<uint32_t> expected_u32 = {200, 1000};
+ EXPECT_THAT(ChiSquare(actual_u32.begin(), actual_u32.end(),
+ expected_u32.begin(), expected_u32.end()),
+ DoubleNear(50.001, 1e-12));
+}
+
+TEST(ChiSquareTest, SubnormalChiSquarePValue) {
+ const double kDenormMin = std::numeric_limits<double>::denorm_min();
+ const double kMinNormal = std::numeric_limits<double>::min();
+
+ // When 0.5 * chi_square underflows to 0.0, odd dof in [3, 150] must return
+ // 1.0 rather than NaN from (+inf) * 0.0.
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 1), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 2), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 3), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 5), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 7), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 149), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 150), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kDenormMin, 200), DoubleEq(1.0));
+
+ EXPECT_THAT(ChiSquarePValue(2.0 * kDenormMin, 3), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kMinNormal, 3), DoubleEq(1.0));
+ EXPECT_THAT(ChiSquarePValue(kMinNormal, 149), DoubleEq(1.0));
+}
+
+TEST(ChiSquareTest, VeryLargeDofNoSignedOverflow) {
+ constexpr int kOverflowDof = std::numeric_limits<int>::max() / 9 + 1;
+ constexpr int kMaxDof = std::numeric_limits<int>::max();
+
+ EXPECT_THAT(
+ ChiSquarePValue(WilsonHilfertyChiSquare(kOverflowDof, 0.0), kOverflowDof),
+ DoubleNear(0.5, 1e-12));
+ EXPECT_THAT(
+ ChiSquarePValue(WilsonHilfertyChiSquare(kOverflowDof, 2.0), kOverflowDof),
+ DoubleNear(0.02275013194817921, 1e-12));
+ EXPECT_THAT(ChiSquareValue(kOverflowDof, 0.5),
+ DoubleNear(WilsonHilfertyChiSquare(kOverflowDof, 0.0), 1e-3));
+
+ EXPECT_THAT(ChiSquarePValue(ChiSquareValue(kMaxDof, 0.5), kMaxDof),
+ DoubleNear(0.5, 1e-8));
+ EXPECT_THAT(ChiSquarePValue(ChiSquareValue(kMaxDof, 0.95), kMaxDof),
+ DoubleNear(0.05, 1e-8));
+ EXPECT_THAT(ChiSquarePValue(ChiSquareValue(kMaxDof, 0.999), kMaxDof),
+ DoubleNear(0.001, 1e-8));
+}
+
} // namespace
diff --git a/absl/random/internal/distribution_test_util.cc b/absl/random/internal/distribution_test_util.cc
index 4ae6fcb..e342499 100644
--- a/absl/random/internal/distribution_test_util.cc
+++ b/absl/random/internal/distribution_test_util.cc
@@ -14,7 +14,6 @@
#include "absl/random/internal/distribution_test_util.h"
-#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
@@ -34,11 +33,93 @@
namespace random_internal {
namespace {
-#if defined(__EMSCRIPTEN__)
-// Workaround __EMSCRIPTEN__ error: llvm_fma_f64 not found.
-inline double fma(double x, double y, double z) { return (x * y) + z; }
+// Use std::fma only when hardware FMA is available, avoiding software libm
+// fma() overhead and Emscripten llvm_fma_f64 link issues.
+#if defined(FP_FAST_FMA) || defined(__FP_FAST_FMA) || defined(__FMA__) || \
+ defined(__aarch64__) || defined(_M_ARM64)
+inline double Fma(double a, double b, double c) { return std::fma(a, b, c); }
+#else
+inline double Fma(double a, double b, double c) { return a * b + c; }
#endif
+constexpr double kPi = 3.1415926535897932384626433832795;
+constexpr double kSqrt2 = 1.4142135623730950488016887242097;
+constexpr double kSqrt1_2 = 0.70710678118654752440084436210485;
+constexpr double kInvSqrt2Pi = 0.39894228040143267793994605993438;
+
+// Evaluates the polynomial factor p(w) for Giles's erfinv(x) = p(w) * x,
+// where w = -log((1 - x) * (1 + x)) is in [0, ~36].
+double ErfInvPoly(double w) {
+ double p = 0.0;
+ if (w < 6.250000) {
+ w = w - 3.125000;
+ p = -3.6444120640178196996e-21;
+ p = Fma(p, w, -1.685059138182016589e-19);
+ p = Fma(p, w, 1.2858480715256400167e-18);
+ p = Fma(p, w, 1.115787767802518096e-17);
+ p = Fma(p, w, -1.333171662854620906e-16);
+ p = Fma(p, w, 2.0972767875968561637e-17);
+ p = Fma(p, w, 6.6376381343583238325e-15);
+ p = Fma(p, w, -4.0545662729752068639e-14);
+ p = Fma(p, w, -8.1519341976054721522e-14);
+ p = Fma(p, w, 2.6335093153082322977e-12);
+ p = Fma(p, w, -1.2975133253453532498e-11);
+ p = Fma(p, w, -5.4154120542946279317e-11);
+ p = Fma(p, w, 1.051212273321532285e-09);
+ p = Fma(p, w, -4.1126339803469836976e-09);
+ p = Fma(p, w, -2.9070369957882005086e-08);
+ p = Fma(p, w, 4.2347877827932403518e-07);
+ p = Fma(p, w, -1.3654692000834678645e-06);
+ p = Fma(p, w, -1.3882523362786468719e-05);
+ p = Fma(p, w, 0.0001867342080340571352);
+ p = Fma(p, w, -0.00074070253416626697512);
+ p = Fma(p, w, -0.0060336708714301490533);
+ p = Fma(p, w, 0.24015818242558961693);
+ p = Fma(p, w, 1.6536545626831027356);
+ } else if (w < 16.000000) {
+ w = std::sqrt(w) - 3.250000;
+ p = 2.2137376921775787049e-09;
+ p = Fma(p, w, 9.0756561938885390979e-08);
+ p = Fma(p, w, -2.7517406297064545428e-07);
+ p = Fma(p, w, 1.8239629214389227755e-08);
+ p = Fma(p, w, 1.5027403968909827627e-06);
+ p = Fma(p, w, -4.013867526981545969e-06);
+ p = Fma(p, w, 2.9234449089955446044e-06);
+ p = Fma(p, w, 1.2475304481671778723e-05);
+ p = Fma(p, w, -4.7318229009055733981e-05);
+ p = Fma(p, w, 6.8284851459573175448e-05);
+ p = Fma(p, w, 2.4031110387097893999e-05);
+ p = Fma(p, w, -0.0003550375203628474796);
+ p = Fma(p, w, 0.00095328937973738049703);
+ p = Fma(p, w, -0.0016882755560235047313);
+ p = Fma(p, w, 0.0024914420961078508066);
+ p = Fma(p, w, -0.0037512085075692412107);
+ p = Fma(p, w, 0.005370914553590063617);
+ p = Fma(p, w, 1.0052589676941592334);
+ p = Fma(p, w, 3.0838856104922207635);
+ } else {
+ w = std::sqrt(w) - 5.000000;
+ p = -2.7109920616438573243e-11;
+ p = Fma(p, w, -2.5556418169965252055e-10);
+ p = Fma(p, w, 1.5076572693500548083e-09);
+ p = Fma(p, w, -3.7894654401267369937e-09);
+ p = Fma(p, w, 7.6157012080783393804e-09);
+ p = Fma(p, w, -1.4960026627149240478e-08);
+ p = Fma(p, w, 2.9147953450901080826e-08);
+ p = Fma(p, w, -6.7711997758452339498e-08);
+ p = Fma(p, w, 2.2900482228026654717e-07);
+ p = Fma(p, w, -9.9298272942317002539e-07);
+ p = Fma(p, w, 4.5260625972231537039e-06);
+ p = Fma(p, w, -1.9681778105531670567e-05);
+ p = Fma(p, w, 7.5995277030017761139e-05);
+ p = Fma(p, w, -0.00021503011930044477347);
+ p = Fma(p, w, -0.00013871931833623122026);
+ p = Fma(p, w, 1.0103004648645343977);
+ p = Fma(p, w, 4.8499064014085844221);
+ }
+ return p;
+}
+
} // namespace
DistributionMoments ComputeDistributionMoments(
@@ -83,9 +164,44 @@
}
double InverseNormalSurvival(double x) {
- // inv_sf(u) = -sqrt(2) * erfinv(2u-1)
- static constexpr double kSqrt2 = 1.4142135623730950488;
- return -kSqrt2 * absl::random_internal::erfinv(2 * x - 1.0);
+ if (std::isnan(x) || x < 0.0 || x > 1.0) {
+ return std::numeric_limits<double>::quiet_NaN();
+ }
+ if (x == 0.0) return std::numeric_limits<double>::infinity();
+ if (x == 1.0) return -std::numeric_limits<double>::infinity();
+ if (x == 0.5) return 0.0;
+
+ // Use symmetry: inv_sf(1 - u) = -inv_sf(u), with u in (0, 0.5).
+ const bool upper = x < 0.5;
+ const double u = upper ? x : (1.0 - x);
+ double z;
+ if (u >= 1e-15) {
+ // inv_sf(u) = sqrt(2) * erfinv(1 - 2u) = sqrt(2) * ErfInvPoly(w) * (1 - 2u)
+ // where w = -log(1 - (1 - 2u)^2) = -log(4u(1 - u)).
+ // Split at u = 0.25 to avoid -log(4u) - log1p(-u) cancellation near
+ // u = 0.5 and precision loss in t = 1 - 2u (and t * t) as u -> 0.
+ const double t = 1.0 - 2.0 * u;
+ const double w = (u >= 0.25) ? -std::log1p(-t * t)
+ : (-std::log(4.0 * u) - std::log1p(-u));
+ z = kSqrt2 * ErfInvPoly(w) * t;
+ } else {
+ // Giles's third interval is fitted up to w ~= 36 (u ~= 5.8e-17) and loses
+ // accuracy beyond it. For extreme tails (u < 1e-15), start from the
+ // asymptotic expansion and refine with Halley's method against
+ // 0.5 * erfc(z / sqrt(2)).
+ const double log_inv_u = -std::log(u);
+ z = std::sqrt(2.0 * log_inv_u - std::log(4.0 * kPi * log_inv_u));
+ for (int i = 0; i < 6; ++i) {
+ const double sf = 0.5 * std::erfc(z * kSqrt1_2);
+ const double pdf = kInvSqrt2Pi * std::exp(-0.5 * z * z);
+ if (pdf == 0.0) break;
+ const double delta = (sf - u) / pdf;
+ const double step = delta / (1.0 - 0.5 * z * delta);
+ z += step;
+ if (std::fabs(step) <= 1e-15 * z) break;
+ }
+ }
+ return upper ? z : -z;
}
bool Near(absl::string_view msg, double actual, double expected, double bound) {
@@ -113,80 +229,13 @@
// Approximation to inverse of the Error Function in double precision.
// (http://people.maths.ox.ac.uk/gilesm/files/gems_erfinv.pdf)
double erfinv(double x) {
-#if !defined(__EMSCRIPTEN__)
- using std::fma;
-#endif
-
- double w = 0.0;
- double p = 0.0;
- w = -std::log((1.0 - x) * (1.0 + x));
- if (w < 6.250000) {
- w = w - 3.125000;
- p = -3.6444120640178196996e-21;
- p = fma(p, w, -1.685059138182016589e-19);
- p = fma(p, w, 1.2858480715256400167e-18);
- p = fma(p, w, 1.115787767802518096e-17);
- p = fma(p, w, -1.333171662854620906e-16);
- p = fma(p, w, 2.0972767875968561637e-17);
- p = fma(p, w, 6.6376381343583238325e-15);
- p = fma(p, w, -4.0545662729752068639e-14);
- p = fma(p, w, -8.1519341976054721522e-14);
- p = fma(p, w, 2.6335093153082322977e-12);
- p = fma(p, w, -1.2975133253453532498e-11);
- p = fma(p, w, -5.4154120542946279317e-11);
- p = fma(p, w, 1.051212273321532285e-09);
- p = fma(p, w, -4.1126339803469836976e-09);
- p = fma(p, w, -2.9070369957882005086e-08);
- p = fma(p, w, 4.2347877827932403518e-07);
- p = fma(p, w, -1.3654692000834678645e-06);
- p = fma(p, w, -1.3882523362786468719e-05);
- p = fma(p, w, 0.0001867342080340571352);
- p = fma(p, w, -0.00074070253416626697512);
- p = fma(p, w, -0.0060336708714301490533);
- p = fma(p, w, 0.24015818242558961693);
- p = fma(p, w, 1.6536545626831027356);
- } else if (w < 16.000000) {
- w = std::sqrt(w) - 3.250000;
- p = 2.2137376921775787049e-09;
- p = fma(p, w, 9.0756561938885390979e-08);
- p = fma(p, w, -2.7517406297064545428e-07);
- p = fma(p, w, 1.8239629214389227755e-08);
- p = fma(p, w, 1.5027403968909827627e-06);
- p = fma(p, w, -4.013867526981545969e-06);
- p = fma(p, w, 2.9234449089955446044e-06);
- p = fma(p, w, 1.2475304481671778723e-05);
- p = fma(p, w, -4.7318229009055733981e-05);
- p = fma(p, w, 6.8284851459573175448e-05);
- p = fma(p, w, 2.4031110387097893999e-05);
- p = fma(p, w, -0.0003550375203628474796);
- p = fma(p, w, 0.00095328937973738049703);
- p = fma(p, w, -0.0016882755560235047313);
- p = fma(p, w, 0.0024914420961078508066);
- p = fma(p, w, -0.0037512085075692412107);
- p = fma(p, w, 0.005370914553590063617);
- p = fma(p, w, 1.0052589676941592334);
- p = fma(p, w, 3.0838856104922207635);
- } else {
- w = std::sqrt(w) - 5.000000;
- p = -2.7109920616438573243e-11;
- p = fma(p, w, -2.5556418169965252055e-10);
- p = fma(p, w, 1.5076572693500548083e-09);
- p = fma(p, w, -3.7894654401267369937e-09);
- p = fma(p, w, 7.6157012080783393804e-09);
- p = fma(p, w, -1.4960026627149240478e-08);
- p = fma(p, w, 2.9147953450901080826e-08);
- p = fma(p, w, -6.7711997758452339498e-08);
- p = fma(p, w, 2.2900482228026654717e-07);
- p = fma(p, w, -9.9298272942317002539e-07);
- p = fma(p, w, 4.5260625972231537039e-06);
- p = fma(p, w, -1.9681778105531670567e-05);
- p = fma(p, w, 7.5995277030017761139e-05);
- p = fma(p, w, -0.00021503011930044477347);
- p = fma(p, w, -0.00013871931833623122026);
- p = fma(p, w, 1.0103004648645343977);
- p = fma(p, w, 4.8499064014085844221);
+ if (x == 1.0) return std::numeric_limits<double>::infinity();
+ if (x == -1.0) return -std::numeric_limits<double>::infinity();
+ if (!(x > -1.0 && x < 1.0)) {
+ return std::numeric_limits<double>::quiet_NaN();
}
- return p * x;
+ const double w = -std::log((1.0 - x) * (1.0 + x));
+ return ErfInvPoly(w) * x;
}
namespace {
@@ -248,7 +297,7 @@
// https://archive.org/details/DTIC_ADA261511/page/n75
}
-// Direct implementation of AS109, XINBTA(p, q, beta, alpha)
+// Adapted from AS109, XINBTA(p, q, beta, alpha)
// https://www.jstor.org/stable/2346798?read-now=1&seq=4#page_scan_tab_contents
// https://www.jstor.org/stable/2346887?seq=1#page_scan_tab_contents
//
@@ -260,7 +309,7 @@
//
double BetaIncompleteInvImpl(const double p, const double q, const double beta,
const double alpha) {
- if (alpha < 0.5) {
+ if (alpha > 0.5) {
// Inverse Incomplete beta function is symmetrical, return the complement.
return 1. - BetaIncompleteInvImpl(q, p, beta, 1. - alpha);
}
@@ -269,17 +318,20 @@
// Compute the initial estimate.
{
- double r = std::sqrt(-std::log(alpha * alpha));
+ double r = std::sqrt(-2.0 * std::log(alpha));
double y =
- r - fma(r, 0.27061, 2.30753) / fma(r, fma(r, 0.04481, 0.99229), 1.0);
+ r - Fma(r, 0.27061, 2.30753) / Fma(r, Fma(r, 0.04481, 0.99229), 1.0);
if (p > 1. && q > 1.) {
r = (y * y - 3.) / 6.;
double s = 1. / (p + p - 1.);
double t = 1. / (q + q - 1.);
- double h = 2. / s + t;
+ double h = 2. / (s + t);
double w =
- y * std::sqrt(h + r) / h - (t - s) * (r + 5. / 6. - t / (3. * h));
+ y * std::sqrt(h + r) / h - (t - s) * (r + 5. / 6. - 2. / (3. * h));
value = p / (p + q * std::exp(w + w));
+ if (value == 0.0) {
+ value = std::numeric_limits<double>::min();
+ }
} else {
r = q + q;
double t = 1.0 / (9. * q);
@@ -291,6 +343,9 @@
t = (4.0 * p + r - 2.0) / t;
if (t <= 1) {
value = std::exp((std::log(alpha * p) + beta) / p);
+ if (value == 0.0) {
+ value = std::numeric_limits<double>::min();
+ }
} else {
value = 1.0 - 2.0 / (t + 1.0);
}
@@ -298,60 +353,62 @@
}
}
- // Solve for x using a modified newton-raphson method using the function
- // BetaIncomplete.
+ // Solve for x using modified Newton-Raphson iteration over
+ // BetaIncompleteImpl.
{
- value = std::max(value, kErr);
- value = std::min(value, 1.0 - kErr);
+ if (!std::isfinite(value) || value <= 0.0) {
+ value = kErr;
+ } else if (value >= 1.0) {
+ value = 1.0 - kErr;
+ } else if (value < std::numeric_limits<double>::min()) {
+ value = std::numeric_limits<double>::min();
+ }
const double r = 1.0 - p;
const double t = 1.0 - q;
- double y;
- double yprev = 0;
- double sq = 1;
- double prev = 1;
+ double yprev = 0.0;
+ double sq = 1.0;
+ double prev = 1.0;
for (;;) {
- if (value < 0 || value > 1.0) {
- // Error case; value went infinite.
- return std::numeric_limits<double>::infinity();
- } else if (value == 0 || value == 1) {
- y = value;
- } else {
- y = BetaIncompleteImpl(value, p, q, beta);
- if (!std::isfinite(y)) {
- return y;
- }
+ const double cdf = BetaIncompleteImpl(value, p, q, beta);
+ if (!std::isfinite(cdf)) {
+ return cdf;
}
- y = (y - alpha) *
- std::exp(beta + r * std::log(value) + t * std::log(1.0 - value));
- if (y * yprev <= 0) {
- prev = std::max(sq, std::numeric_limits<double>::min());
+ const double err = cdf - alpha;
+ if (err == 0.0) {
+ return value;
+ }
+ double y = err * std::exp(beta + r * std::log(value) +
+ t * std::log(1.0 - value));
+ if (std::isnan(y)) {
+ return y;
+ }
+ if (yprev == 0.0 || std::signbit(y) != std::signbit(yprev)) {
+ prev = sq;
+ }
+ if (std::isinf(y)) {
+ // Avoid infinity when the density underflows in an extreme tail.
+ y = std::copysign(0.5 * prev, err);
+ }
+ const double tol = kErr * value;
+ if (prev <= tol) {
+ return value;
}
double g = 1.0;
for (;;) {
const double adj = g * y;
- const double adj_sq = adj * adj;
- if (adj_sq >= prev) {
- g = g / 3.0;
+ sq = std::fabs(adj);
+ if (sq >= prev) {
+ g /= 3.0;
continue;
}
const double tx = value - adj;
- if (tx < 0 || tx > 1) {
- g = g / 3.0;
+ if (!(tx > 0.0 && tx < 1.0)) {
+ g /= 3.0;
continue;
}
- if (prev < kErr) {
- return value;
- }
- if (y * y < kErr) {
- return value;
- }
- if (tx == value) {
- return value;
- }
- if (tx == 0 || tx == 1) {
- g = g / 3.0;
- continue;
+ if (sq <= tol || tx == value) {
+ return tx;
}
value = tx;
yprev = y;
@@ -371,7 +428,11 @@
double BetaIncomplete(const double x, const double p, const double q) {
// Error cases.
- if (p < 0 || q < 0 || x < 0 || x > 1.0) {
+ if (std::isnan(x) || std::isnan(p) || std::isnan(q)) {
+ return std::numeric_limits<double>::quiet_NaN();
+ }
+ if (p <= 0.0 || q <= 0.0 || std::isinf(p) || std::isinf(q) || x < 0.0 ||
+ x > 1.0) {
return std::numeric_limits<double>::infinity();
}
if (x == 0 || x == 1) {
@@ -379,12 +440,19 @@
}
// ln(Beta(p, q))
double beta = std::lgamma(p) + std::lgamma(q) - std::lgamma(p + q);
+ if (!std::isfinite(beta)) {
+ return std::numeric_limits<double>::quiet_NaN();
+ }
return BetaIncompleteImpl(x, p, q, beta);
}
double BetaIncompleteInv(const double p, const double q, const double alpha) {
// Error cases.
- if (p < 0 || q < 0 || alpha < 0 || alpha > 1.0) {
+ if (std::isnan(p) || std::isnan(q) || std::isnan(alpha)) {
+ return std::numeric_limits<double>::quiet_NaN();
+ }
+ if (p <= 0.0 || q <= 0.0 || std::isinf(p) || std::isinf(q) || alpha < 0.0 ||
+ alpha > 1.0) {
return std::numeric_limits<double>::infinity();
}
if (alpha == 0 || alpha == 1) {
@@ -392,15 +460,24 @@
}
// ln(Beta(p, q))
double beta = std::lgamma(p) + std::lgamma(q) - std::lgamma(p + q);
+ if (!std::isfinite(beta)) {
+ return std::numeric_limits<double>::quiet_NaN();
+ }
return BetaIncompleteInvImpl(p, q, beta, alpha);
}
// Given `num_trials` trials each with probability `p` of success, the
-// probability of no failures is `p^k`. To ensure the probability of a failure
-// is no more than `p_fail`, it must be that `p^k == 1 - p_fail`. This function
-// computes `p` from that equation.
+// probability of no failures is `p^num_trials`. To ensure the probability of
+// at least one failure is no more than `p_fail`, we solve
+// `p^num_trials == 1 - p_fail`.
double RequiredSuccessProbability(const double p_fail, const int num_trials) {
- double p = std::exp(std::log(1.0 - p_fail) / static_cast<double>(num_trials));
+ double p = std::exp(std::log1p(-p_fail) / static_cast<double>(num_trials));
+ if (p_fail > 0.0 && p >= 1.0) {
+ // Prevent rounding to 1.0 when p_fail / num_trials <= 2^-54, which would
+ // cause MaxErrorTolerance(p) to return +inf and make Z-tests pass
+ // unconditionally.
+ p = std::nextafter(1.0, 0.0);
+ }
ABSL_ASSERT(p > 0);
return p;
}
@@ -412,8 +489,10 @@
}
double MaxErrorTolerance(double acceptance_probability) {
- double one_sided_pvalue = 0.5 * (1.0 - acceptance_probability);
- const double max_err = InverseNormalSurvival(one_sided_pvalue);
+ const double max_err =
+ (acceptance_probability <= 0.5)
+ ? kSqrt2 * absl::random_internal::erfinv(acceptance_probability)
+ : InverseNormalSurvival(0.5 * (1.0 - acceptance_probability));
ABSL_ASSERT(max_err > 0);
return max_err;
}
diff --git a/absl/random/internal/distribution_test_util.h b/absl/random/internal/distribution_test_util.h
index 1189340..e6e3544 100644
--- a/absl/random/internal/distribution_test_util.h
+++ b/absl/random/internal/distribution_test_util.h
@@ -22,7 +22,7 @@
#include "absl/strings/string_view.h"
#include "absl/types/span.h"
-// NOTE: The functions in this file are test only, and are should not be used in
+// NOTE: The functions in this file are test only, and should not be used in
// non-test code.
namespace absl {
@@ -55,15 +55,14 @@
// than `p_fail`.
double RequiredSuccessProbability(double p_fail, int num_trials);
-// Computes the maximum distance from the mean tolerable, for Z-Tests that are
-// expected to pass with `acceptance_probability`. Will terminate if the
-// resulting tolerance is zero (due to passing in 0.0 for
-// `acceptance_probability` or rounding errors).
+// Computes the maximum tolerable Z-score magnitude (in standard errors) for
+// two-sided Z-tests expected to pass with `acceptance_probability`. Asserts in
+// debug builds that the resulting tolerance is positive.
//
-// For example,
-// MaxErrorTolerance(0.001) = 0.0
-// MaxErrorTolerance(0.5) = ~0.47
-// MaxErrorTolerance(1.0) = inf
+// For example:
+// MaxErrorTolerance(0.001) ~= 0.00125
+// MaxErrorTolerance(0.5) ~= 0.6745
+// MaxErrorTolerance(1.0) = inf
double MaxErrorTolerance(double acceptance_probability);
// Approximation to inverse of the Error Function in double precision.
@@ -73,7 +72,8 @@
// Beta(p, q) = Gamma(p) * Gamma(q) / Gamma(p+q)
double beta(double p, double q);
-// The inverse of the normal survival function.
+// Inverse of the standard normal survival function: returns z such that
+// P(Z > z) = x for x in [0, 1], or NaN outside [0, 1].
double InverseNormalSurvival(double x);
// Returns whether actual is "near" expected, based on the bound.
@@ -91,19 +91,18 @@
//
double BetaIncomplete(double x, double p, double q);
-// Implements the inverse of the incomplete regularized beta function, AS109,
-// XINBTA.
+// Implements the inverse of the incomplete regularized beta function, adapted
+// from AS109, XINBTA.
// https://www.jstor.org/stable/2346798
// https://www.jstor.org/stable/2346887
//
-// BetaIncompleteInv(p, q, beta, alpha)
+// BetaIncompleteInv(p, q, alpha)
// `p` is beta parameter p, `q` is beta parameter q.
// `alpha` is the value of the lower tail area.
//
-// NOTE: This is a test-only function and, when successful, is only accurate to
-// within ~1e-6 of the actual value; there are some cases where it diverges from
-// the actual value by much more than that. The function uses Newton's method,
-// and thus the runtime is highly variable.
+// NOTE: This is a test-only function using modified Newton-Raphson iteration
+// over BetaIncomplete(), targeting ~1e-13 relative accuracy where the CDF is
+// not flat to double precision.
double BetaIncompleteInv(double p, double q, double alpha);
} // namespace random_internal
diff --git a/absl/random/internal/distribution_test_util_test.cc b/absl/random/internal/distribution_test_util_test.cc
index 1b66879..f614e42 100644
--- a/absl/random/internal/distribution_test_util_test.cc
+++ b/absl/random/internal/distribution_test_util_test.cc
@@ -14,13 +14,30 @@
#include "absl/random/internal/distribution_test_util.h"
+#include <cmath>
+#include <limits>
#include <utility>
#include <vector>
+#include "gmock/gmock.h"
#include "gtest/gtest.h"
namespace {
+using absl::random_internal::BetaIncomplete;
+using absl::random_internal::BetaIncompleteInv;
+using absl::random_internal::erfinv;
+using absl::random_internal::InverseNormalSurvival;
+using absl::random_internal::MaxErrorTolerance;
+using absl::random_internal::RequiredSuccessProbability;
+using ::testing::AllOf;
+using ::testing::DoubleEq;
+using ::testing::DoubleNear;
+using ::testing::Gt;
+using ::testing::IsNan;
+using ::testing::Le;
+using ::testing::Lt;
+
TEST(TestUtil, InverseErf) {
const struct {
const double z;
@@ -193,4 +210,210 @@
m.variance = 100;
EXPECT_NEAR(absl::random_internal::ZScore(-4, m), -10, 1e-12);
}
+
+MATCHER_P4(InvertsBetaIncompleteNear, p, q, expected_alpha, tol, "") {
+ const double actual_alpha = BetaIncomplete(arg, p, q);
+ if (std::fabs(actual_alpha - expected_alpha) <= tol) {
+ return true;
+ }
+ *result_listener << "BetaIncomplete(" << arg << ", " << p << ", " << q
+ << ") = " << actual_alpha << " (expected " << expected_alpha
+ << ", diff " << std::fabs(actual_alpha - expected_alpha)
+ << ")";
+ return false;
+}
+
+MATCHER_P2(HasNormalSurvivalNear, expected_u, rel_tol, "") {
+ constexpr double kSqrt1_2 = 0.70710678118654752440084436210485;
+ const double actual_u = 0.5 * std::erfc(arg * kSqrt1_2);
+ if (std::fabs(actual_u - expected_u) <= rel_tol * expected_u) {
+ return true;
+ }
+ *result_listener << "normal_survival(" << arg << ") = " << actual_u
+ << " (expected " << expected_u << ")";
+ return false;
+}
+
+TEST(BetaTest, BetaIncompleteInvHighPrecision) {
+ // Exact closed-form Beta quantiles should invert to near double precision.
+ EXPECT_THAT(BetaIncompleteInv(2.0, 2.0, 0.028), DoubleNear(0.1, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(2.0, 2.0, 0.216), DoubleNear(0.3, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(2.0, 2.0, 0.784), DoubleNear(0.7, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(2.0, 2.0, 0.972), DoubleNear(0.9, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(1.0, 5.0, 0.67232), DoubleNear(0.2, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(5.0, 2.0, 0.010935), DoubleNear(0.3, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(10.0, 5.0, 0.08978271484375),
+ DoubleNear(0.5, 1e-13));
+
+ // Skewed and symmetric distributions at interior and extreme-tail quantiles.
+ EXPECT_THAT(BetaIncompleteInv(20.0, 5.0, 0.4598773297575791),
+ DoubleNear(0.8, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(30.0, 10.0, 0.2241297491808366),
+ DoubleNear(0.7, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(40.0, 20.0, 0.7001783247477069),
+ DoubleNear(0.7, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(0.5, 0.5, 1e-8),
+ AllOf(DoubleNear(2.46740110027234e-16, 1e-28),
+ InvertsBetaIncompleteNear(0.5, 0.5, 1e-8, 1e-20)));
+ EXPECT_THAT(BetaIncompleteInv(2.0, 5.0, 1e-12),
+ InvertsBetaIncompleteNear(2.0, 5.0, 1e-12, 1e-24));
+ EXPECT_THAT(BetaIncompleteInv(2.0, 5.0, 1.0 - 1e-12),
+ InvertsBetaIncompleteNear(2.0, 5.0, 1.0 - 1e-12, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(5.0, 2.0, 1e-12),
+ InvertsBetaIncompleteNear(5.0, 2.0, 1e-12, 1e-24));
+ EXPECT_THAT(BetaIncompleteInv(5.0, 2.0, 1.0 - 1e-12),
+ InvertsBetaIncompleteNear(5.0, 2.0, 1.0 - 1e-12, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(100.0, 100.0, 1e-12),
+ InvertsBetaIncompleteNear(100.0, 100.0, 1e-12, 1e-24));
+ EXPECT_THAT(BetaIncompleteInv(100.0, 100.0, 1.0 - 1e-12),
+ InvertsBetaIncompleteNear(100.0, 100.0, 1.0 - 1e-12, 1e-13));
+ EXPECT_THAT(BetaIncompleteInv(0.1, 10.0, 1e-10),
+ InvertsBetaIncompleteNear(0.1, 10.0, 1e-10, 1e-22));
+ EXPECT_THAT(BetaIncompleteInv(10.0, 0.1, 1e-10),
+ InvertsBetaIncompleteNear(10.0, 0.1, 1e-10, 1e-22));
+ EXPECT_THAT(BetaIncompleteInv(1000.0, 1000.0, 1e-12),
+ InvertsBetaIncompleteNear(1000.0, 1000.0, 1e-12, 1e-24));
+}
+
+TEST(BetaTest, BetaIncompleteInvExtremeTailAndUnderflowRegressions) {
+ const double kMinNormal = std::numeric_limits<double>::min();
+
+ // Quantiles in [DBL_MIN, DBL_MIN / kErr) where tol = kErr * value < DBL_MIN.
+ EXPECT_THAT(BetaIncompleteInv(0.001, 1.0, 0.5),
+ AllOf(DoubleNear(std::ldexp(1.0, -1000), 1e-312),
+ InvertsBetaIncompleteNear(0.001, 1.0, 0.5, 1e-13)));
+ EXPECT_THAT(BetaIncompleteInv(0.05, 1.0, 1e-15),
+ AllOf(DoubleNear(1e-300, 1e-311),
+ InvertsBetaIncompleteNear(0.05, 1.0, 1e-15, 1e-28)));
+ EXPECT_THAT(BetaIncompleteInv(0.05, 2.0, 1e-15),
+ AllOf(Gt(0.0), Lt(1e-299),
+ InvertsBetaIncompleteNear(0.05, 2.0, 1e-15, 1e-28)));
+ EXPECT_THAT(BetaIncompleteInv(0.05, 0.05, 1e-15),
+ AllOf(Gt(0.0), Lt(1e-293),
+ InvertsBetaIncompleteNear(0.05, 0.05, 1e-15, 1e-28)));
+
+ // Positive initial-estimate underflow branches (both p > 1 && q > 1 and
+ // t <= 1) clamp to DBL_MIN and converge without stalling.
+ EXPECT_THAT(BetaIncompleteInv(1.1, 100.0, 1e-300),
+ AllOf(Gt(0.0), Lt(1e-270),
+ InvertsBetaIncompleteNear(1.1, 100.0, 1e-300, 1e-312)));
+ EXPECT_THAT(BetaIncompleteInv(0.05, 2.0, 1e-20),
+ AllOf(Gt(0.0), Le(kMinNormal)));
+ EXPECT_THAT(BetaIncompleteInv(0.001, 1.0, 0.48),
+ AllOf(Gt(0.0), Le(kMinNormal)));
+
+ // Quantiles pressed against 0 / 1 terminate cleanly (including under x87).
+ EXPECT_THAT(BetaIncompleteInv(1e-5, 1.0, 0.75), AllOf(Gt(0.0), Lt(1e-13)));
+ EXPECT_THAT(BetaIncompleteInv(1.0, 1e-5, 0.25),
+ AllOf(Gt(1.0 - 1e-13), Lt(1.0)));
+}
+
+TEST(BetaTest, InvalidAndBoundaryInputs) {
+ const double kInf = std::numeric_limits<double>::infinity();
+ const double kNan = std::numeric_limits<double>::quiet_NaN();
+
+ EXPECT_THAT(BetaIncomplete(kNan, 1.0, 1.0), IsNan());
+ EXPECT_THAT(BetaIncomplete(0.5, kNan, 1.0), IsNan());
+ EXPECT_THAT(BetaIncomplete(0.5, 1.0, kNan), IsNan());
+ EXPECT_THAT(BetaIncomplete(0.0, kNan, 1.0), IsNan());
+
+ EXPECT_THAT(BetaIncomplete(0.5, 0.0, 1.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(0.5, 1.0, 0.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(0.5, -1.0, 1.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(0.5, 1.0, -1.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(0.5, kInf, 1.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(0.5, 1.0, kInf), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(-0.1, 1.0, 1.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(1.1, 1.0, 1.0), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncomplete(0.0, 0.0, 1.0), DoubleEq(kInf));
+
+ EXPECT_THAT(BetaIncompleteInv(kNan, 1.0, 0.5), IsNan());
+ EXPECT_THAT(BetaIncompleteInv(1.0, kNan, 0.5), IsNan());
+ EXPECT_THAT(BetaIncompleteInv(1.0, 1.0, kNan), IsNan());
+ EXPECT_THAT(BetaIncompleteInv(kNan, 1.0, 0.0), IsNan());
+
+ EXPECT_THAT(BetaIncompleteInv(0.0, 1.0, 0.25), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(1.0, 0.0, 0.25), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(-1.0, 1.0, 0.5), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(1.0, -1.0, 0.5), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(kInf, 1.0, 0.5), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(1.0, kInf, 0.5), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(1.0, 1.0, -0.1), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(1.0, 1.0, 1.1), DoubleEq(kInf));
+ EXPECT_THAT(BetaIncompleteInv(0.0, 1.0, 0.0), DoubleEq(kInf));
+}
+
+TEST(TestUtil, RequiredSuccessProbabilityAndMaxErrorTolerance) {
+ const double kInf = std::numeric_limits<double>::infinity();
+
+ // Small p_fail where naive 1.0 - p_fail loses ~40 bits of precision.
+ const double p_1e12_100 = RequiredSuccessProbability(1e-12, 100);
+ EXPECT_THAT(p_1e12_100, AllOf(Lt(1.0), DoubleNear(1.0 - 1e-14, 1e-15)));
+ EXPECT_THAT(MaxErrorTolerance(p_1e12_100), DoubleNear(7.739358, 1e-4));
+
+ // When p_fail / num_trials <= 2^-54, RequiredSuccessProbability clamps below
+ // 1.0 so MaxErrorTolerance remains finite.
+ const double p_1e12_100k = RequiredSuccessProbability(1e-12, 100000);
+ EXPECT_THAT(p_1e12_100k, Lt(1.0));
+ EXPECT_THAT(MaxErrorTolerance(p_1e12_100k),
+ AllOf(Gt(8.0), Lt(kInf), DoubleNear(8.292361, 1e-4)));
+
+ const double p_1e15_100 = RequiredSuccessProbability(1e-15, 100);
+ EXPECT_THAT(p_1e15_100, Lt(1.0));
+ EXPECT_THAT(MaxErrorTolerance(p_1e15_100),
+ AllOf(Gt(8.0), Lt(kInf), DoubleNear(8.292361, 1e-4)));
+
+ EXPECT_THAT(RequiredSuccessProbability(0.0, 100), DoubleEq(1.0));
+ EXPECT_THAT(MaxErrorTolerance(1.0), DoubleEq(kInf));
+
+ // Very small acceptance probability without 1 - p cancellation near 0.
+ EXPECT_THAT(MaxErrorTolerance(1e-12),
+ DoubleNear(1.2533141373155002e-12, 1e-20));
+}
+
+TEST(TestUtil, InverseNormalSurvivalExtremeTailsAndBoundaries) {
+ const double kInf = std::numeric_limits<double>::infinity();
+ const double kNan = std::numeric_limits<double>::quiet_NaN();
+
+ EXPECT_THAT(InverseNormalSurvival(0.0), DoubleEq(kInf));
+ EXPECT_THAT(InverseNormalSurvival(1.0), DoubleEq(-kInf));
+ EXPECT_THAT(InverseNormalSurvival(0.5), DoubleEq(0.0));
+ EXPECT_THAT(InverseNormalSurvival(-0.1), IsNan());
+ EXPECT_THAT(InverseNormalSurvival(1.1), IsNan());
+ EXPECT_THAT(InverseNormalSurvival(kNan), IsNan());
+
+ EXPECT_THAT(InverseNormalSurvival(1e-10),
+ HasNormalSurvivalNear(1e-10, 1e-12));
+ EXPECT_THAT(InverseNormalSurvival(1e-15),
+ HasNormalSurvivalNear(1e-15, 1e-12));
+ EXPECT_THAT(InverseNormalSurvival(std::ldexp(1.0, -54)),
+ AllOf(DoubleNear(8.292361075813595, 1e-12),
+ HasNormalSurvivalNear(std::ldexp(1.0, -54), 1e-12)));
+ EXPECT_THAT(InverseNormalSurvival(1e-20),
+ HasNormalSurvivalNear(1e-20, 1e-12));
+ EXPECT_THAT(InverseNormalSurvival(1e-50),
+ HasNormalSurvivalNear(1e-50, 1e-12));
+ EXPECT_THAT(InverseNormalSurvival(1e-100),
+ HasNormalSurvivalNear(1e-100, 1e-12));
+ EXPECT_THAT(InverseNormalSurvival(1e-300),
+ HasNormalSurvivalNear(1e-300, 1e-12));
+
+ // Anti-symmetry across 0.5 using an exact dyadic fraction so 1 - u is exact.
+ const double kDyadic = std::ldexp(1.0, -33);
+ EXPECT_THAT(InverseNormalSurvival(1.0 - kDyadic),
+ DoubleEq(-InverseNormalSurvival(kDyadic)));
+}
+
+TEST(TestUtil, InverseErfBoundaries) {
+ const double kInf = std::numeric_limits<double>::infinity();
+ const double kNan = std::numeric_limits<double>::quiet_NaN();
+
+ EXPECT_THAT(erfinv(1.0), DoubleEq(kInf));
+ EXPECT_THAT(erfinv(-1.0), DoubleEq(-kInf));
+ EXPECT_THAT(erfinv(0.0), DoubleEq(0.0));
+ EXPECT_THAT(erfinv(1.5), IsNan());
+ EXPECT_THAT(erfinv(-1.5), IsNan());
+ EXPECT_THAT(erfinv(kNan), IsNan());
+}
+
} // namespace