Fix precision, cancellation, and degenerate-regime bugs in beta_distribution. Extreme or skewed shape parameters previously produced biased, constant, or non-terminating draws: * In Cheng's sampler, `float` intermediates underflowed and cancellation in near-zero `expm1`/`log1p` terms broke acceptance at large parameters and inflated sample means under strong skew. * Degenerate-regime thresholds collapsed valid skewed distributions with one large parameter to a constant, and overflowed `alpha + beta` when both parameters were large. * In Joehnk's sampler (`alpha, beta <= 1`), subnormal `pow` fast paths, log-space cancellation, and `log(u) / alpha` overflow distorted small-shape and bimodal draws. The Joehnk and Cheng rejection steps move out of line into a new `beta_distribution.cc`, reducing compiled sampling `.text` per `(RealType, URBG)` instantiation from ~1.2-3.5 KB to ~0.9-1.5 KB on x86-64 `clang++ -O3` (e.g. 1,407 -> 1,131 B for `<double, absl::BitGen>`), sharing 1,663 B in `beta_distribution.cc` for `float`/`double`. `beta_distribution<float>` now computes in `double` so that `float` Cheng intermediates cannot underflow. `DEGENERATE_SMALL` parameters (both shapes below `2^(min_exponent / 2)`, or one below `1 / max`) now sample `Bernoulli(alpha / (alpha + beta))` instead of a constant 0 or 1. `param_type` gains default arguments matching `beta_distribution()` and stores its mode-specific state (including Cheng's precomputed loop invariants) in a union; each Cheng draw evaluates a single `exp` (or `expm1` for `min(alpha, beta) > 1e4`). Output sequences change; `absl::beta_distribution` does not guarantee cross-release stability. PiperOrigin-RevId: 1022233127
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 253898d..c9ec340 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -232,6 +232,7 @@ "profiling/internal/profile_builder.h" "profiling/internal/sample_recorder.h" "random/bernoulli_distribution.h" + "random/beta_distribution.cc" "random/beta_distribution.h" "random/bit_gen_ref.h" "random/discrete_distribution.cc"
diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 162e328..16a435a 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel
@@ -56,6 +56,7 @@ cc_library( name = "distributions", srcs = [ + "beta_distribution.cc", "discrete_distribution.cc", "gaussian_distribution.cc", ],
diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index cef4ab5..4a16a79 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt
@@ -184,6 +184,7 @@ NAME random_distributions SRCS + "beta_distribution.cc" "discrete_distribution.cc" "gaussian_distribution.cc" HDRS
diff --git a/absl/random/beta_distribution.cc b/absl/random/beta_distribution.cc new file mode 100644 index 0000000..1a98cfd --- /dev/null +++ b/absl/random/beta_distribution.cc
@@ -0,0 +1,315 @@ +// Copyright 2026 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 <algorithm> +#include <cassert> +#include <cmath> +#include <limits> + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { +namespace { + +// Fused multiply-add for the Horner series below. Use std::fma only when +// hardware FMA is available (software libm fma() adds significant call +// overhead); otherwise fall back to `a * b + c`, which differs by only a few +// ULP. The explicit call matters because some toolchains disable +// floating-point contraction, so `a * b + c` is not fused even on FMA hardware. +#if defined(FP_FAST_FMA) || defined(__FP_FAST_FMA) || defined(__FMA__) || \ + (defined(_MSC_VER) && defined(__AVX2__)) || 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 + +#if defined(FP_FAST_FMAL) || defined(__FP_FAST_FMAL) +inline long double Fma(long double a, long double b, long double c) { + return std::fma(a, b, c); +} +#else +inline long double Fma(long double a, long double b, long double c) { + return a * b + c; +} +#endif + +// The truncation bounds of the series below intentionally limit 128-bit +// `long double` to ~2e-20 relative accuracy. + +// Horner evaluation of sum_{k=2}^{14} x^(k-1) / k! = (expm1(x) - x) / x for +// |x| <= 0.25. Truncation error is <= 0.25^14 / 15! < 3e-21. +template <typename T> +T Expm1MinusXOverXImpl(T x) { + T p = T(1.14707455977297247138516979786821057e-11L); // 1 / 14! + p = Fma(p, x, T(1.60590438368216145993923771701549479e-10L)); // 1 / 13! + p = Fma(p, x, T(2.08767569878680989792100903212014323e-9L)); // 1 / 12! + p = Fma(p, x, T(2.50521083854417187750521083854417188e-8L)); // 1 / 11! + p = Fma(p, x, T(2.75573192239858906525573192239858907e-7L)); // 1 / 10! + p = Fma(p, x, T(2.75573192239858906525573192239858907e-6L)); // 1 / 9! + p = Fma(p, x, T(2.48015873015873015873015873015873016e-5L)); // 1 / 8! + p = Fma(p, x, T(1.98412698412698412698412698412698413e-4L)); // 1 / 7! + p = Fma(p, x, T(1.38888888888888888888888888888888889e-3L)); // 1 / 6! + p = Fma(p, x, T(8.33333333333333333333333333333333333e-3L)); // 1 / 5! + p = Fma(p, x, T(4.16666666666666666666666666666666667e-2L)); // 1 / 4! + p = Fma(p, x, T(1.66666666666666666666666666666666667e-1L)); // 1 / 3! + p = Fma(p, x, T(0.5)); // 1 / 2! + return x * p; +} + +// Using w = u / (2 + u), log(1 + u) = 2 * atanh(w), so +// (log1p(u) - u) / u +// = w * (-1 + (2 * w / (2 + u)) * sum_{k=0}^{10} w^(2k) / (2k + 3)). +// For |u| <= 0.25, |w| <= 1/7, so truncation error <= (1/7)^22 / 25 < 2e-20. +template <typename T> +T Log1pMinusXOverXImpl(T u) { + const T denom = T(2) + u; + const T w = u / denom; + const T w2 = w * w; + T p = T(4.34782608695652173913043478260869565e-2L); // 1 / 23 + p = Fma(p, w2, T(4.76190476190476190476190476190476190e-2L)); // 1 / 21 + p = Fma(p, w2, T(5.26315789473684210526315789473684211e-2L)); // 1 / 19 + p = Fma(p, w2, T(5.88235294117647058823529411764705882e-2L)); // 1 / 17 + p = Fma(p, w2, T(6.66666666666666666666666666666666667e-2L)); // 1 / 15 + p = Fma(p, w2, T(7.69230769230769230769230769230769231e-2L)); // 1 / 13 + p = Fma(p, w2, T(9.09090909090909090909090909090909091e-2L)); // 1 / 11 + p = Fma(p, w2, T(1.11111111111111111111111111111111111e-1L)); // 1 / 9 + p = Fma(p, w2, T(1.42857142857142857142857142857142857e-1L)); // 1 / 7 + p = Fma(p, w2, T(2.00000000000000000000000000000000000e-1L)); // 1 / 5 + p = Fma(p, w2, T(3.33333333333333333333333333333333333e-1L)); // 1 / 3 + return w * Fma(T(2) * w / denom, p, T(-1)); +} + +template <typename T> +T BetaJoehnkStepImpl(double u_in, double v_in, T alpha, T beta, T inv_alpha, + T inv_beta, bool try_direct_pow) { + static constexpr T kLn2 = + T(0.693147180559945309417232121458176568L); // log(2) + const T u = static_cast<T>(u_in); + const T v = static_cast<T>(v_in); + + if (try_direct_pow) { + const T x = std::pow(u, inv_alpha); + const T y = std::pow(v, inv_beta); + const T z = x + y; + if (z > T(1)) { + // Reject if and only if `x + y > 1.0`. + return T(-1); + } + if (z < T(1) && (std::min)(x, y) >= (std::numeric_limits<T>::min)()) { + // Only return x / z when both x and y are normal; otherwise fall through + // to the log-transform path to avoid subnormal flush. + return x / z; + } + } + + // Log transform. + // x = log(pow(u, 1 / alpha)), y = log(pow(v, 1 / beta)). + // Since u, v in (0, 1), x and y are negative (possibly -inf for the smaller + // parameter, but never both -inf because param_type routes + // max(alpha, beta) < 2^(min_exponent / 2) to DEGENERATE_SMALL). + const T x = std::log(u) / alpha; + const T y = std::log(v) / beta; + const T m = (std::max)(x, y); + // Reject iff log(e^x + e^y) > 0. Since log(e^x + e^y) <= m + log(2), + // m <= -log(2) guarantees acceptance without computing exp/log1p. + if (m > -kLn2 && m + std::log1p(std::exp(-std::abs(x - y))) > T(0)) { + return T(-1); + } + if (x >= y) { + return T(1) / (T(1) + std::exp(y - x)); + } + const T e = std::exp(x - y); + return e / (T(1) + e); +} + +template <typename T> +T BetaChengStepImpl(double u1, double u2, const BetaChengState<T>& state) { + static constexpr T kLogFour = + T(1.3862943611198906188344642429163531361L); // log(4) + static constexpr T kS = + T(2.6094379124341003746007593332261876L); // 1 + log(5) + static constexpr T kMaxQuarter = (std::numeric_limits<T>::max)() / T(4); + + const T logit = static_cast<T>(std::log(u1 / (1.0 - u1))); + const T v = state.y * logit; + + // Evaluate a single transcendental per draw and derive the other. Only + // large a (> 1e4, where |v| < ~0.5 always) needs expm1(v) itself: there + // a * (expm1(v) - v) and the output's offset from a / (a + b) would lose + // up to a * eps to cancellation. Otherwise exp(v) - 1 has absolute error + // <= 1.5 * eps for |v| <= 0.5 (relative error <= 2.5 * eps beyond), which + // perturbs s, lhs, and u by < 4e-12 and the output by a few ULP. + const bool precise = state.a > T(1e4); + T exp_v; + T expm1_v; + if (precise && std::abs(v) <= T(0.5)) { + expm1_v = std::expm1(v); + exp_v = T(1) + expm1_v; + } else { + exp_v = std::exp(v); + if (!std::isfinite(exp_v)) { + // exp(v) > max implies X = W / (b + W) with W = a * exp(v) > a * max: + // -(a + b) * log1p(u) dominates a * v + logit - t except on target mass + // < 1e-180, so rejecting introduces no measurable bias. + return T(-1); + } + expm1_v = exp_v - T(1); + } + + const T a = state.a; + + // u = (a / (a + b)) * expm1(v). Finite since a_frac <= 0.5, or, when + // a_frac is subnormal, a < min_normal * max (an overflowed u on + // double-double is still rejected below via log1p(u) > kMaxQuarter / b). + T u; + if (state.subnormal_a_frac) { + // a_frac < min_normal implies 1 + r == 1, so a / (a + b) == a / b; avoid + // subnormal rounding in a_frac. + const T b = state.b; + if (std::abs(expm1_v) > kMaxQuarter) { + u = a * (expm1_v / b); + } else { + u = (a * expm1_v) / b; + } + } else { + u = state.a_frac * expm1_v; + } + + // Start the division early so that it overlaps the acceptance test. + const T inv_1pu = T(1) / (T(1) + u); + + // Cheng's squeeze: s = a + (gamma * v - log(4)) - a * exp(v) + // = logit - a * (expm1(v) - v) - log(4), + // since gamma = a + 1 / y and v / y = logit. For large a, evaluate + // a * (expm1(v) - v) without cancellation or v^2 underflow; otherwise the + // direct form's absolute error (<= a * eps) is negligible, and grouping it + // as below shortens the dependency chain after exp(v). + T a_expm1_minus_v = T(0); + T s; + if (precise) { + a_expm1_minus_v = (std::abs(v) <= T(0.25)) + ? (a * v) * Expm1MinusXOverXImpl(v) + : a * (expm1_v - v); + s = logit - a_expm1_minus_v - kLogFour; + } else { + s = (logit - kLogFour + a * (v + T(1))) - a * exp_v; + } + // u1, u2 >= 2^-65, so z >= 2^-195 >> DBL_MIN cannot underflow in double. + const double z = u1 * u1 * u2; + bool accepted = !state.use_algorithm_ba && s + kS >= T(5) * static_cast<T>(z); + if (!accepted) { + const T t = static_cast<T>(std::log(z)); + if (!state.use_algorithm_ba && s >= t) { + accepted = true; + } else { + // Cheng's exact acceptance: + // lhs = -(a + b) * log(1 + u) + a * v + logit - log(4), + // where u = (a / (a + b)) * expm1(v). For large a and |u| <= 0.25, + // rewrite using (a + b) * u == a * expm1(v) to eliminate O(a * v) + // cancellation (otherwise its absolute error a * |v| * eps is < 1e-12): + // -(a + b) * log(1 + u) + a * v + // = -(a * expm1(v)) * ((log1p(u) - u) / u) - a * (expm1(v) - v). + // Note |u| <= 0.25 implies |a * expm1(v)| <= 0.25 * (a + b) <= 0.5 * b. + T lhs; + if (precise && std::abs(u) <= T(0.25)) { + lhs = -(state.a * expm1_v) * Log1pMinusXOverXImpl(u) - a_expm1_minus_v + + logit - kLogFour; + } else { + const T log1p_u = std::log1p(u); + const T b = state.b; + if (log1p_u > kMaxQuarter / b) { + // Exact: (a + b) * log1p(u) - a * v >= b * log1p(u) + a * log(a_frac) + // > max / 4 - max / 97 (as a < max / log(max)) >> logit - t. + return T(-1); + } + lhs = + -(b * log1p_u) * (T(1) + state.r) + state.a * v + logit - kLogFour; + } + accepted = (lhs >= t); + } + } + if (!accepted) { + return T(-1); + } + + // Reconstruct X = W / (b + W) (or 1 - X if inverted), where W = a * exp(v), + // as X = (a_frac + u) / (1 + u). The common paths avoid data-dependent + // branches, which would mispredict on a large fraction of accepted draws. + T res; + const T b_frac = state.b_frac; + if (state.subnormal_a_frac) { + // a_frac < min_normal implies 1 + r == 1, so a / (a + b) == a / b; scale + // by a / b directly to avoid subnormal rounding in a_frac. + if (state.inverted) { + res = b_frac * inv_1pu; + } else if (u > T(1)) { + res = T(1) - b_frac * inv_1pu; + } else if (exp_v > kMaxQuarter) { + res = (state.a * (exp_v / state.b)) * inv_1pu; + } else { + res = ((state.a * exp_v) / state.b) * inv_1pu; + } + } else { + const T a_frac = state.a_frac; + if (precise && std::abs(v) <= T(0.5)) { + // X is a / (a + b) plus a tiny offset; add the offset explicitly so + // that it is not lost to rounding. + const T delta = (b_frac * u) * inv_1pu; + res = state.inverted ? (b_frac - delta) : (a_frac + delta); + } else { + // 1 - X = b_frac / (1 + u) is accurate to 2 ULP. For u > 1 (X > 1/2), + // X = 1 - (1 - X) is then accurate to 1 ULP of 1. + const T one_minus_x = b_frac * inv_1pu; + const T x = (u > T(1)) ? T(1) - one_minus_x : (a_frac * exp_v) * inv_1pu; + res = state.inverted ? one_minus_x : x; + } + } + // u > -1 (since u >= -a_frac), so every branch above is non-negative. + assert(res >= T(0)); + return res; +} + +} // namespace + +double BetaJoehnkStep(double u, double v, double alpha, double beta, + double inv_alpha, double inv_beta, bool try_direct_pow) { + return BetaJoehnkStepImpl(u, v, alpha, beta, inv_alpha, inv_beta, + try_direct_pow); +} + +long double BetaJoehnkStep(double u, double v, long double alpha, + long double beta, long double inv_alpha, + long double inv_beta, bool try_direct_pow) { + return BetaJoehnkStepImpl(u, v, alpha, beta, inv_alpha, inv_beta, + try_direct_pow); +} + +double BetaChengStep(double u1, double u2, + const BetaChengState<double>& state) { + return BetaChengStepImpl(u1, u2, state); +} + +long double BetaChengStep(double u1, double u2, + const BetaChengState<long double>& state) { + return BetaChengStepImpl(u1, u2, state); +} + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/random/beta_distribution.h b/absl/random/beta_distribution.h index b2d0f8f..d4b568d 100644 --- a/absl/random/beta_distribution.h +++ b/absl/random/beta_distribution.h
@@ -15,6 +15,7 @@ #ifndef ABSL_RANDOM_BETA_DISTRIBUTION_H_ #define ABSL_RANDOM_BETA_DISTRIBUTION_H_ +#include <algorithm> #include <cassert> #include <cmath> #include <cstdint> @@ -26,20 +27,76 @@ #include "absl/base/config.h" #include "absl/meta/type_traits.h" +#include "absl/random/bernoulli_distribution.h" #include "absl/random/internal/fast_uniform_bits.h" #include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" namespace absl { ABSL_NAMESPACE_BEGIN +namespace random_internal { + +// Loop-invariant Cheng parameters precomputed by param_type from +// (a, b, y, method, inverted); subnormal_a_frac is a / (a + b) < min_normal. +template <typename CalcType> +struct BetaChengState { + CalcType a; + CalcType b; + CalcType y; + CalcType r; + CalcType a_frac; + CalcType b_frac; + bool use_algorithm_ba; + bool inverted; + bool subnormal_a_frac; +}; + +template <typename CalcType> +inline BetaChengState<CalcType> MakeBetaChengState(CalcType a, CalcType b, + CalcType y, + bool use_algorithm_ba, + bool inverted) { + static constexpr CalcType kMinNormal = (std::numeric_limits<CalcType>::min)(); + const CalcType r = a / b; + const CalcType a_frac = r / (CalcType(1) + r); + const CalcType b_frac = CalcType(1) - a_frac; + return BetaChengState<CalcType>{a, + b, + y, + r, + a_frac, + b_frac, + use_algorithm_ba, + inverted, + a_frac < kMinNormal}; +} + +// Evaluates one rejection-sampling step of Joehnk's algorithm for u, v in +// (0, 1). Returns a variate in [0, 1] on accept or -1 on reject. +double BetaJoehnkStep(double u, double v, double alpha, double beta, + double inv_alpha, double inv_beta, bool try_direct_pow); +long double BetaJoehnkStep(double u, double v, long double alpha, + long double beta, long double inv_alpha, + long double inv_beta, bool try_direct_pow); + +// Evaluates one rejection-sampling step of Cheng's BA/BB algorithm for u1, u2 +// in (0, 1). Returns a variate in [0, 1] on accept or -1 on reject. +double BetaChengStep(double u1, double u2, const BetaChengState<double>& state); +long double BetaChengStep(double u1, double u2, + const BetaChengState<long double>& state); + +} // namespace random_internal // absl::beta_distribution: // Generate a floating-point variate conforming to a Beta distribution: // pdf(x) \propto x^(alpha-1) * (1-x)^(beta-1), -// where the params alpha and beta are both strictly positive real values. +// where the params alpha and beta are positive real values; zero is also +// accepted as a degenerate limit ((0, b) -> 0, (a, 0) -> 1, and +// (0, 0) -> Bernoulli(0.5)). // -// The support is the open interval (0, 1), but the return value might be equal -// to 0 or 1, due to numerical errors when alpha and beta are very different. +// For positive alpha and beta, the support is the open interval (0, 1), but +// the return value might be equal to 0 or 1, due to numerical errors when +// alpha and beta are very different (or both very small). // // Usage note: One usage is that alpha and beta are counts of number of // successes and failures. When the total number of trials are large, consider @@ -56,7 +113,8 @@ public: using distribution_type = beta_distribution; - explicit param_type(result_type alpha, result_type beta) + explicit param_type(result_type alpha = result_type(1), + result_type beta = result_type(1)) : alpha_(alpha), beta_(beta) { assert(alpha >= 0); assert(beta >= 0); @@ -64,59 +122,89 @@ assert(beta <= (std::numeric_limits<result_type>::max)()); if (alpha == 0 || beta == 0) { method_ = DEGENERATE_SMALL; - x_ = (alpha >= beta) ? 1 : 0; + if (alpha == beta) { + inverted_ = false; + x_ = calc_type(0.5); + } else { + inverted_ = (beta < alpha); + x_ = calc_type(0); + } return; } - // a_ = min(beta, alpha), b_ = max(beta, alpha). + // a = min(beta, alpha), b = max(beta, alpha). + calc_type a; + calc_type b; if (beta < alpha) { inverted_ = true; - a_ = beta; - b_ = alpha; + a = static_cast<calc_type>(beta); + b = static_cast<calc_type>(alpha); } else { inverted_ = false; - a_ = alpha; - b_ = beta; - } - if (a_ <= 1 && b_ >= ThresholdForLargeA()) { - method_ = DEGENERATE_SMALL; - x_ = inverted_ ? result_type(1) : result_type(0); - return; + a = static_cast<calc_type>(alpha); + b = static_cast<calc_type>(beta); } // For threshold values, see also: // Evaluation of Beta Generation Algorithms, Ying-Chao Hung, et. al. // February, 2009. - if ((b_ < 1.0 && a_ + b_ <= 1.2) || a_ <= ThresholdForSmallA()) { + if ((b < calc_type(1) && a + b <= calc_type(1.2)) || + a <= static_cast<calc_type>(ThresholdForSmallA())) { // Choose Joehnk over Cheng when it's faster or when Cheng encounters // numerical issues. - method_ = JOEHNK; - a_ = result_type(1) / alpha_; - b_ = result_type(1) / beta_; - if (std::isinf(a_) || std::isinf(b_)) { + const calc_type inv_alpha = + calc_type(1) / static_cast<calc_type>(alpha_); + const calc_type inv_beta = calc_type(1) / static_cast<calc_type>(beta_); + if (b < kMinJoehnkB || std::isinf(inv_alpha) || std::isinf(inv_beta)) { + // Either max(alpha, beta) < 2^(min_exponent / 2), so log(u) / alpha + // and log(v) / beta could both overflow to -inf, or the smaller + // parameter is < 1 / max, so its reciprocal overflows to +inf. In + // both limits X lies in (min_normal, 1 - epsilon) only with + // probability O(min(alpha, beta) * log(max)), so Beta(alpha, beta) + // collapses to Bernoulli(alpha / (alpha + beta)) (same mean); + // rescale by 2^-exp_b to avoid overflow and subnormal underflow. method_ = DEGENERATE_SMALL; - x_ = inverted_ ? result_type(1) : result_type(0); + int exp_b = 0; + std::frexp(b, &exp_b); + const calc_type a_s = std::scalbn(a, -exp_b); + const calc_type b_s = std::scalbn(b, -exp_b); + x_ = a_s / (a_s + b_s); + return; } + method_ = JOEHNK; + joehnk_ = JoehnkState{inv_alpha, inv_beta}; return; } - if (a_ >= ThresholdForLargeA()) { + // If both parameters are at or above ThresholdForLargeA() (since a <= b, + // checking a suffices), the relative standard deviation is + // <= 1 / sqrt(ThresholdForLargeA()) << ULP, so the variate collapses to + // the mean a / (a + b). Rescale by b so a + b never overflows. + if (a >= static_cast<calc_type>(ThresholdForLargeA())) { method_ = DEGENERATE_LARGE; // Note: on PPC for long double, evaluating // `std::numeric_limits::max() / ThresholdForLargeA` results in NaN. - result_type r = a_ / b_; - x_ = (inverted_ ? result_type(1) : r) / (1 + r); + const calc_type r = a / b; + x_ = (inverted_ ? calc_type(1) : r) / (calc_type(1) + r); return; } - x_ = a_ + b_; - log_x_ = std::log(x_); - if (a_ <= 1) { + calc_type y; + if (a <= calc_type(1)) { method_ = CHENG_BA; - y_ = result_type(1) / a_; - gamma_ = a_ + a_; - return; + y = calc_type(1) / a; + } else { + method_ = CHENG_BB; + // Compute y = sqrt((a + b - 2) / (2ab - a - b)) with positive terms so + // a, b -> 1+ cannot cancel, rescaling when 2ab could overflow. + if (b < kMaxDirectChengB) { + const calc_type am1 = a - calc_type(1); + const calc_type bm1 = b - calc_type(1); + y = std::sqrt((am1 + bm1) / (am1 * b + a * bm1)); + } else { + const calc_type fa = (a - calc_type(1)) / a; + const calc_type fb = (b - calc_type(1)) / b; + y = std::sqrt((fa / b + fb / a) / (fa + fb)); + } } - method_ = CHENG_BB; - result_type r = (a_ - 1) / (b_ - 1); - y_ = std::sqrt((1 + r) / (b_ * r * 2 - r + 1)); - gamma_ = a_ + result_type(1) / y_; + cheng_ = random_internal::MakeBetaChengState(a, b, y, method_ == CHENG_BA, + inverted_); } result_type alpha() const { return alpha_; } @@ -133,6 +221,9 @@ private: friend class beta_distribution; + using calc_type = + std::conditional_t<std::is_same_v<RealType, float>, double, RealType>; + #ifdef _MSC_VER // MSVC does not have constexpr implementations for std::log and std::exp // so they are computed at runtime. @@ -142,7 +233,7 @@ #endif // The threshold for whether std::exp(1/a) is finite. - // Note that this value is quite large, and a smaller a_ is NOT abnormal. + // Note that this value is quite large, and a smaller a is NOT abnormal. static ABSL_RANDOM_INTERNAL_LOG_EXP_CONSTEXPR result_type ThresholdForSmallA() { return result_type(1) / @@ -164,6 +255,36 @@ // template specialization below. static constexpr result_type ThresholdPadding() { return 0; } + // Exact 2^exp for normal radix-2 exponents (std::ldexp is not constexpr + // before C++23). Steps by 2^+-32 so large long double exponents fold fast. + static constexpr calc_type Pow2(int exp) { + constexpr calc_type kTwo32 = calc_type(uint64_t{1} << 32); + constexpr calc_type kTwoM32 = calc_type(1) / kTwo32; + calc_type x = calc_type(1); + while (exp >= 32) { + x *= kTwo32; + exp -= 32; + } + while (exp <= -32) { + x *= kTwoM32; + exp += 32; + } + while (exp > 0) { + x *= calc_type(2); + --exp; + } + while (exp < 0) { + x *= calc_type(0.5); + ++exp; + } + return x; + } + + static constexpr calc_type kMinJoehnkB = + Pow2(std::numeric_limits<calc_type>::min_exponent / 2); + static constexpr calc_type kMaxDirectChengB = + Pow2(std::numeric_limits<calc_type>::max_exponent / 2 - 1); + enum Method { JOEHNK, // Uses algorithm Joehnk CHENG_BA, // Uses algorithm BA in Cheng @@ -176,26 +297,32 @@ // Zechner, Heinz, and Ernst Stadlober. Generating beta variates via // patchwork rejection. Computing 50.1 (1993): 1-18. - DEGENERATE_SMALL, // a_ is abnormally small. - DEGENERATE_LARGE, // a_ is abnormally large. + DEGENERATE_SMALL, // a is abnormally small. + DEGENERATE_LARGE, // a is abnormally large. + }; + + struct JoehnkState { + calc_type inv_alpha; + calc_type inv_beta; }; result_type alpha_; result_type beta_; - - result_type a_{}; // the smaller of {alpha, beta}, or 1.0/alpha_ in JOEHNK - result_type b_{}; // the larger of {alpha, beta}, or 1.0/beta_ in JOEHNK - result_type x_{}; // alpha + beta, or the result in degenerate cases - result_type log_x_{}; // log(x_) - result_type y_{}; // "beta" in Cheng - result_type gamma_{}; // "gamma" in Cheng - Method method_{}; - - // Placing this last for optimal alignment. - // Whether alpha_ != a_, i.e. true iff alpha_ > beta_. + // Whether alpha_ != min(alpha_, beta_), i.e. true iff alpha_ > beta_. bool inverted_{}; + union { + // Bernoulli p in DEGENERATE_SMALL, or mean in DEGENERATE_LARGE. + calc_type x_{}; + // 1 / alpha_ and 1 / beta_ in JOEHNK. + JoehnkState joehnk_; + // Loop-invariant Cheng state (including Cheng's "beta" as cheng_.y) in + // CHENG_BA and CHENG_BB, precomputed once so operator() performs no + // divisions before sampling. + random_internal::BetaChengState<calc_type> cheng_; + }; + static_assert(std::is_floating_point_v<RealType>, "Class-template absl::beta_distribution<> must be " "parameterized using a floating-point type."); @@ -239,6 +366,8 @@ } private: + using calc_type = typename param_type::calc_type; + template <typename URBG> result_type AlgorithmJoehnk(URBG& g, // NOLINT(runtime/references) const param_type& p); @@ -250,13 +379,15 @@ template <typename URBG> result_type DegenerateCase(URBG& g, // NOLINT(runtime/references) const param_type& p) { - if (p.method_ == param_type::DEGENERATE_SMALL && p.alpha_ == p.beta_) { - // Returns 0 or 1 with equal probability. - random_internal::FastUniformBits<uint8_t> fast_u8; - return static_cast<result_type>((fast_u8(g) & 0x10) != - 0); // pick any single bit. + if (p.method_ == param_type::DEGENERATE_SMALL) { + const double prob = static_cast<double>(p.x_); + if (prob == 0.0) { + return p.inverted_ ? result_type(1) : result_type(0); + } + const bool hit = absl::bernoulli_distribution(prob)(g); + return (hit != p.inverted_) ? result_type(1) : result_type(0); } - return p.x_; + return static_cast<result_type>(p.x_); } param_type param_; @@ -281,53 +412,30 @@ const param_type& p) { using random_internal::GeneratePositiveTag; using random_internal::GenerateRealFromBits; - using real_type = - std::conditional_t<std::is_same_v<RealType, float>, float, double>; // Based on Joehnk, M. D. Erzeugung von betaverteilten und gammaverteilten // Zufallszahlen. Metrika 8.1 (1964): 5-15. // This method is described in Knuth, Vol 2 (Third Edition), pp 134. + // For exponents above 500, pow(u, 1 / alpha) is subnormal for u < 0.24 + // (i.e., on > 24% of draws), which falls back to log space anyway. + static constexpr calc_type kMaxDirectPowExponent = calc_type(500); + const bool try_direct_pow = !std::is_same_v<float, result_type> && + p.joehnk_.inv_alpha >= calc_type(1) && + p.joehnk_.inv_beta >= calc_type(1) && + p.joehnk_.inv_alpha <= kMaxDirectPowExponent && + p.joehnk_.inv_beta <= kMaxDirectPowExponent; - result_type u, v, x, y, z; for (;;) { - u = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( - fast_u64_(g)); - v = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( - fast_u64_(g)); - - // Direct method. std::pow is slow for float, so rely on the optimizer to - // remove the std::pow() path for that case. - if (!std::is_same_v<float, result_type>) { - x = std::pow(u, p.a_); - y = std::pow(v, p.b_); - z = x + y; - if (z > 1) { - // Reject if and only if `x + y > 1.0` - continue; - } - if (z > 0) { - // When both alpha and beta are small, x and y are both close to 0, so - // divide by (x+y) directly may result in nan. - return x / z; - } + const double u = + GenerateRealFromBits<double, GeneratePositiveTag, false>(fast_u64_(g)); + const double v = + GenerateRealFromBits<double, GeneratePositiveTag, false>(fast_u64_(g)); + const calc_type res = random_internal::BetaJoehnkStep( + u, v, static_cast<calc_type>(p.alpha_), static_cast<calc_type>(p.beta_), + p.joehnk_.inv_alpha, p.joehnk_.inv_beta, try_direct_pow); + if (res >= calc_type(0)) { + return static_cast<result_type>(res); } - - // Log transform. - // x = log( pow(u, p.a_) ), y = log( pow(v, p.b_) ) - // since u, v <= 1.0, x, y < 0. - x = std::log(u) * p.a_; - y = std::log(v) * p.b_; - if (!std::isfinite(x) || !std::isfinite(y)) { - continue; - } - // z = log( pow(u, a) + pow(v, b) ) - z = x > y ? (x + std::log(1 + std::exp(y - x))) - : (y + std::log(1 + std::exp(x - y))); - // Reject iff log(x+y) > 0. - if (z > 0) { - continue; - } - return std::exp(x - z); } } @@ -339,43 +447,20 @@ const param_type& p) { using random_internal::GeneratePositiveTag; using random_internal::GenerateRealFromBits; - using real_type = - std::conditional_t<std::is_same_v<RealType, float>, float, double>; // Based on Cheng, Russell CH. Generating beta variates with nonintegral // shape parameters. Communications of the ACM 21.4 (1978): 317-322. // (https://dl.acm.org/citation.cfm?id=359482). - static constexpr result_type kLogFour = - result_type(1.3862943611198906188344642429163531361); // log(4) - static constexpr result_type kS = - result_type(2.6094379124341003746007593332261876); // 1+log(5) - - const bool use_algorithm_ba = (p.method_ == param_type::CHENG_BA); - result_type u1, u2, v, w, z, r, s, t, bw_inv, lhs; for (;;) { - u1 = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( - fast_u64_(g)); - u2 = GenerateRealFromBits<real_type, GeneratePositiveTag, false>( - fast_u64_(g)); - v = p.y_ * std::log(u1 / (1 - u1)); - w = p.a_ * std::exp(v); - bw_inv = result_type(1) / (p.b_ + w); - r = p.gamma_ * v - kLogFour; - s = p.a_ + r - w; - z = u1 * u1 * u2; - if (!use_algorithm_ba && s + kS >= 5 * z) { - break; - } - t = std::log(z); - if (!use_algorithm_ba && s >= t) { - break; - } - lhs = p.x_ * (p.log_x_ + std::log(bw_inv)) + r; - if (lhs >= t) { - break; + const double u1 = + GenerateRealFromBits<double, GeneratePositiveTag, false>(fast_u64_(g)); + const double u2 = + GenerateRealFromBits<double, GeneratePositiveTag, false>(fast_u64_(g)); + const calc_type res = random_internal::BetaChengStep(u1, u2, p.cheng_); + if (res >= calc_type(0)) { + return (std::min)(static_cast<result_type>(res), result_type(1)); } } - return p.inverted_ ? (1 - w * bw_inv) : w * bw_inv; } template <typename RealType>
diff --git a/absl/random/beta_distribution_test.cc b/absl/random/beta_distribution_test.cc index b44bde0..7bed185 100644 --- a/absl/random/beta_distribution_test.cc +++ b/absl/random/beta_distribution_test.cc
@@ -20,8 +20,10 @@ #include <cstddef> #include <cstdint> #include <cstdlib> +#include <initializer_list> #include <iterator> #include <limits> +#include <ostream> #include <random> #include <sstream> #include <string> @@ -46,6 +48,15 @@ namespace { +using ::testing::AllOf; +using ::testing::DoubleEq; +using ::testing::DoubleNear; +using ::testing::Eq; +using ::testing::FloatEq; +using ::testing::Ge; +using ::testing::Le; +using ::testing::Pair; + template <typename IntType> class BetaDistributionInterfaceTest : public ::testing::Test {}; @@ -71,6 +82,17 @@ ::testing::Types<float, double>>; TYPED_TEST_SUITE(BetaDistributionInterfaceTest, RealTypes); +TYPED_TEST(BetaDistributionInterfaceTest, DefaultParamType) { + using Dist = absl::beta_distribution<TypeParam>; + using param_type = typename Dist::param_type; + static_assert(std::is_trivially_copyable_v<param_type>); + static_assert(std::is_trivially_destructible_v<param_type>); + EXPECT_THAT(param_type(), Eq(param_type(TypeParam(1), TypeParam(1)))); + EXPECT_THAT(param_type(TypeParam(2)), + Eq(param_type(TypeParam(2), TypeParam(1)))); + EXPECT_THAT(Dist().param(), Eq(param_type())); +} + TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { // The threshold for whether std::exp(1/a) is finite. const TypeParam kSmallA = @@ -84,14 +106,23 @@ 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), + 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(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)), // @@ -215,7 +246,9 @@ for (TypeParam beta : kLargeValues) { absl::beta_distribution<TypeParam> d(alpha, beta); for (int i = 0; i < kCount; ++i) { - EXPECT_EQ(d(rng), 0.0); + // Beta(epsilon, max) can rightly yield a subnormal from the Gamma + // tail, so only require the sample to be below min_normal. + EXPECT_LT(d(rng), (std::numeric_limits<TypeParam>::min)()); } } } @@ -509,7 +542,7 @@ 998340000, 619030004, 500000001, 999990000, 996280000, 500000001, 844740004, 847210001, 999970000, 872320000, 585480007, 933280000, 869080042, 647670031, 528240004, - 969980004, 626050008, 915930002, 833440033, 878040015)); + 969980004, 626050008, 915930002, 833450033, 878040015)); } urbg.reset(); @@ -583,7 +616,7 @@ // u=0.499, v=0.5 absl::beta_distribution<double> dist(1e-4, 1e-4); double a = dist(urbg); - EXPECT_EQ(a, 2.0202860861567108529e-09); + EXPECT_EQ(a, 2.0202860861579454e-09); EXPECT_EQ(2, urbg.invocations()); } @@ -617,6 +650,488 @@ } } +struct SampleMoments { + double mean; + double stddev; + int zeros; + int ones; + int total; +}; + +void PrintTo(const SampleMoments& m, std::ostream* os) { + *os << "{mean=" << absl::StreamFormat("%.17g", m.mean) + << ", stddev=" << absl::StreamFormat("%.17g", m.stddev) + << ", zeros=" << m.zeros << ", ones=" << m.ones << ", total=" << m.total + << "}"; +} + +template <typename RealType> +SampleMoments SampleScaledMoments(RealType alpha, RealType beta, double scale, + int samples) { + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + absl::beta_distribution<RealType> dist(alpha, beta); + std::vector<double> values; + values.reserve(static_cast<size_t>(samples)); + int zeros = 0; + int ones = 0; + double sum = 0.0; + for (int i = 0; i < samples; ++i) { + const RealType sample = dist(rng); + EXPECT_TRUE(std::isfinite(sample)); + EXPECT_GE(sample, RealType(0)); + EXPECT_LE(sample, RealType(1)); + if (sample == RealType(0)) ++zeros; + if (sample == RealType(1)) ++ones; + const double scaled = static_cast<double>(sample) * scale; + values.push_back(scaled); + sum += scaled; + } + const double mean = sum / samples; + double sq_diff_sum = 0.0; + for (double v : values) { + const double d = v - mean; + sq_diff_sum += d * d; + } + const double stddev = std::sqrt(sq_diff_sum / (samples - 1)); + return SampleMoments{mean, stddev, zeros, ones, samples}; +} + +template <typename RealType> +RealType SampleBetaWithBits(RealType alpha, RealType beta, + std::initializer_list<uint64_t> bits) { + absl::random_internal::sequence_urbg urbg(bits); + absl::beta_distribution<RealType> dist(alpha, beta); + return dist(urbg); +} + +template <typename RealType> +std::pair<RealType, size_t> SampleBetaWithBitsAndCount( + RealType alpha, RealType beta, std::initializer_list<uint64_t> bits) { + absl::random_internal::sequence_urbg urbg(bits); + absl::beta_distribution<RealType> dist(alpha, beta); + const RealType sample = dist(urbg); + return {sample, urbg.invocations()}; +} + +MATCHER_P4(HasMomentsNear, expected_mean, mean_tol, expected_stddev, stddev_tol, + absl::StrFormat("has mean within %.3g of %.6g and stddev within " + "%.3g of %.6g", + mean_tol, expected_mean, stddev_tol, + expected_stddev)) { + const double mean_err = std::abs(arg.mean - expected_mean); + const double stddev_err = std::abs(arg.stddev - expected_stddev); + if (mean_err <= mean_tol && stddev_err <= stddev_tol) { + return true; + } + *result_listener << "mean error " << mean_err << " (tol " << mean_tol + << "), stddev error " << stddev_err << " (tol " << stddev_tol + << ")"; + return false; +} + +MATCHER_P2(IsBernoulliNear, expected_p, tol, + absl::StrFormat("contains only 0/1 samples with mean within %.3g " + "of %.6g", + tol, expected_p)) { + if (arg.zeros + arg.ones != arg.total) { + *result_listener << "has " << (arg.total - arg.zeros - arg.ones) + << " non-binary samples"; + return false; + } + const double err = std::abs(arg.mean - expected_p); + if (err <= tol) { + return true; + } + *result_listener << "mean error " << err << " (tol " << tol << ")"; + return false; +} + +TEST(BetaDistributionTest, HighSkewMeanAccuracy) { + constexpr int kSamples = 20000; + + EXPECT_THAT(SampleScaledMoments<float>(0.5f, 1e8f, 1e8, kSamples), + HasMomentsNear(0.5, 0.05, std::sqrt(0.5), 0.06)); + EXPECT_THAT(SampleScaledMoments<double>(0.5, 1e18, 1e18, kSamples), + HasMomentsNear(0.5, 0.05, std::sqrt(0.5), 0.06)); + EXPECT_THAT(SampleScaledMoments<double>(2.0, 1e20, 1e20, kSamples), + HasMomentsNear(2.0, 0.1, std::sqrt(2.0), 0.08)); +} + +TEST(BetaDistributionTest, HighAlphaUpperTailRoundsToOneWithoutBias) { + // True 1 - X mean is 5e-19 and P(1 - X > 2^-54) < 1e-20, so every sample + // must round to exactly 1.0 rather than suffering cancellation bias. + EXPECT_THAT(SampleScaledMoments<double>(1e18, 0.5, 1.0, 20000), + IsBernoulliNear(1.0, 0.0)); +} + +TEST(BetaDistributionTest, LargeBetaNearMaxPreservesMeanRatio) { + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + const double max_val = (std::numeric_limits<double>::max)(); + const double alpha = 1e305; + const double r = alpha / max_val; + const double expected_ratio = r / (1.0 + r); + absl::beta_distribution<double> dist(alpha, max_val); + absl::beta_distribution<double> inv_dist(max_val, alpha); + + EXPECT_THAT(dist(rng), DoubleNear(expected_ratio, expected_ratio * 1e-12)); + EXPECT_THAT(1.0 - inv_dist(rng), + DoubleNear(expected_ratio, expected_ratio * 1e-12)); +} + +TEST(BetaDistributionTest, ChengLargeSymmetricPrecision) { + constexpr int kSamples = 20000; + // True stddev of Beta(a, a) is 1 / sqrt(4 * (2a + 1)). A 5% tolerance + // catches both the +28.3% Logistic inflation from s = (a + r) - w + // cancellation and discretization spikes from exp(v) around 1.0. + const double sigma_1e22 = 1.0 / std::sqrt(4.0 * 2e22); + const double sigma_1e30 = 1.0 / std::sqrt(4.0 * 2e30); + const double sigma_1e9 = 1.0 / std::sqrt(4.0 * 2e9); + + EXPECT_THAT( + SampleScaledMoments<double>(1e22, 1e22, 1.0, kSamples), + HasMomentsNear(0.5, sigma_1e22 * 0.05, sigma_1e22, sigma_1e22 * 0.05)); + EXPECT_THAT( + SampleScaledMoments<double>(1e30, 1e30, 1.0, kSamples), + HasMomentsNear(0.5, sigma_1e30 * 0.05, sigma_1e30, sigma_1e30 * 0.05)); + EXPECT_THAT( + SampleScaledMoments<float>(1e9f, 1e9f, 1.0, kSamples), + HasMomentsNear(0.5, sigma_1e9 * 0.05, sigma_1e9, sigma_1e9 * 0.05)); +} + +TEST(BetaDistributionTest, ChengFloatProductUnderflowDoesNotFalseAccept) { + // Verify float ChengBB computes t = log(u1*u1*u2) in double rather than + // float: for u1 = u2 = 2^-65, float(u1*u1*u2) flushes to 0.0f (t = -inf) + // and would falsely accept on the first draw (2 calls). The second draw + // (u1 = 0.5, so v = 0) is accepted by the squeeze and returns exactly 0.5. + EXPECT_THAT(SampleBetaWithBitsAndCount<float>( + 5.0f, 5.0f, + {0ull, 0ull, 0x8000000000000000ull, 0x4000000000000000ull}), + Pair(FloatEq(0.5f), 4u)); +} + +TEST(BetaDistributionTest, SkewedHugeBetaRetainsVariance) { + constexpr int kSamples = 20000; + // For b >= ThresholdForLargeA() and moderate a, b * Beta(a, b) ~ Gamma(a, 1) + // with mean a and stddev sqrt(a), rather than collapsing to a constant. + EXPECT_THAT(SampleScaledMoments<double>(2.0, 3e305, 3e305, kSamples), + HasMomentsNear(2.0, 0.06, std::sqrt(2.0), 0.06)); + EXPECT_THAT(SampleScaledMoments<double>(1.0, 3e305, 3e305, kSamples), + HasMomentsNear(1.0, 0.05, 1.0, 0.05)); + EXPECT_THAT(SampleScaledMoments<double>(0.5, 3e305, 3e305, kSamples), + HasMomentsNear(0.5, 0.04, std::sqrt(0.5), 0.05)); + EXPECT_THAT(SampleScaledMoments<float>(2.0f, 1e37f, 1e37, kSamples), + HasMomentsNear(2.0, 0.06, std::sqrt(2.0), 0.06)); + // Both sides of the Cheng BB y-formula overflow switch at b = 2^511. + const double kChengSplit = std::ldexp(1.0, 511); + const double kBelowSplit = std::nextafter(kChengSplit, 0.0); + EXPECT_THAT( + SampleScaledMoments<double>(2.0, kBelowSplit, kBelowSplit, kSamples), + HasMomentsNear(2.0, 0.06, std::sqrt(2.0), 0.06)); + EXPECT_THAT( + SampleScaledMoments<double>(2.0, kChengSplit, kChengSplit, kSamples), + HasMomentsNear(2.0, 0.06, std::sqrt(2.0), 0.06)); + // Parameters just above 1 enter Cheng BB with a - 1 = b - 1 = eps and follow + // Uniform(0, 1) (mean 1/2, stddev 1 / sqrt(12)) without y cancellation. + const double kAboveOne = std::nextafter(1.0, 2.0); + const float kAboveOneF = std::nextafter(1.0f, 2.0f); + EXPECT_THAT(SampleScaledMoments<double>(kAboveOne, kAboveOne, 1.0, kSamples), + HasMomentsNear(0.5, 0.01, 1.0 / std::sqrt(12.0), 0.01)); + EXPECT_THAT(SampleScaledMoments<float>(kAboveOneF, kAboveOneF, 1.0, kSamples), + HasMomentsNear(0.5, 0.01, 1.0 / std::sqrt(12.0), 0.01)); +} + +TEST(BetaDistributionTest, SubnormalMeanRatioRetainsGammaShape) { + constexpr int kSamples = 20000; + constexpr double kDblMax = (std::numeric_limits<double>::max)(); + constexpr float kFltMax = (std::numeric_limits<float>::max)(); + // a / (a + b) < DBL_MIN, so samples are subnormal; max * Beta(a, max) must + // still follow Gamma(a, 1) rather than flushing or quantizing a / (a + b). + EXPECT_THAT(SampleScaledMoments<double>(0.5, kDblMax, kDblMax, kSamples), + HasMomentsNear(0.5, 0.04, std::sqrt(0.5), 0.05)); + EXPECT_THAT(SampleScaledMoments<double>(3.0, kDblMax, kDblMax, kSamples), + HasMomentsNear(3.0, 0.08, std::sqrt(3.0), 0.08)); + EXPECT_THAT(SampleScaledMoments<float>(0.5f, kFltMax, kFltMax, kSamples), + HasMomentsNear(0.5, 0.04, std::sqrt(0.5), 0.05)); +} + +TEST(BetaDistributionTest, ZeroParametersSampleDegenerateLimits) { + constexpr int kSamples = 20000; + EXPECT_THAT(SampleScaledMoments<double>(0.0, 1.0, 1.0, kSamples), + IsBernoulliNear(0.0, 0.0)); + EXPECT_THAT(SampleScaledMoments<double>(1.0, 0.0, 1.0, kSamples), + IsBernoulliNear(1.0, 0.0)); + EXPECT_THAT(SampleScaledMoments<double>(0.0, 0.0, 1.0, kSamples), + IsBernoulliNear(0.5, 0.015)); +} + +TEST(BetaDistributionTest, JoehnkSubnormalPowUsesLogSpace) { + // Subnormal quantization on the direct pow path (1/alpha = 400 <= 500): + // u^400 == v^400 == DBL_TRUE_MIN, so direct x / (x + y) would return 0.5 + // instead of ~1/3 from log space. + EXPECT_THAT( + SampleBetaWithBits<double>( + 0.0025, 0.0025, {0x27bf0fef76a3ce00ull, 0x27d0b5a68fa3ee00ull}), + DoubleNear(0.33333333333332027, 1e-12)); + + // Direct-pow bypass for large exponents (1/alpha = 1000 > 500): + // u^1000 == 0.0 and v^1000 == DBL_TRUE_MIN, so log space yields ~0.30098. + EXPECT_THAT(SampleBetaWithBits<double>( + 0.001, 0.001, {0x7978d4fdf3b645a2ull, 0x79930be0ded288ceull}), + DoubleNear(0.30097958588233603, 1e-12)); +} + +TEST(BetaDistributionTest, JoehnkEqualDrawsAvoidLogCancellation) { + // x - z cancellation: equal draws u == v == 0.5 must return 0.5 rather than + // 1.0 when |x| exceeds float/double precision relative to log(2). + EXPECT_THAT(SampleBetaWithBits<float>( + 1e-7f, 1e-7f, {0x8000000000000000ull, 0x8000000000000000ull}), + FloatEq(0.5f)); + EXPECT_THAT(SampleBetaWithBits<double>( + 1e-16, 1e-16, {0x8000000000000000ull, 0x8000000000000000ull}), + DoubleEq(0.5)); +} + +TEST(BetaDistributionTest, JoehnkSkewedParametersPreserveMoments) { + // Skewed Joehnk: pow(v, 1/1e18) rounds to 1.0, so the direct path must not + // accept x + y <= 1.0. Scaled by 1e18, mean is 0.001 and stddev sqrt(0.001). + EXPECT_THAT(SampleScaledMoments<double>(0.001, 1e18, 1e18, 50000), + HasMomentsNear(0.001, 8e-4, std::sqrt(0.001), 0.03)); +} + +TEST(BetaDistributionTest, TinyParametersNearUnderflowFollowBernoulliRatio) { + constexpr int kSamples = 20000; + + // Near-underflow tiny parameters: no -inf rejection truncation bias (true + // mean 1/11 ~ 0.0909, not 0.1374). + EXPECT_THAT(SampleScaledMoments<double>(6e-309, 6e-308, 1.0, kSamples), + IsBernoulliNear(1.0 / 11.0, 0.01)); + + // Unequal DEGENERATE_SMALL parameters follow Bernoulli(alpha / (alpha+beta)) + // rather than collapsing to deterministic 0.0 / 1.0. + EXPECT_THAT(SampleScaledMoments<double>(1e-310, 2e-310, 1.0, kSamples), + IsBernoulliNear(1.0 / 3.0, 0.015)); + EXPECT_THAT(SampleScaledMoments<double>(2e-310, 1e-310, 1.0, kSamples), + IsBernoulliNear(2.0 / 3.0, 0.015)); +} + +TEST(BetaDistributionTest, LongDoubleSmoke) { + if (absl::numeric_internal::IsDoubleDouble()) { + GTEST_SKIP() << "Skipping long double test on double-double platforms"; + } + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + const auto draw = [&rng](long double a, long double b) { + absl::beta_distribution<long double> dist(a, b); + return dist(rng); + }; + const auto valid_unit = AllOf(Ge(0.0L), Le(1.0L)); + EXPECT_THAT(draw(0.1L, 0.2L), valid_unit); + EXPECT_THAT(draw(0.5L, 2.0L), valid_unit); + EXPECT_THAT(draw(2.0L, 5.0L), valid_unit); + EXPECT_THAT(static_cast<double>(draw(1e20L, 1e20L)), DoubleNear(0.5, 1e-8)); + // Highly skewed Cheng BB: 1e30 * Beta(2, 1e30) ~ Gamma(2, 1). + EXPECT_THAT(SampleScaledMoments<long double>(2.0L, 1e30L, 1e30, 20000), + HasMomentsNear(2.0, 0.06, std::sqrt(2.0), 0.06)); + if constexpr (std::numeric_limits<long double>::min_exponent <= -16381) { + // Non-zero long double Bernoulli probability that rounds to 0.0 in double + // must return the endpoint without consuming a URBG draw. + const long double tiny = std::ldexp(1.0L, -11000); + const long double larger = std::ldexp(1.0L, -9000); + EXPECT_THAT(SampleBetaWithBitsAndCount<long double>(tiny, larger, {0ull}), + Pair(Eq(0.0L), 0u)); + EXPECT_THAT(SampleBetaWithBitsAndCount<long double>(larger, tiny, {0ull}), + Pair(Eq(1.0L), 0u)); + } +} + +// Direct tests of the out-of-line rejection steps. Cheng states below use the +// real (a, b, y) for the parameters unless noted; u1 is chosen to hit a +// specific v = y * log(u1 / (1 - u1)). +using ::absl::random_internal::BetaChengState; +using ::absl::random_internal::BetaChengStep; +using ::absl::random_internal::BetaJoehnkStep; +using ::absl::random_internal::MakeBetaChengState; + +// Returns u1 such that y * log(u1 / (1 - u1)) ~= v. +double U1ForV(const BetaChengState<double>& state, double v) { + return 1.0 / (1.0 + std::exp(-v / state.y)); +} + +// Mirrors BetaChengStep's computation of v from u1. +double ChengV(const BetaChengState<double>& state, double u1) { + return state.y * std::log(u1 / (1.0 - u1)); +} + +// Cheng's exact log acceptance ratio, evaluated in long double. +long double ChengLhs(const BetaChengState<double>& state, double u1) { + const long double logit = std::log(u1 / (1.0 - u1)); + const long double v = ChengV(state, u1); + const long double a = state.a; + const long double b = state.b; + const long double u = a / (a + b) * std::expm1(v); + return -(a + b) * std::log1p(u) + a * v + logit - std::log(4.0L); +} + +// Returns BetaChengStep(u1, u2) for u2 chosen so log(u1 * u1 * u2) is +// lhs - 1e-9 (must accept) and lhs + 1e-9 (must reject). +std::pair<double, double> ChengDecisionsNearLhs( + const BetaChengState<double>& state, double v) { + const double u1 = U1ForV(state, v); + const long double lhs = ChengLhs(state, u1); + const long double u1_sq = static_cast<long double>(u1) * u1; + const double u2_accept = static_cast<double>(std::exp(lhs - 1e-9L) / u1_sq); + const double u2_reject = static_cast<double>(std::exp(lhs + 1e-9L) / u1_sq); + return {BetaChengStep(u1, u2_accept, state), + BetaChengStep(u1, u2_reject, state)}; +} + +struct ChengSample { + double actual; + long double expected; +}; + +void PrintTo(const ChengSample& s, std::ostream* os) { + *os << absl::StreamFormat("{actual=%.17g, expected=%.17g}", s.actual, + static_cast<double>(s.expected)); +} + +// Returns an accepted BetaChengStep sample at v along with the closed form +// X = W / (b + W) (or b / (b + W) if inverted), W = a * exp(v). +ChengSample ChengSampleAt(const BetaChengState<double>& state, + double target_v) { + const double u1 = U1ForV(state, target_v); + const long double v = ChengV(state, u1); + const long double w = static_cast<long double>(state.a) * std::exp(v); + const long double b = state.b; + // u2 = 1e-30 puts t = log(u1 * u1 * u2) far below lhs, forcing acceptance. + return {BetaChengStep(u1, 1e-30, state), + state.inverted ? b / (b + w) : w / (b + w)}; +} + +MATCHER_P(MatchesClosedForm, rel_tol, + absl::StrFormat("is accepted and within %.3g relative of the " + "closed form", + rel_tol)) { + const long double err = std::abs(arg.actual - arg.expected); + return arg.actual >= 0 && err <= rel_tol * arg.expected; +} + +TEST(BetaChengStepTest, SubnormalAFracHugeExpm1Rejects) { + constexpr double kDblMax = (std::numeric_limits<double>::max)(); + // Beta(0.002, 0.9 * max) is Cheng BA with y = 500 and a / (a + b) < DBL_MIN. + // At v ~ 709, exp(v) > max / 4 takes the (a * (expm1(v) / b)) branch; the + // target density there is negligible, so the step must reject (not NaN). + const BetaChengState<double> state = + MakeBetaChengState(0.002, 0.9 * kDblMax, 500.0, /*use_algorithm_ba=*/true, + /*inverted=*/false); + ASSERT_TRUE(state.subnormal_a_frac); + EXPECT_THAT(BetaChengStep(U1ForV(state, 709.0), 0.5, state), DoubleEq(-1)); + const BetaChengState<double> inverted = + MakeBetaChengState(0.002, 0.9 * kDblMax, 500.0, /*use_algorithm_ba=*/true, + /*inverted=*/true); + EXPECT_THAT(BetaChengStep(U1ForV(inverted, 709.0), 0.5, inverted), + DoubleEq(-1)); +} + +TEST(BetaChengStepTest, SubnormalAFracAcceptsSubnormalSample) { + constexpr double kDblMax = (std::numeric_limits<double>::max)(); + // Accepted |v| > 0.5 draw with a / (a + b) < DBL_MIN: the subnormal result + // a * exp(v) / b must not be quantized through a subnormal a_frac. + const BetaChengState<double> state = + MakeBetaChengState(0.002, 0.9 * kDblMax, 500.0, /*use_algorithm_ba=*/true, + /*inverted=*/false); + EXPECT_THAT(ChengSampleAt(state, 1.6), MatchesClosedForm(1e-9)); +} + +TEST(BetaChengStepTest, Log1pOverflowGuardRejects) { + constexpr double kDblMax = (std::numeric_limits<double>::max)(); + // Hand-built state (y = 709.5 / 30, beyond any real Cheng y) reaching + // v = 709.5: u ~ 0.83, so log1p(u) > (max / 4) / b and the step must reject + // before evaluating b * log1p(u) * (1 + r). + const BetaChengState<double> state = + MakeBetaChengState(1.0, 0.9 * kDblMax, 709.5 / 30.0, + /*use_algorithm_ba=*/false, /*inverted=*/false); + EXPECT_THAT(BetaChengStep(U1ForV(state, 709.5), 0.5, state), DoubleEq(-1)); +} + +TEST(BetaChengStepTest, OverflowingExpRejects) { + // Beta(0.002, 1) is Cheng BA with y = 500: v = 715 overflows exp(v). + const BetaChengState<double> state = + MakeBetaChengState(0.002, 1.0, 500.0, /*use_algorithm_ba=*/true, + /*inverted=*/false); + EXPECT_THAT(BetaChengStep(U1ForV(state, 715.0), 0.5, state), DoubleEq(-1)); +} + +TEST(BetaChengStepTest, ExactAcceptanceMatchesLongDoubleNearSplices) { + const auto kAcceptsThenRejects = Pair(Ge(0.0), DoubleEq(-1.0)); + // Beta(10, 10) exercises the non-precise (a <= 1e4, log1p(u)) exact + // acceptance path for positive and negative v near u = +-0.25. + const BetaChengState<double> bb = + MakeBetaChengState(10.0, 10.0, std::sqrt(0.1), + /*use_algorithm_ba=*/false, /*inverted=*/false); + EXPECT_THAT(ChengDecisionsNearLhs(bb, std::log(1.5) - 1e-6), + kAcceptsThenRejects); + EXPECT_THAT(ChengDecisionsNearLhs(bb, std::log(1.5) + 1e-6), + kAcceptsThenRejects); + EXPECT_THAT(ChengDecisionsNearLhs(bb, std::log(0.5) - 1e-6), + kAcceptsThenRejects); + EXPECT_THAT(ChengDecisionsNearLhs(bb, std::log(0.5) + 1e-6), + kAcceptsThenRejects); + // Beta(2e4, 2e4) (a > 1e4) switches a * (expm1(v) - v) between its series + // and direct forms at |v| = 0.25. + const BetaChengState<double> large = + MakeBetaChengState(2e4, 2e4, std::sqrt((4e4 - 2) / (8e8 - 4e4)), + /*use_algorithm_ba=*/false, /*inverted=*/false); + EXPECT_THAT(ChengDecisionsNearLhs(large, -0.25 + 1e-6), kAcceptsThenRejects); + EXPECT_THAT(ChengDecisionsNearLhs(large, -0.25 - 1e-6), kAcceptsThenRejects); +} + +TEST(BetaChengStepTest, SampleMatchesClosedFormAcrossBranches) { + // Beta(0.5, 2) is Cheng BA with y = 2 and a_frac = 0.2. The non-inverted + // output switches from a_frac * exp(v) / (1 + u) to 1 - b_frac / (1 + u) at + // u = 0.2 * expm1(v) = 1, i.e. v = log(6). + for (bool inverted : {false, true}) { + const BetaChengState<double> ba = + MakeBetaChengState(0.5, 2.0, 2.0, /*use_algorithm_ba=*/true, inverted); + EXPECT_THAT(ChengSampleAt(ba, std::log(6.0) - 1e-6), + MatchesClosedForm(1e-15)); + EXPECT_THAT(ChengSampleAt(ba, std::log(6.0) + 1e-6), + MatchesClosedForm(1e-15)); + EXPECT_THAT(ChengSampleAt(ba, 0.5), MatchesClosedForm(1e-15)); + EXPECT_THAT(ChengSampleAt(ba, -0.5), MatchesClosedForm(1e-15)); + } + // Beta(2e4, 2e4) (a > 1e4) adds the offset from a / (a + b) explicitly. + const BetaChengState<double> large = + MakeBetaChengState(2e4, 2e4, std::sqrt((4e4 - 2) / (8e8 - 4e4)), + /*use_algorithm_ba=*/false, /*inverted=*/false); + EXPECT_THAT(ChengSampleAt(large, 0.01), MatchesClosedForm(1e-15)); + EXPECT_THAT(ChengSampleAt(large, -0.01), MatchesClosedForm(1e-15)); +} + +TEST(BetaJoehnkStepTest, DirectPowSumRoundingToOneUsesLogSpace) { + // alpha = beta = 1, so x = u and y = v exactly; both sums round to 1.0. + const double kTwoM30 = std::ldexp(1.0, -30); + const double v = 1.0 - kTwoM30; + // u + v = 1 + 2^-53 > 1 (ties to 1.0): must reject. + EXPECT_THAT(BetaJoehnkStep(kTwoM30 + std::ldexp(1.0, -53), v, 1.0, 1.0, 1.0, + 1.0, /*try_direct_pow=*/true), + DoubleEq(-1)); + // u + v = 1 - 2^-54 < 1 (ties to 1.0): must accept u / (u + v). + const double u = kTwoM30 - std::ldexp(1.0, -54); + EXPECT_THAT(BetaJoehnkStep(u, v, 1.0, 1.0, 1.0, 1.0, /*try_direct_pow=*/true), + DoubleNear(u / (u + v), 1e-12 * u)); +} + +TEST(BetaJoehnkStepTest, OneSidedInfiniteLogReturnsEndpoint) { + // log(0.5) / 1e-310 overflows to -inf while the other side stays finite. + constexpr double kTiny = 1e-310; + EXPECT_THAT(BetaJoehnkStep(0.5, 0.9, kTiny, 1.0, 1.0 / kTiny, 1.0, + /*try_direct_pow=*/false), + DoubleEq(0.0)); + EXPECT_THAT(BetaJoehnkStep(0.9, 0.5, 1.0, kTiny, 1.0, 1.0 / kTiny, + /*try_direct_pow=*/false), + DoubleEq(1.0)); +} + MATCHER(FailsLeavingUnchanged, "fails stream extraction and leaves target and stream flags " "unchanged") {