Fix numerical stability and float-to-int overflow UB in zipf_distribution. Extreme parameter regimes in `absl::zipf_distribution` previously suffered from undefined behavior, infinite rejection loops, or severe bias: * Casting 64-bit `k` bounds above `2^53` directly to `double` rounded up to `2^63` or `2^64`, triggering `[conv.fpint]` float-to-int overflow UB or sampling outcomes above `k`; `k >= 2^53` also degraded rejection efficiency to ~50%. * Cancellation and overflow/underflow in the unnormalized ZRI integral `h(x)` distorted weights as `q -> 1+` or `v < 1`, hung in infinite loops when `h(x)` underflowed at large `q`, collapsed squeeze thresholds out of `[0, 0.5)`, and double-counted `k = 0` on boundary rounding. Also factor the `IntType`-independent ZRI state and transcendental paths out of the header into `zipf_distribution.cc`. Output sequences change; `absl::zipf_distribution` does not guarantee cross-release stability. PiperOrigin-RevId: 1022524399
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 253898d..62b4720 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -276,6 +276,7 @@ "random/seed_sequences.h" "random/uniform_int_distribution.h" "random/uniform_real_distribution.h" + "random/zipf_distribution.cc" "random/zipf_distribution.h" "status/internal/status_internal.cc" "status/internal/status_internal.h"
diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 162e328..edca821 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel
@@ -58,6 +58,7 @@ srcs = [ "discrete_distribution.cc", "gaussian_distribution.cc", + "zipf_distribution.cc", ], hdrs = [ "bernoulli_distribution.h", @@ -76,7 +77,6 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:public"], deps = [ - "//absl/base:base_internal", "//absl/base:config", "//absl/base:core_headers", "//absl/meta:type_traits", @@ -457,7 +457,9 @@ deps = [ ":distributions", ":random", + "//absl/base:config", "//absl/log", + "//absl/numeric:int128", "//absl/random/internal:distribution_test_util", "//absl/random/internal:pcg_engine", "//absl/random/internal:sequence_urbg",
diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index cef4ab5..db119e1 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt
@@ -186,6 +186,7 @@ SRCS "discrete_distribution.cc" "gaussian_distribution.cc" + "zipf_distribution.cc" HDRS "bernoulli_distribution.h" "beta_distribution.h" @@ -508,6 +509,8 @@ LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS + absl::config + absl::int128 absl::log absl::random_distributions absl::random_internal_distribution_test_util
diff --git a/absl/random/benchmarks.cc b/absl/random/benchmarks.cc index c89388b..ebfa949 100644 --- a/absl/random/benchmarks.cc +++ b/absl/random/benchmarks.cc
@@ -328,6 +328,7 @@ BENCHMARK_TEMPLATE(BM_Zipf, Engine, absl::zipf_distribution<uint64_t>); \ BENCHMARK_TEMPLATE(BM_Zipf, Engine, absl::zipf_distribution<uint64_t>, 2, \ 3); \ + BENCHMARK_TEMPLATE(BM_Zipf, Engine, absl::zipf_distribution<uint64_t>, 3); \ BENCHMARK_TEMPLATE(BM_Bernoulli, Engine, std::bernoulli_distribution, \ 257305); \ BENCHMARK_TEMPLATE(BM_Bernoulli, Engine, absl::bernoulli_distribution, \
diff --git a/absl/random/zipf_distribution.cc b/absl/random/zipf_distribution.cc new file mode 100644 index 0000000..8997664 --- /dev/null +++ b/absl/random/zipf_distribution.cc
@@ -0,0 +1,251 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/random/zipf_distribution.h" + +#include <algorithm> +#include <cassert> +#include <cmath> +#include <limits> + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +namespace { + +// Returns v / (v + x) for v > 0 and 0 <= x <= 1e300. The direct form costs a +// single division; dividing through by v is only needed where v + x could +// overflow. +double RatioVOverVPlusX(double v, double x) { + return (v <= 1e300) ? v / (v + x) : 1.0 / (1.0 + (x / v)); +} + +// Returns log(exp(a) + exp(b)) without overflow or underflow of exp(). +double LogAddExp(double a, double b) { + return (std::max)(a, b) + std::log1p(std::exp(-std::abs(a - b))); +} + +} // namespace + +ZipfParam::ZipfParam(double max_kd, double q, double v) + : q_(q), + v_(v), + max_kd_(max_kd), + qm1_(q - 1.0), + qm1_inv_(0.0), + xm_(max_kd + 0.5), + quadratic_(q == 2.0) { + assert(max_kd >= 0.0); + assert(std::isfinite(q) && q > 1.0); + assert(std::isfinite(v) && v > 0.0); + qm1_inv_ = 1.0 / qm1_; + if (quadratic_) { + // D(x) = (xm - x) * (v / (v + x)) * cm with cm = v / (v + xm). + exp_zm_ = 0.0; + zm_or_cm_ = RatioVOverVPlusX(v_, xm_); + // D(0) = v * xm / (v + xm) is symmetric in (v, xm). Scaling the smaller + // of the two by the ratio of the larger, which lies in [0.5, 1], keeps + // every intermediate away from overflow and subnormals. + const double lo = (std::min)(v_, xm_); + const double hi = (std::max)(v_, xm_); + d0_ = lo * RatioVOverVPlusX(hi, lo); + } else { + const double log_xm = Log1pRatio(xm_); + if (q_ * log_xm <= 1e-40) { + // Across [0, xm_], (1 + t / v)^(-q) == 1.0 to > 130 bits. Use the exact + // linear limit D(x) = xm_ - x to avoid subnormal underflow in zm or + // (q - 1) / v * delta when q -> 1+ and v is near DBL_MAX. + zm_or_cm_ = 0.0; + exp_zm_ = 0.0; + d0_ = xm_; + } else { + const double zm = -qm1_ * log_xm; + zm_or_cm_ = zm; + double neg_expm1_zm; + if (zm >= -0.5) { + exp_zm_ = std::expm1(zm); + neg_expm1_zm = -exp_zm_; + } else { + exp_zm_ = (zm > -746.0) ? std::exp(zm) : 0.0; + neg_expm1_zm = 1.0 - exp_zm_; + } + d0_ = v_ * (neg_expm1_zm * qm1_inv_); + } + } + + d0x5_ = (std::min)(TailIntegral(0.5), d0_); + total_hat_ = d0x5_ + 1.0; + + if (max_kd_ == 0.0) { + s_ = 0.0; + } else if (v_ == 1.0 && quadratic_) { + s_ = 0.46153846153846123; + } else { + s_ = ComputeS(); + } +} + +double ZipfParam::Log1pRatio(double x) const { + const double ratio = x / v_; + if (std::isfinite(ratio)) { + return std::log1p(ratio); + } + // When x / v_ overflows double, 1 + x / v_ == x / v_ to full precision. + return std::log(x) - std::log(v_); +} + +double ZipfParam::VExpm1(double t) const { + if (t <= 709.0) { + return v_ * std::expm1(t); + } + // When t > 709, exp(t) - 1 == exp(t) to full precision; combine logs to + // avoid premature overflow when v_ is very small. + return std::exp(std::log(v_) + t); +} + +double ZipfParam::ScaleQm1OverV(double delta) const { + if (v_ < 1.0) { + return (delta / v_) * qm1_; + } + if (qm1_ > 1e280) { + return (qm1_ / v_) * delta; + } + return (qm1_ * delta) / v_; +} + +double ZipfParam::TailIntegral(double x) const { + if (x >= xm_) { + return 0.0; + } + if (quadratic_) { + return ((xm_ - x) * RatioVOverVPlusX(v_, x)) * zm_or_cm_; + } + if (zm_or_cm_ == 0.0) { + return xm_ - x; + } + const double zx = -qm1_ * Log1pRatio(x); + if (zx < -746.0) { + return 0.0; + } + const double exp_zx = std::exp(zx); + const double neg_expm1_diff = -std::expm1(zm_or_cm_ - zx); + // 1 - exp(zm - zx) <= min(1, zx - zm) and log1p(xm / v) <= xm / v bound + // v * (neg_expm1_diff / (q - 1)) by xm_, so the inner product can not + // overflow for any v > 0. Scaling by exp_zx <= 1 last (rather than forming + // v * exp_zx first) keeps it from underflowing into subnormals before the + // final product does. + return exp_zx * (v_ * (neg_expm1_diff * qm1_inv_)); +} + +double ZipfParam::TailIntegralInvGeneral(double d) const { + double z; + if (d >= 0.5 * d0_) { + // When d is in the upper half of [0, D(0)], d0_ - d is exact by Sterbenz's + // lemma and u = (q - 1) / v * (D(0) - d) <= 0.5, avoiding catastrophic + // cancellation of exp(zm_) + b near 1.0 when x << v << xm_. + const double u = ScaleQm1OverV(d0_ - d); + if (u >= 1.0) { + return xm_; + } + z = std::log1p(-u); + } else { + const double b = ScaleQm1OverV(d); + if (zm_or_cm_ >= -0.5) { + const double s = exp_zm_ + b; + if (s <= -1.0) return xm_; + if (s >= 0.0) return 0.0; + z = std::log1p(s); + } else if (zm_or_cm_ >= -708.0) { + const double val = exp_zm_ + b; + if (val >= 1.0) return 0.0; + z = std::log(val); + } else if (b == 0.0) { + return xm_; + } else { + // exp(zm_) underflows; evaluate log(exp(zm_) + b) in log space. + z = LogAddExp(zm_or_cm_, std::log(b)); + } + } + return (std::min)(VExpm1(-z * qm1_inv_), xm_); +} + +double ZipfParam::ComputeS() const { + // Solve \int_{1 - s}^{1.5} (v + x)^(-q) dx = (v + 1)^(-q) directly on + // [1 - s, 1.5] with y = v + 1, independent of xm_. With r = 1 / y and + // q1 = q - 1 > 0: + // (1 - s * r)^(-q1) = (1 + 0.5 * r)^(-q1) + q1 * r. + // Because s(k) increases with k >= 1 and 0 < s(1) < 0.5, stepping down below + // transcendental rounding error and clamping to [0, nextafter(0.5, 0)) gives + // a sound squeeze threshold for all k >= 1 and ensures k - x == 0 <= s_ for + // all x >= 2^52 (where every double is an integer, and k + 0.5 == k for + // k >= 2^53). + const double y = v_ + 1.0; + double s; + if (quadratic_) { + const double r = 1.0 / y; + s = (0.5 * (1.0 + r)) / (1.0 + r * (1.0 + 0.5 * r)); + } else if (q_ / y <= 1e-8) { + // For q / y <= 1e-8, 0.5 - s_exact < 0.085 * (q / y)^2 < 1e-17 < 2^-54, + // avoiding subnormal underflow of qm1_ / y when v_ is huge and q_ -> 1+. + s = std::nextafter(0.5, 0.0); + } else { + const double qr = qm1_ / y; + if (!std::isfinite(qr) || qr >= 1e300) { + // (1 + 0.5 / y)^(-qm1_) <= 1 is negligible relative to qr >= 1e300. + const double log_lhs_over_qm1 = (std::log(qm1_) - std::log(y)) / qm1_; + s = -y * std::expm1(-log_lhs_over_qm1); + } else if (y >= 1e100) { + // 0.5 / y <= 5e-101 so log1p(0.5 / y) == 0.5 / y and + // log1p(a) / qm1_ < 1e-89, avoiding subnormal underflow at huge v_. + const double a = std::expm1(-0.5 * qr) + qr; + s = std::log1p(a) / qr; + } else { + const double a = std::expm1(-qm1_ * std::log1p(0.5 / y)) + qr; + const double log_lhs_over_qm1 = std::log1p(a) / qm1_; + s = -y * std::expm1(-log_lhs_over_qm1); + } + } + + if (!std::isfinite(s) || s <= 0.0) { + return 0.0; + } + constexpr double kSafetyFactor = + 1.0 - 8.0 * std::numeric_limits<double>::epsilon(); + s = std::nextafter(s * kSafetyFactor, 0.0); + s = (std::min)(s, std::nextafter(0.5, 0.0)); + return (s > 0.0) ? s : 0.0; +} + +double ZipfParam::PowNegativeQ(double k) const { + if (k == 0.0) { + return 1.0; + } + if (quadratic_) { + const double r = RatioVOverVPlusX(v_, k); + return r * r; + } + const double arg = -q_ * Log1pRatio(k); + return (arg > -746.0) ? std::exp(arg) : 0.0; +} + +bool ZipfParam::AcceptsHatSqueezeMiss(double k, double d) const { + return d <= TailIntegral(k + 0.5) + PowNegativeQ(k); +} + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/random/zipf_distribution.h b/absl/random/zipf_distribution.h index 50d9410..44aced0 100644 --- a/absl/random/zipf_distribution.h +++ b/absl/random/zipf_distribution.h
@@ -17,6 +17,7 @@ #include <cassert> #include <cmath> +#include <cstdint> #include <ios> #include <istream> #include <limits> @@ -24,13 +25,124 @@ #include <type_traits> #include "absl/base/config.h" +#include "absl/random/internal/fast_uniform_bits.h" +#include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" #include "absl/random/internal/traits.h" -#include "absl/random/uniform_real_distribution.h" namespace absl { ABSL_NAMESPACE_BEGIN +namespace random_internal { +struct ZipfDistributionTestPeer; + +// Returns the largest IEEE-754 double <= k, which round-trips into IntType +// without [conv.fpint] overflow or exceeding k. Masking bits below the top +// double significand bits in integer arithmetic avoids x87 excess precision +// (FLT_EVAL_METHOD == 2) rounding the result above k. +template <typename IntType> +double MaxIntegralDoubleLe(IntType k) { + if (!(k > IntType{0})) { + return 0.0; + } + if constexpr (std::numeric_limits<IntType>::digits <= + std::numeric_limits<double>::digits) { + return static_cast<double>(k); + } else { + using UnsignedT = typename MakeUnsigned<IntType>::type; + UnsignedT uk = static_cast<UnsignedT>(k); + const int width = BitWidth(uk); + if (width > std::numeric_limits<double>::digits) { + const int shift = width - std::numeric_limits<double>::digits; + uk = (uk >> shift) << shift; + } + return static_cast<double>(uk); + } +} + +// ZipfParam holds the IntType-independent state and math of Algorithm ZRI +// for absl::zipf_distribution, expressed via the normalized tail integral +// +// D(x) = \int_x^{xm} (1 + t / v)^(-q) dt, xm = max_kd + 0.5, +// +// which scales the unnormalized PMF by v^q so f(0) = 1.0 and avoids +// cancellation as q -> 1+, overflow when v < 1, underflow when q is steep, and +// subtraction of v at large v. +// +// Only the libm-free inversion paths (q == 2 and the linear limit) are inline; +// setup, the general inversion, and the squeeze-miss evaluation are cold or +// libm-bound and live in zipf_distribution.cc. +class ZipfParam { + public: + // Preconditions: max_kd >= 0 is integral, q > 1, v > 0. + ZipfParam(double max_kd, double q, double v); + + double q() const { return q_; } + double v() const { return v_; } + double max_kd() const { return max_kd_; } + double d0x5() const { return d0x5_; } + double total_hat() const { return total_hat_; } + double s() const { return s_; } + + // Returns D(x), clamped to 0 for x >= xm. + double TailIntegral(double x) const; + + // Returns x in [0, xm] such that D(x) == d. + double TailIntegralInv(double d) const { + if (d > 0.0 && d >= d0_) { + return 0.0; + } + return TailIntegralInvBelowD0(d); + } + + // TailIntegralInv() for d < D(0), which the sampling loop has already + // established via d < d0x5() <= D(0). + double TailIntegralInvBelowD0(double d) const { + if (d <= 0.0) { + return xm_; + } + if (quadratic_) { + const double x = (d0_ - d) / (zm_or_cm_ + (d / v_)); + return (x < xm_) ? x : xm_; + } + if (zm_or_cm_ == 0.0) { + return d0_ - d; + } + return TailIntegralInvGeneral(d); + } + + // Exact ZRI acceptance test d <= D(k + 0.5) + f(k) for integral k >= 1, + // evaluated only when the squeeze k - x <= s() misses. + bool AcceptsHatSqueezeMiss(double k, double d) const; + + private: + // TailIntegralInv() for 0 < d < D(0) when q != 2 outside the linear limit. + double TailIntegralInvGeneral(double d) const; + + double Log1pRatio(double x) const; // log(1 + x / v) + double VExpm1(double t) const; // v * (exp(t) - 1) + double ScaleQm1OverV(double delta) const; // (q - 1) / v * delta + double PowNegativeQ(double k) const; // f(k) = (1 + k / v)^(-q) + double ComputeS() const; + + double q_; + double v_; + double max_kd_; // largest double <= k + double qm1_; // q - 1 + double qm1_inv_; // 1 / (q - 1) + double xm_; // max_kd_ + 0.5 + double zm_or_cm_; // q == 2 ? v / (v + xm_) : -(q - 1) * log(1 + xm_ / v), + // or 0 for the linear limit D(x) = xm_ - x + double exp_zm_; // q != 2: expm1(zm) if zm >= -0.5 else exp(zm) + double d0_; // D(0) + double d0x5_; // D(0.5) + double total_hat_; // D(0.5) + f(0) == D(0.5) + 1.0 + double s_; // ZRI squeeze threshold, guaranteed in [0, 0.5) + bool quadratic_; // q == 2 +}; + +} // namespace random_internal + // absl::zipf_distribution produces random integer-values in the range [0, k], // distributed according to the unnormalized discrete probability function: // @@ -68,11 +180,11 @@ double q = 2.0, double v = 1.0); result_type k() const { return k_; } - double q() const { return q_; } - double v() const { return v_; } + double q() const { return zri_.q(); } + double v() const { return zri_.v(); } friend bool operator==(const param_type& a, const param_type& b) { - return a.k_ == b.k_ && a.q_ == b.q_ && a.v_ == b.v_; + return a.k_ == b.k_ && a.q() == b.q() && a.v() == b.v(); } friend bool operator!=(const param_type& a, const param_type& b) { return !(a == b); @@ -80,22 +192,10 @@ private: friend class zipf_distribution; - inline double h(double x) const; - inline double hinv(double x) const; - inline double compute_s() const; - inline double pow_negative_q(double x) const; + friend struct random_internal::ZipfDistributionTestPeer; - // Parameters here are exactly the same as the parameters of Algorithm ZRI - // in the paper. IntType k_; - double q_; - double v_; - - double one_minus_q_; // 1-q - double s_; - double one_minus_q_inv_; // 1 / 1-q - double hxm_; // h(k + 0.5) - double hx0_minus_hxm_; // h(x0) - h(k + 0.5) + random_internal::ZipfParam zri_; static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::zipf_distribution<> must be " @@ -151,65 +251,9 @@ template <typename IntType> zipf_distribution<IntType>::param_type::param_type( typename zipf_distribution<IntType>::result_type k, double q, double v) - : k_(k), q_(q), v_(v), one_minus_q_(1 - q) { - assert(q > 1); - assert(v > 0); + : k_(k), zri_(random_internal::MaxIntegralDoubleLe(k), q, v) { + // q and v are validated in ZipfParam::ZipfParam(). assert(k >= 0); - one_minus_q_inv_ = 1 / one_minus_q_; - - // Setup for the ZRI algorithm (pg 17 of the paper). - // Compute: h(i max) => h(k + 0.5) - constexpr double kMax = 18446744073709549568.0; - double kd = static_cast<double>(k); - // TODO(absl-team): Determine if this check is needed, and if so, add a test - // that fails for k > kMax - if (kd > kMax) { - // Ensure that our maximum value is capped to a value which will - // round-trip back through double. - kd = kMax; - } - hxm_ = h(kd + 0.5); - - // Compute: h(0) - const bool use_precomputed = (v == 1.0 && q == 2.0); - const double h0x5 = use_precomputed ? (-1.0 / 1.5) // exp(-log(1.5)) - : h(0.5); - const double elogv_q = (v_ == 1.0) ? 1 : pow_negative_q(v_); - - // h(0) = h(0.5) - exp(log(v) * -q) - hx0_minus_hxm_ = (h0x5 - elogv_q) - hxm_; - - // And s - s_ = use_precomputed ? 0.46153846153846123 : compute_s(); -} - -template <typename IntType> -double zipf_distribution<IntType>::param_type::h(double x) const { - // std::exp(one_minus_q_ * std::log(v_ + x)) * one_minus_q_inv_; - x += v_; - return (one_minus_q_ == -1.0) - ? (-1.0 / x) // -exp(-log(x)) - : (std::exp(std::log(x) * one_minus_q_) * one_minus_q_inv_); -} - -template <typename IntType> -double zipf_distribution<IntType>::param_type::hinv(double x) const { - // std::exp(one_minus_q_inv_ * std::log(one_minus_q_ * x)) - v_; - return -v_ + ((one_minus_q_ == -1.0) - ? (-1.0 / x) // exp(-log(-x)) - : std::exp(one_minus_q_inv_ * std::log(one_minus_q_ * x))); -} - -template <typename IntType> -double zipf_distribution<IntType>::param_type::compute_s() const { - // 1 - hinv(h(1.5) - std::exp(std::log(v_ + 1) * -q_)); - return 1.0 - hinv(h(1.5) - pow_negative_q(v_ + 1.0)); -} - -template <typename IntType> -double zipf_distribution<IntType>::param_type::pow_negative_q(double x) const { - // std::exp(std::log(x) * -q_); - return q_ == 2.0 ? (1.0 / (x * x)) : std::exp(std::log(x) * -q_); } template <typename IntType> @@ -217,22 +261,38 @@ typename zipf_distribution<IntType>::result_type zipf_distribution<IntType>::operator()( URBG& g, const param_type& p) { // NOLINT(runtime/references) - absl::uniform_real_distribution<double> uniform_double; + const random_internal::ZipfParam& zri = p.zri_; + using random_internal::GeneratePositiveTag; + using random_internal::GenerateRealFromBits; + random_internal::FastUniformBits<uint64_t> fast_u64; double k; for (;;) { - const double v = uniform_double(g); - const double u = p.hxm_ + v * p.hx0_minus_hxm_; - const double x = p.hinv(u); - k = rint(x); // std::floor(x + 0.5); - if (k > static_cast<double>(p.k())) continue; // reject k > max_k - if (k - x <= p.s_) break; - const double h = p.h(k + 0.5); - const double r = p.pow_negative_q(p.v_ + k); - if (u >= h - r) break; + // w ~ U[0, 1). + const double w = + GenerateRealFromBits<double, GeneratePositiveTag, true>(fast_u64(g)); + const double d = w * zri.total_hat(); + if (d >= zri.d0x5()) { + return 0; + } + const double x = zri.TailIntegralInvBelowD0(d); + k = std::rint(x); + if (k < 1.0) { + // d >= d0x5() already accounts for the full mass of k = 0; clamping to + // k = 1 prevents double-counting k = 0 if rounding yields x <= 0.5, and + // since k - x >= 0.5 > s() it falls through to the exact rejection test. + k = 1.0; + } + if (!(k <= zri.max_kd())) { // Also rejects NaN. + continue; + } + if (k - x <= zri.s() || zri.AcceptsHatSqueezeMiss(k, d)) { + break; + } } - IntType ki = static_cast<IntType>(k); - assert(ki <= p.k_); - return ki; + // k is integral with 1 <= k <= max_kd() <= p.k_, and max_kd() converts to + // IntType exactly (see MaxIntegralDoubleLe), so the cast neither overflows + // nor exceeds p.k_. + return static_cast<IntType>(k); } template <typename CharT, typename Traits, typename IntType>
diff --git a/absl/random/zipf_distribution_test.cc b/absl/random/zipf_distribution_test.cc index fcdf110..3783031 100644 --- a/absl/random/zipf_distribution_test.cc +++ b/absl/random/zipf_distribution_test.cc
@@ -21,6 +21,7 @@ #include <cstdint> #include <iterator> #include <limits> +#include <ostream> #include <random> #include <sstream> #include <string> @@ -29,7 +30,9 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/log/log.h" +#include "absl/numeric/int128.h" #include "absl/random/internal/chi_square.h" #include "absl/random/internal/distribution_test_util.h" #include "absl/random/internal/pcg_engine.h" @@ -37,12 +40,54 @@ #include "absl/random/random.h" #include "absl/strings/str_cat.h" #include "absl/strings/str_replace.h" -#include "absl/strings/strip.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +struct ZipfDistributionTestPeer { + template <typename IntType> + static double s(const zipf_distribution<IntType>& d) { + return d.param().zri_.s(); + } + template <typename IntType> + static double d0x5(const zipf_distribution<IntType>& d) { + return d.param().zri_.d0x5(); + } + template <typename IntType> + static double total_hat(const zipf_distribution<IntType>& d) { + return d.param().zri_.total_hat(); + } + template <typename IntType> + static double tail_integral(const zipf_distribution<IntType>& d, double x) { + return d.param().zri_.TailIntegral(x); + } + template <typename IntType> + static double tail_integral_inv(const zipf_distribution<IntType>& d, + double u) { + return d.param().zri_.TailIntegralInv(u); + } +}; + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl namespace { using ::absl::random_internal::kChiSquared; +using ::absl::random_internal::MaxIntegralDoubleLe; +using ::absl::random_internal::ZipfDistributionTestPeer; +using ::absl::random_internal::ZipfParam; +using ::testing::AllOf; +using ::testing::DoubleNear; +using ::testing::Each; using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::Ge; +using ::testing::Gt; +using ::testing::Le; +using ::testing::Lt; template <typename IntType> class ZipfDistributionTypedTest : public ::testing::Test {}; @@ -58,6 +103,7 @@ absl::InsecureBitGen gen; for (const auto& param : { param_type(), + param_type(0), param_type(32), param_type(100, 3, 2), param_type(std::numeric_limits<TypeParam>::max(), 4, 3), @@ -91,6 +137,7 @@ ss >> after; + EXPECT_FALSE(ss.fail()); EXPECT_EQ(before.k(), after.k()); EXPECT_EQ(before.q(), after.q()); EXPECT_EQ(before.v(), after.v()); @@ -107,44 +154,49 @@ if (sample > sample_max) sample_max = sample; if (sample < sample_min) sample_min = sample; } - LOG(INFO) << "Range: " << sample_min << ", " << sample_max; + LOG(INFO) << "Range: " << +sample_min << ", " << +sample_max; } } class ZipfModel { public: - ZipfModel(size_t k, double q, double v) : k_(k), q_(q), v_(v) {} + ZipfModel(uint64_t k, double q, double v) : k_(k), q_(q), v_(v) {} double mean() const { return mean_; } // For the other moments of the Zipf distribution, see, for example, // http://mathworld.wolfram.com/ZipfDistribution.html - // PMF(k) = (1 / k^s) / H(N,s) - // Returns the probability that any single invocation returns k. - double PMF(size_t i) { return i >= hnq_.size() ? 0.0 : hnq_[i] / sum_hnq_; } + // PMF(i) = (1 + i / v)^(-q) / Z + // Returns the probability that any single invocation returns i. + double PMF(uint64_t i) { + return i >= weights_.size() + ? 0.0 + : weights_[static_cast<size_t>(i)] / sum_weights_; + } - // CDF = H(k, s) / H(N,s) - double CDF(size_t i) { - if (i >= hnq_.size()) { + // CDF(i) = P(X < i) = sum_{j=0}^{i-1} PMF(j). + double CDF(uint64_t i) { + if (i == 0) { + return 0.0; + } + if (i > cdf_.size()) { return 1.0; } - auto it = std::begin(hnq_); - double h = 0.0; - for (const auto end = it; it != end; it++) { - h += *it; + if (i == cdf_.size() && !truncated_) { + return 1.0; } - return h / sum_hnq_; + return cdf_[static_cast<size_t>(i - 1)] / sum_weights_; } // The InverseCDF returns the k values which bound p on the upper and lower // bound. Since there is no closed-form solution, this is implemented as a - // bisction of the cdf. - std::pair<size_t, size_t> InverseCDF(double p) { - size_t min = 0; - size_t max = hnq_.size(); + // bisection of the cdf. + std::pair<uint64_t, uint64_t> InverseCDF(double p) { + uint64_t min = 0; + uint64_t max = static_cast<uint64_t>(cdf_.size()) + (truncated_ ? 1 : 0); while (max > min + 1) { - size_t target = (max + min) >> 1; + uint64_t target = (max + min) >> 1; double x = CDF(target); if (x > p) { max = target; @@ -155,60 +207,58 @@ return {min, max}; } - // Compute the probability totals, which are based on the generalized harmonic - // number, H(N,s). - // H(N,s) == SUM(k=1..N, 1 / k^s) - // - // In the limit, H(N,s) == zetac(s) + 1. - // - // NOTE: The mean of a zipf distribution could be computed here as well. - // Mean := H(N, s-1) / H(N,s). - // Given the parameter v = 1, this gives the following function: - // (Hn(100, 1) - Hn(1,1)) / (Hn(100,2) - Hn(1,2)) = 6.5944 - // + // Compute the unnormalized probability totals based on (1 + i / v)^(-q). void Init() { - if (!hnq_.empty()) { + if (!weights_.empty()) { return; } - hnq_.clear(); - hnq_.reserve(std::min(k_, size_t{1000})); + const size_t reserve_n = + (k_ < uint64_t{1000}) ? static_cast<size_t>(k_ + 1) : size_t{1001}; + weights_.reserve(reserve_n); + cdf_.reserve(reserve_n); - sum_hnq_ = 0; - double qm1 = q_ - 1.0; - double sum_hnq_m1 = 0; - for (size_t i = 0; i < k_; i++) { - // Partial n-th generalized harmonic number - const double x = v_ + i; - - // H(n, q-1) - const double hnqm1 = (q_ == 2.0) ? (1.0 / x) - : (q_ == 3.0) ? (1.0 / (x * x)) - : std::pow(x, -qm1); - sum_hnq_m1 += hnqm1; - - // H(n, q) - const double hnq = (q_ == 2.0) ? (1.0 / (x * x)) - : (q_ == 3.0) ? (1.0 / (x * x * x)) - : std::pow(x, -q_); - sum_hnq_ += hnq; - hnq_.push_back(hnq); - if (i > 1000 && hnq <= 1e-10) { - // The harmonic number is too small. + sum_weights_ = 0.0; + double weighted_i_sum = 0.0; + truncated_ = false; + uint64_t i = 0; + for (;; ++i) { + const double lp = std::log1p(static_cast<double>(i) / v_); + const double weight = std::exp(-q_ * lp); + sum_weights_ += weight; + weighted_i_sum += static_cast<double>(i) * weight; + weights_.push_back(weight); + cdf_.push_back(sum_weights_); + if (i == k_) { + break; + } + if (i >= 10000 && weight <= 1e-12 * sum_weights_) { + truncated_ = true; break; } } - assert(sum_hnq_ > 0); - mean_ = sum_hnq_m1 / sum_hnq_; + if (truncated_) { + const double kd = MaxIntegralDoubleLe(k_); + const double z_lo = + -(q_ - 1.0) * std::log1p((static_cast<double>(i) + 0.5) / v_); + const double z_hi = -(q_ - 1.0) * std::log1p((kd + 0.5) / v_); + const double tail = + v_ * std::exp(z_lo) * (-std::expm1(z_hi - z_lo)) / (q_ - 1.0); + sum_weights_ += tail; + } + assert(sum_weights_ > 0); + mean_ = weighted_i_sum / sum_weights_; } private: - const size_t k_; + const uint64_t k_; const double q_; const double v_; - double mean_; - std::vector<double> hnq_; - double sum_hnq_; + double mean_ = 0.0; + std::vector<double> weights_; + std::vector<double> cdf_; + double sum_weights_ = 0.0; + bool truncated_ = false; }; using zipf_u64 = absl::zipf_distribution<uint64_t>; @@ -219,7 +269,7 @@ ZipfTest() : ZipfModel(GetParam().k(), GetParam().q(), GetParam().v()) {} // We use a fixed bit generator for distribution accuracy tests. This allows - // these tests to be deterministic, while still testing the qualify of the + // these tests to be deterministic, while still testing the quality of the // implementation. absl::random_internal::pcg64_2018_engine rng_{0x2B7E151628AED2A6}; }; @@ -231,7 +281,7 @@ size_t trials = 10000; // Find the split-points for the buckets. - std::vector<size_t> points; + std::vector<uint64_t> points; std::vector<double> expected; { double last_cdf = 0.0; @@ -239,32 +289,35 @@ for (double p = 0.01; p < 1.0; p += 0.01) { auto x = InverseCDF(p); if (points.empty() || points.back() < x.second) { - const double p = CDF(x.second); + const double cdf_at_split = CDF(x.second); + if (cdf_at_split <= last_cdf) { + continue; + } points.push_back(x.second); - double q = p - last_cdf; + double q = cdf_at_split - last_cdf; expected.push_back(q); - last_cdf = p; + last_cdf = cdf_at_split; if (q < min_p) { min_p = q; } } } - if (last_cdf < 0.999) { - points.push_back(std::numeric_limits<size_t>::max()); + if (last_cdf < 0.999 || (points.size() == 1 && last_cdf < 1.0)) { + points.push_back(std::numeric_limits<uint64_t>::max()); double q = 1.0 - last_cdf; expected.push_back(q); if (q < min_p) { min_p = q; } } else { - points.back() = std::numeric_limits<size_t>::max(); + points.back() = std::numeric_limits<uint64_t>::max(); expected.back() += (1.0 - last_cdf); } // The Chi-Squared score is not completely scale-invariant; it works best // when the small values are in the small digits. trials = static_cast<size_t>(8.0 / min_p); } - ASSERT_GT(points.size(), 0); + ASSERT_GT(points.size(), 1); // Generate n variates and fill the counts vector with the count of their // occurrences. @@ -277,25 +330,24 @@ ASSERT_LE(x, dis.max()); ASSERT_GE(x, dis.min()); avg += static_cast<double>(x); - auto it = std::upper_bound(std::begin(points), std::end(points), - static_cast<size_t>(x)); - buckets[std::distance(std::begin(points), it)]++; + auto it = std::upper_bound(points.begin(), points.end() - 1, x); + buckets[static_cast<size_t>(std::distance(points.begin(), it))]++; } avg = avg / static_cast<double>(trials); } // Validate the output using the Chi-Squared test. for (auto& e : expected) { - e *= trials; + e *= static_cast<double>(trials); } - // The null-hypothesis is that the distribution is a poisson distribution with - // the provided mean (not estimated from the data). + // The null-hypothesis is that the distribution is a Zipf distribution with + // the provided k, q, and v (not estimated from the data). const int dof = static_cast<int>(expected.size()) - 1; + ASSERT_GT(dof, 0); - // NOTE: This test runs about 15x per invocation, so a value of 0.9995 is - // approximately correct for a test suite failure rate of 1 in 100. In - // practice we see failures slightly higher than that. + // NOTE: This test runs about 17x per invocation, so a value of 0.9999 gives + // a low suite-wide false positive rate. const double threshold = absl::random_internal::ChiSquareValue(dof, 0.9999); const double chi_square = absl::random_internal::ChiSquare( @@ -315,7 +367,7 @@ LOG(INFO) << "mean " << avg << " vs. expected " << mean(); LOG(INFO) << kChiSquared << "(data, " << dof << ") = " << chi_square << " (" << p_actual << ")"; - LOG(INFO) << kChiSquared << " @ 0.9995 = " << threshold; + LOG(INFO) << kChiSquared << " @ 0.9999 = " << threshold; FAIL() << kChiSquared << " value of " << chi_square << " is above the threshold."; } @@ -336,8 +388,9 @@ param(k2, q, 0.5), param(k2, q, 1.5), param(k2, q, 2.5), param(k2, q, 10), // vary Q param(k2, 1.5, v), param(k2, 3, v), param(k2, 5, v), param(k2, 10, v), - // Vary V & Q - param(k2, 1.5, 0.5), param(k2, 3, 1.5), param(k, 10, 10)}; + // Vary V & Q, including q -> 1+ and large v + param(k2, 1.5, 0.5), param(k2, 3, 1.5), param(k, 10, 10), + param(100, 1.0 + 1e-15, 10.0), param(100, 2.5, 1e16)}; } std::string ParamName( @@ -425,6 +478,520 @@ } } +template <typename IntType> +IntType SampleFromSeedBits(absl::zipf_distribution<IntType> dist, + uint64_t first_bits) { + absl::random_internal::sequence_urbg urbg( + {first_bits, 0x8000000000000000ull}); + return dist(urbg); +} + +template <typename IntType> +std::vector<IntType> DrawSamples(absl::zipf_distribution<IntType> dist, + size_t count) { + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ull); + std::vector<IntType> samples(count); + std::generate(samples.begin(), samples.end(), [&] { return dist(rng); }); + return samples; +} + +template <typename IntType> +struct SampleSummary { + IntType min_sample; + IntType max_sample; + double mean; +}; + +template <typename IntType> +void PrintTo(const SampleSummary<IntType>& s, std::ostream* os) { + *os << "{min_sample=" << +s.min_sample << ", max_sample=" << +s.max_sample + << ", mean=" << s.mean << "}"; +} + +template <typename IntType> +SampleSummary<IntType> SummarizeSamples(absl::zipf_distribution<IntType> dist, + size_t count) { + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ull); + IntType min_s = dist.max(); + IntType max_s = dist.min(); + double sum = 0.0; + for (size_t i = 0; i < count; ++i) { + const IntType s = dist(rng); + min_s = (std::min)(min_s, s); + max_s = (std::max)(max_s, s); + sum += static_cast<double>(s); + } + return {min_s, max_s, sum / static_cast<double>(count)}; +} + +MATCHER_P3(IsWithinBoundsWithMean, max_val, expected_mean, tol, "") { + return arg.min_sample >= 0 && arg.max_sample <= max_val && + std::abs(arg.mean - expected_mean) <= tol; +} + +struct TailFractionSummary { + uint64_t max_sample; + double tail_fraction; +}; + +void PrintTo(const TailFractionSummary& s, std::ostream* os) { + *os << "{max_sample=" << s.max_sample << ", tail_fraction=" << s.tail_fraction + << "}"; +} + +TailFractionSummary SummarizeTailFraction( + absl::zipf_distribution<uint64_t> dist, uint64_t threshold, size_t count) { + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ull); + uint64_t max_s = 0; + size_t hits = 0; + for (size_t i = 0; i < count; ++i) { + const uint64_t x = dist(rng); + max_s = (std::max)(max_s, x); + if (x >= threshold) { + ++hits; + } + } + return {max_s, static_cast<double>(hits) / static_cast<double>(count)}; +} + +MATCHER_P3(HasBoundedTailFraction, max_val, expected_fraction, tol, "") { + return arg.max_sample <= max_val && + std::abs(arg.tail_fraction - expected_fraction) <= tol; +} + +double SqueezeThreshold(uint64_t k, double q, double v) { + return ZipfDistributionTestPeer::s( + absl::zipf_distribution<uint64_t>(k, q, v)); +} + +MATCHER_P2(IsSoundSqueezeNear, expected, tol, "") { + return arg >= 0.0 && arg < 0.5 && std::abs(arg - expected) <= tol; +} + +double TailIntegralRoundTrip(const absl::zipf_distribution<uint64_t>& dist, + double x) { + return ZipfDistributionTestPeer::tail_integral_inv( + dist, ZipfDistributionTestPeer::tail_integral(dist, x)); +} + +struct ZeroBoundarySummary { + int zeros_below_d0x5; + double zero_probability; + uint64_t first_nonzero_sample; +}; + +void PrintTo(const ZeroBoundarySummary& s, std::ostream* os) { + *os << "{zeros_below_d0x5=" << s.zeros_below_d0x5 + << ", zero_probability=" << s.zero_probability + << ", first_nonzero_sample=" << s.first_nonzero_sample << "}"; +} + +ZeroBoundarySummary ScanTopUniformGrid(absl::zipf_distribution<uint64_t> dist, + int grid_steps) { + const double d0x5 = ZipfDistributionTestPeer::d0x5(dist); + const double total_hat = ZipfDistributionTestPeer::total_hat(dist); + constexpr double kStep = 1.0 / static_cast<double>(uint64_t{1} << 53); + int total_zeros = 0; + int zeros_below = 0; + uint64_t first_nonzero = 0; + for (int m = 1; m <= grid_steps; ++m) { + // Top 52-bit mantissas in [0.5, 1.0): w = 1.0 - m * 2^-53. + const uint64_t bits = 0xfffffffffffff800ull - + static_cast<uint64_t>(m - 1) * (uint64_t{1} << 11); + absl::random_internal::sequence_urbg urbg({bits, 0x0000000000000001ull}); + const uint64_t sample = dist(urbg); + const bool accepted_first = (urbg.invocations() == 1); + const double w = 1.0 - static_cast<double>(m) * kStep; + const bool below_d0x5 = (w * total_hat < d0x5); + if (accepted_first && sample == 0) { + ++total_zeros; + if (below_d0x5) { + ++zeros_below; + } + } else if (accepted_first && first_nonzero == 0) { + first_nonzero = sample; + } + } + return {zeros_below, static_cast<double>(total_zeros) * kStep, first_nonzero}; +} + +MATCHER_P2(MatchesZeroMassWithoutDoubleCounting, expected_prob, tol, "") { + return arg.zeros_below_d0x5 == 0 && + std::abs(arg.zero_probability - expected_prob) <= tol && + arg.first_nonzero_sample == 1; +} + +TEST(ZipfDistributionTest, Int64AndUint64UpperBoundsAvoidFloatCastOverflow) { + constexpr int64_t kRoundsUpInDouble = (int64_t{1} << 62) - 1; + constexpr int64_t kNearMaxRoundsUp = + std::numeric_limits<int64_t>::max() - 1025; + constexpr uint64_t kAbove53Bits = (uint64_t{1} << 53) + 1; + constexpr uint64_t kExact53Bits = (uint64_t{1} << 53) - 1; + + // 64-bit k values where static_cast<double>(k) or xm_ = max_kd_ + 0.5 rounds + // above k (including INT64_MAX -> 2^63 and x87 excess precision): drawing at + // uniform_double == 0.0 must stay <= k without [conv.fpint] overflow. + EXPECT_THAT(SampleFromSeedBits(absl::zipf_distribution<int64_t>{}, 0ull), + Eq(int64_t{9223372036854774784})); + EXPECT_THAT(SampleFromSeedBits(absl::zipf_distribution<int64_t>{}, 1ull), + AllOf(Ge(int64_t{0}), Le(std::numeric_limits<int64_t>::max()))); + EXPECT_THAT(SampleFromSeedBits( + absl::zipf_distribution<int64_t>(kRoundsUpInDouble), 0ull), + Eq(int64_t{4611686018427387392})); + EXPECT_THAT(SampleFromSeedBits( + absl::zipf_distribution<int64_t>(kNearMaxRoundsUp), 0ull), + Eq(int64_t{9223372036854773760})); + EXPECT_THAT( + SampleFromSeedBits(absl::zipf_distribution<uint64_t>(kAbove53Bits), 0ull), + Eq(uint64_t{9007199254740992ull})); + EXPECT_THAT( + SampleFromSeedBits(absl::zipf_distribution<uint64_t>(kExact53Bits), 0ull), + AllOf(Ge(uint64_t{0}), Le(kExact53Bits))); + EXPECT_THAT(SampleFromSeedBits(absl::zipf_distribution<uint64_t>{}, 0ull), + Eq(uint64_t{18446744073709549568ull})); + EXPECT_THAT(SampleFromSeedBits(absl::zipf_distribution<int64_t>(0), 0ull), + Eq(0)); +} + +TEST(ZipfDistributionTest, ExtremeParametersRemainInBoundsAndTerminate) { + // Near q -> 1+: avoids catastrophic cancellation and negative outputs. + EXPECT_THAT( + DrawSamples(absl::zipf_distribution<int>(100, 1.0 + 1e-15, 10.0), 1000), + Each(AllOf(Ge(0), Le(100)))); + EXPECT_THAT(DrawSamples(absl::zipf_distribution<int>( + 100, std::nextafter(1.0, 2.0), 0.5), + 1000), + Each(AllOf(Ge(0), Le(100)))); + + // Steep q (v < 1 or v > 1) and tiny v: P(X = 0) == 1 in IEEE-754 double + // without pow overflow or infinite rejection loops. + EXPECT_THAT(DrawSamples(absl::zipf_distribution<int>(100, 1400.0, 0.6), 500), + Each(0)); + EXPECT_THAT(DrawSamples(absl::zipf_distribution<int>(100, 800.0, 3.0), 500), + Each(0)); + EXPECT_THAT(DrawSamples(zipf_u64(1000, 1.5, 1e-300), 500), Each(0)); +} + +TEST(ZipfDistributionTest, LargeVApproachesUniformSupportMean) { + // Large v = 1e16: previously cancelled exp(...) - v; weights (1 + k/v)^(-q) + // are nearly uniform over [0, 100] with mean ~50.0. + EXPECT_THAT( + SummarizeSamples(absl::zipf_distribution<int>(100, 2.0, 1e16), 10000), + IsWithinBoundsWithMean(100, 50.0, 1.5)); +} + +TEST(ZipfDistributionTest, SqueezeThresholdIsSoundAndBounded) { + constexpr uint64_t kLargeK = 1000000000000000000ull; // 10^18 + + // Previously cancelled against xm_ (s_ = +1.0, false accept) or disabled the + // squeeze (s_ = -1.0, tail bias). + EXPECT_THAT(SqueezeThreshold(kLargeK, 2.0, 1e16), + IsSoundSqueezeNear(0.5, 1e-12)); + EXPECT_THAT(SqueezeThreshold(kLargeK, 1.05, 1e10), + IsSoundSqueezeNear(0.5, 1e-12)); + EXPECT_THAT(SqueezeThreshold(1000, 1.5, 1e-300), + IsSoundSqueezeNear(0.423020306144, 1e-11)); + EXPECT_THAT(SqueezeThreshold(1000, 1.0 + 1e-12, 1e-300), + IsSoundSqueezeNear(0.448180838243, 1e-11)); + EXPECT_THAT(SqueezeThreshold(1000, 1000.0, 1.0), + IsSoundSqueezeNear(0.012401048681, 1e-11)); + EXPECT_THAT(SqueezeThreshold(1000, 1e10, 1e100), + IsSoundSqueezeNear(0.5, 1e-12)); + EXPECT_THAT(SqueezeThreshold(0, 2.0, 1.0), AllOf(Ge(0.0), Lt(0.5))); +} + +TEST(ZipfDistributionTest, TailProbabilityAccurateAboveTwoToTheFiftyThree) { + constexpr uint64_t kLargeK = 1000000000000000000ull; // 10^18 + + // With s_ = +1.0 or s_ = -1.0, k >= 2^53 either falsely accepted everything + // or rejected ~50% of valid tail draws because k + 0.5 == k in double. + EXPECT_THAT(SummarizeTailFraction(zipf_u64(kLargeK, 2.0, 1e16), + uint64_t{10000000000000000ull}, 50000), + HasBoundedTailFraction(kLargeK, 0.495, 0.008)); + EXPECT_THAT(SummarizeTailFraction(zipf_u64(kLargeK, 1.05, 1e10), + uint64_t{1} << 58, 100000), + HasBoundedTailFraction(kLargeK, 0.04245, 0.003)); +} + +TEST(ZipfDistributionTest, TailIntegralInversionPreservesPrecisionNearZero) { + constexpr uint64_t kLargeK = 1000000000000000000ull; // 10^18 + const double q_min = std::nextafter(1.0, 2.0); + const double v_max = (std::numeric_limits<double>::max)(); + + // zm_ < -0.5 with x << v << xm_: previously inverted x = 0.5 to ~0.3701. + const zipf_u64 dist_zm_mid(kLargeK, 2.5, 1e15); + // zm_ >= -0.5 with d close to D(0). + const zipf_u64 dist_zm_high(kLargeK, 1.05, 1e15); + // zm_ < -708 with d close to D(0). + const zipf_u64 dist_zm_low(kLargeK, 100.0, 1e10); + // Linear limit (q * log_xm <= 1e-40) where zm or (q - 1) / v * delta would + // otherwise underflow to zero or a few-bit subnormal. + const zipf_u64 dist_linear_small(100, q_min, v_max); + const zipf_u64 dist_linear_large(1000000000000000ull, 1.0 + 5e-15, v_max); + + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_mid, 0.5), DoubleNear(0.5, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_mid, 1.0), DoubleNear(1.0, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_mid, 1.5), DoubleNear(1.5, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_mid, 2.0), DoubleNear(2.0, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_mid, 10.0), DoubleNear(10.0, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_high, 10.0), + DoubleNear(10.0, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_high, 100.0), + DoubleNear(100.0, 1e-9)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_low, 0.5), DoubleNear(0.5, 1e-6)); + EXPECT_THAT(TailIntegralRoundTrip(dist_zm_low, 1.5), DoubleNear(1.5, 1e-6)); + EXPECT_THAT(TailIntegralRoundTrip(dist_linear_small, 50.5), + DoubleNear(50.5, 1e-12)); + EXPECT_THAT(TailIntegralRoundTrip(dist_linear_large, 0.5), + DoubleNear(0.5, 1e-12)); + EXPECT_THAT(TailIntegralRoundTrip(dist_linear_large, 100.0), + DoubleNear(100.0, 1e-12)); +} + +TEST(ZipfDistributionTest, ZeroMassIsNotDoubleCountedBelowD0x5) { + constexpr uint64_t kLargeK = 1000000000000000000ull; // 10^18 + + // Exact P(X == 0) ~ 1.500047e-15 (~13.51 ULPs of w below 1.0). Previously, + // rounding x < 0.5 on the d < d0x5_ branch double-counted k = 0 (+12.5%). + EXPECT_THAT(ScanTopUniformGrid(zipf_u64(kLargeK, 2.5, 1e15), 64), + MatchesZeroMassWithoutDoubleCounting(1.500047364598e-15, 7e-17)); + // For q = 2.0, d0_ - d0x5_ rounds to 0.375, so d = d0x5_ - 0.125 inverts to + // x = 0.5 (rint(0.5) == 0); clamping k < 1 prevents double-counting k = 0. + EXPECT_THAT(ScanTopUniformGrid(zipf_u64(kLargeK, 2.0, 1e15), 64), + MatchesZeroMassWithoutDoubleCounting(1.000999999999e-15, 7e-17)); +} + +TEST(ZipfDistributionTest, SubnormalZmUsesLinearLimit) { + const double q_min = std::nextafter(1.0, 2.0); + const double v_max = (std::numeric_limits<double>::max)(); + + // Without the linear limit, (1, nextafter(1, 2), DBL_MAX) underflows zm to + // -0.0 and returns 0 unconditionally instead of uniform {0, 1}, while + // (100, nextafter(1, 2), DBL_MAX) quantizes zm to a 6-bit subnormal and + // distorts midpoint draws from 50 to 48. + EXPECT_THAT( + SummarizeSamples(absl::zipf_distribution<int>(1, q_min, v_max), 5000), + IsWithinBoundsWithMean(1, 0.5, 0.04)); + EXPECT_THAT( + SummarizeSamples(absl::zipf_distribution<int>(100, q_min, v_max), 5000), + IsWithinBoundsWithMean(100, 50.0, 2.0)); + EXPECT_THAT( + SampleFromSeedBits(absl::zipf_distribution<int>(100, q_min, v_max), + 0x8000000000000000ull), + Eq(50)); + EXPECT_THAT(DrawSamples(absl::zipf_distribution<int>(0, q_min, v_max), 50), + Each(0)); +} + +MATCHER_P2(IsRelativelyNear, expected, rel_tol, "") { + return std::abs(arg - expected) <= rel_tol * std::abs(expected); +} + +double ZipfParamRoundTrip(const ZipfParam& p, double x) { + return p.TailIntegralInv(p.TailIntegral(x)); +} + +TEST(ZipfParamTest, MaxIntegralDoubleLeMasksBitsBelowDoublePrecision) { + // Types and values that fit the 53-bit double significand are exact. + EXPECT_THAT(MaxIntegralDoubleLe(std::numeric_limits<int32_t>::max()), + Eq(2147483647.0)); + EXPECT_THAT(MaxIntegralDoubleLe(uint64_t{0}), Eq(0.0)); + EXPECT_THAT(MaxIntegralDoubleLe((uint64_t{1} << 53) - 1), + Eq(9007199254740991.0)); + // Wider values truncate toward zero rather than rounding to nearest, which + // would otherwise yield 2^63, 2^64, and 2^128. + EXPECT_THAT(MaxIntegralDoubleLe((uint64_t{1} << 53) + 1), + Eq(9007199254740992.0)); + EXPECT_THAT(MaxIntegralDoubleLe(std::numeric_limits<int64_t>::max()), + Eq(9223372036854774784.0)); + EXPECT_THAT(MaxIntegralDoubleLe(std::numeric_limits<uint64_t>::max()), + Eq(18446744073709549568.0)); + EXPECT_THAT(MaxIntegralDoubleLe(absl::Uint128Max()), + Eq(std::ldexp(9007199254740991.0, 75))); +} + +TEST(ZipfParamTest, QuadraticTailIntegralMatchesClosedFormAtZero) { + // q == 2: D(0) = v * xm / (v + xm). + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1e-300).TailIntegral(0.0), + IsRelativelyNear(1e-300, 1e-13)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 0.5).TailIntegral(0.0), + IsRelativelyNear(0.49975024975024973, 1e-13)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1.0).TailIntegral(0.0), + IsRelativelyNear(0.99900149775337, 1e-13)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1e16).TailIntegral(0.0), + IsRelativelyNear(1000.4999999999, 1e-13)); +} + +TEST(ZipfParamTest, QuadraticInversionReturnsZeroExactlyFromDZero) { + constexpr double kLargeK = 1e18; + + // TailIntegralInv(d) == 0 iff d >= D(0). For v = 1e-300 and xm ~ 1e18, + // v / (v + xm) is a 17-bit subnormal, so D(0) must not be derived from it. + EXPECT_THAT( + ZipfParam(kLargeK, 2.0, 1e-300).TailIntegralInv(1e-300 * (1.0 + 1e-9)), + Eq(0.0)); + EXPECT_THAT( + ZipfParam(kLargeK, 2.0, 1e-300).TailIntegralInv(1e-300 * (1.0 - 1e-9)), + Gt(0.0)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 0.5) + .TailIntegralInv(0.49975024975024973 * (1.0 + 1e-9)), + Eq(0.0)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 0.5) + .TailIntegralInv(0.49975024975024973 * (1.0 - 1e-9)), + Gt(0.0)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1e16) + .TailIntegralInv(1000.4999999999 * (1.0 + 1e-9)), + Eq(0.0)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1e16) + .TailIntegralInv(1000.4999999999 * (1.0 - 1e-9)), + Gt(0.0)); +} + +TEST(ZipfParamTest, QuadraticInversionMatchesClosedForm) { + constexpr double kLargeK = 1e18; + const double v_max = (std::numeric_limits<double>::max)(); + + // q == 2: x = 1 / (d / v^2 + 1 / (v + xm)) - v, evaluated to 700 digits. + // Covers v whose reciprocal is inexact (3, 0.1, 7), huge (1e-300), and + // subnormal (DBL_MAX). + EXPECT_THAT(ZipfParam(1000.0, 2.0, 3.0).TailIntegralInv(0.1), + IsRelativelyNear(79.5925925925926, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 3.0).TailIntegralInv(1.0), + IsRelativelyNear(5.92, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 3.0).TailIntegralInv(2.9), + IsRelativelyNear(0.09388006782796371, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 0.1).TailIntegralInv(0.01), + IsRelativelyNear(0.8990015974440896, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 0.1).TailIntegralInv(0.09), + IsRelativelyNear(0.011098774205009782, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1e-300).TailIntegralInv(5e-301), + IsRelativelyNear(1e-300, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 1e300).TailIntegralInv(500.0), + IsRelativelyNear(500.5, 1e-12)); + EXPECT_THAT(ZipfParam(1000.0, 2.0, v_max).TailIntegralInv(250.25), + IsRelativelyNear(750.25, 1e-12)); + EXPECT_THAT(ZipfParam(kLargeK, 2.0, 7.0).TailIntegralInv(1e-12), + IsRelativelyNear(48997599117636.234, 1e-12)); + EXPECT_THAT(ZipfParam(kLargeK, 2.0, 7.0).TailIntegralInv(3.5), + IsRelativelyNear(7.0, 1e-12)); +} + +TEST(ZipfParamTest, QuadraticInversionWithSubnormalV) { + // v = 1e-310 is subnormal and 1 / v overflows to +inf, so the inversion + // must divide by v rather than scale by a precomputed reciprocal, which + // would return 0 (or NaN at d == 0). P(X == 0) == 1 in double. + const ZipfParam subnormal_v(1000.0, 2.0, 1e-310); + EXPECT_THAT(subnormal_v.TailIntegralInv(5e-311), + IsRelativelyNear(1e-310, 1e-9)); + EXPECT_THAT(subnormal_v.TailIntegralInv(5e-324), + IsRelativelyNear(2.0240225330729937e-297, 1e-9)); + EXPECT_THAT(subnormal_v.TailIntegralInv(0.0), Eq(1000.5)); + EXPECT_THAT(DrawSamples(zipf_u64(1000, 2.0, 1e-310), 500), Each(0)); +} + +TEST(ZipfDistributionTest, QuadraticSamplingWithDegenerateParameters) { + // k == 0 and P(X == 0) == 1 in double: every draw returns 0. + EXPECT_THAT(DrawSamples(absl::zipf_distribution<int>(0, 2.0, 1.0), 200), + Each(0)); + EXPECT_THAT(DrawSamples(absl::zipf_distribution<int>(1, 2.0, 1e-300), 200), + Each(0)); + // Near-uniform over [0, 127]: 0 is rarely returned. + EXPECT_THAT( + DrawSamples(absl::zipf_distribution<int8_t>(127, 2.0, 1e300), 2000), + Each(AllOf(Ge(0), Le(127)))); +} + +TEST(ZipfParamTest, QuadraticTailIntegralRoundTrips) { + const ZipfParam tiny_v(1000.0, 2.0, 1e-300); + const ZipfParam small_v(1000.0, 2.0, 0.5); + const ZipfParam unit_v(1000.0, 2.0, 1.0); + const ZipfParam large_v(1000.0, 2.0, 1e16); + + EXPECT_THAT(ZipfParamRoundTrip(tiny_v, 1e-300), + IsRelativelyNear(1e-300, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(tiny_v, 1e-295), + IsRelativelyNear(1e-295, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(small_v, 0.5), IsRelativelyNear(0.5, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(small_v, 10.0), IsRelativelyNear(10.0, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(small_v, 500.0), + IsRelativelyNear(500.0, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(unit_v, 0.5), IsRelativelyNear(0.5, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(unit_v, 10.0), IsRelativelyNear(10.0, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(unit_v, 500.0), IsRelativelyNear(500.0, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(large_v, 0.5), IsRelativelyNear(0.5, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(large_v, 10.0), IsRelativelyNear(10.0, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(large_v, 500.0), + IsRelativelyNear(500.0, 1e-9)); +} + +TEST(ZipfParamTest, GeneralTailIntegralMatchesClosedFormForSmallV) { + // D(x) = v / (q - 1) * ((1 + x / v)^(1 - q) - (1 + xm / v)^(1 - q)), + // evaluated to 80 digits. + const ZipfParam small_v(1000.0, 3.5, 1e-3); + EXPECT_THAT(small_v.TailIntegral(0.0), + IsRelativelyNear(0.0003999999999999996, 1e-10)); + EXPECT_THAT(small_v.TailIntegral(0.5), + IsRelativelyNear(7.11976524558709e-11, 1e-10)); + EXPECT_THAT(small_v.TailIntegral(2.0), + IsRelativelyNear(2.2332749368948122e-12, 1e-10)); + EXPECT_THAT(small_v.TailIntegral(999.0), + IsRelativelyNear(1.5013102006029483e-21, 1e-10)); + EXPECT_THAT(small_v.TailIntegral(1000.5), Eq(0.0)); + + // v * (1 + x / v)^(1 - q) ~ 8.7e-309 is subnormal while D(x) is not. + EXPECT_THAT(ZipfParam(1e18, 1.01, 1e-305).TailIntegral(10.0), + IsRelativelyNear(2.8211993460048987e-307, 1e-10)); +} + +TEST(ZipfParamTest, GeneralInversionRoundTripsWhenExpZmUnderflows) { + // zm ~ -1823 < -708 and d < D(0) / 2: log(exp(zm) + b) is evaluated in log + // space. + const ZipfParam steep(1e18, 100.0, 1e10); + EXPECT_THAT(ZipfParamRoundTrip(steep, 1e9), IsRelativelyNear(1e9, 1e-9)); + EXPECT_THAT(ZipfParamRoundTrip(steep, 1e12), IsRelativelyNear(1e12, 1e-9)); +} + +TEST(ZipfParamTest, AcceptsHatSqueezeMissMatchesExactThreshold) { + // Accepts iff d <= D(k + 0.5) + f(k), with f(k) = (1 + k / v)^(-q). + // q == 2, v == 1, k == 1: (1 / 2.5 - 1 / 11.5) + 1 / 4. + const ZipfParam quadratic(10.0, 2.0, 1.0); + EXPECT_THAT( + quadratic.AcceptsHatSqueezeMiss(1.0, 0.5630434782608695 * (1.0 - 1e-9)), + Eq(true)); + EXPECT_THAT( + quadratic.AcceptsHatSqueezeMiss(1.0, 0.5630434782608695 * (1.0 + 1e-9)), + Eq(false)); + // k == max_kd: D(k + 0.5) == 0, leaving f(10) = 1 / 121. + EXPECT_THAT(quadratic.AcceptsHatSqueezeMiss( + 10.0, 0.008264462809917356 * (1.0 - 1e-9)), + Eq(true)); + EXPECT_THAT(quadratic.AcceptsHatSqueezeMiss( + 10.0, 0.008264462809917356 * (1.0 + 1e-9)), + Eq(false)); + // q == 3, v == 0.5, k == 3: 0.25 * (1 / 64 - 1 / 484) + 1 / 343. + const ZipfParam cubic(10.0, 3.0, 0.5); + EXPECT_THAT( + cubic.AcceptsHatSqueezeMiss(3.0, 0.0063051729694238974 * (1.0 - 1e-9)), + Eq(true)); + EXPECT_THAT( + cubic.AcceptsHatSqueezeMiss(3.0, 0.0063051729694238974 * (1.0 + 1e-9)), + Eq(false)); +} + +TEST(ZipfParamTest, TailIntegralInvStaysWithinDomainForTinyD) { + constexpr double kMinPos = std::numeric_limits<double>::denorm_min(); + // Exercises all TailIntegralInv paths where rounding at d -> 0+ can + // otherwise exceed xm = max_kd + 0.5 by a few ULPs. + EXPECT_THAT(ZipfParam(10.0, 10.0, 100.0).TailIntegralInv(kMinPos), + AllOf(Ge(0.0), Le(10.5))); + EXPECT_THAT(ZipfParam(100.0, 1.5, 0.1).TailIntegralInv(kMinPos), + AllOf(Ge(0.0), Le(100.5))); + EXPECT_THAT(ZipfParam(1000.0, 2.0, 200.0).TailIntegralInv(kMinPos), + AllOf(Ge(0.0), Le(1000.5))); + EXPECT_THAT(ZipfParam(1e12, 100.0, 1e4).TailIntegralInv(kMinPos), + Eq(1e12 + 0.5)); +} + MATCHER(FailsLeavingUnchanged, "fails stream extraction and leaves target and stream flags " "unchanged") {