Fix overflow, tiny-mean, and cancellation bugs in absl::poisson_distribution. * Avoid integer overflow UB and `uint64_t` wraparound in Knuth / split-Knuth sampling by checking `r <= p.emu_` before incrementing `result_type n` and clamping immediately at `(max)()`. This prevents signed overflow UB on narrow types (`int8_t`), wraparound on `uint64_t` / `absl::uint128`, and redundant draws once saturated. * Sample tiny means (`mean < 1e-4`, including `mean == 0.0`) via exact `bernoulli_distribution(-std::expm1(-mean))` and Poisson arrival-time thinning (`rem = std::log1p(v * std::expm1(rem))`). Previously `std::exp(-mean)` rounded to `>= 1 - 2^-53` for all `0 < mean < 1.665e-16`, returning `0` identically. * Eliminate catastrophic `O(mean * ln(mean))` cancellation in Stadlober's ratio-of-uniforms acceptance test by evaluating `ln(P(X = x) / P(X = mode)) = g(x, mean) - g(mode, mean)` out-of-line in `poisson_distribution.cc` via `StirlingLogFactorialRemainder` and an exact small-`x` (`0..19`) log-factorial table, using a cancellation-free series in `y = (x - mean) / (x + mean)` for `|y| <= 0.1` and splitting `floor(s * v / u + a_frac) + a_int`. This fixes mode acceptance clipping and mean bias at `mean = 1e10`, and raises the supported `mean` cap to `1e15` (within IEEE-754 `double`'s exact integer range `< 2^53`). * Use `x >= static_cast<double>((max)())` when `IntType` has more precision bits than `double` (`int64_t`, `uint64_t`, `absl::int128`, `absl::uint128`), avoiding `[conv.fpint]` UB when `static_cast<double>((max)())` rounds up to a power of two. PiperOrigin-RevId: 1022528503
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 253898d..4b877d3 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -268,6 +268,7 @@ "random/internal/uniform_helper.h" "random/internal/wide_multiply.h" "random/log_uniform_int_distribution.h" + "random/poisson_distribution.cc" "random/poisson_distribution.h" "random/random.h" "random/seed_gen_exception.cc"
diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 42b59d3..2cd527d 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel
@@ -58,6 +58,7 @@ srcs = [ "discrete_distribution.cc", "gaussian_distribution.cc", + "poisson_distribution.cc", ], hdrs = [ "bernoulli_distribution.h",
diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index b2c3fa2..5566960 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt
@@ -186,6 +186,7 @@ SRCS "discrete_distribution.cc" "gaussian_distribution.cc" + "poisson_distribution.cc" HDRS "bernoulli_distribution.h" "beta_distribution.h"
diff --git a/absl/random/internal/fastmath.h b/absl/random/internal/fastmath.h index 8f4f356..d6170e8 100644 --- a/absl/random/internal/fastmath.h +++ b/absl/random/internal/fastmath.h
@@ -51,6 +51,18 @@ (1.0 / 360.0) * ninv * ninv * ninv; } +// Returns the Stirling asymptotic remainder: +// ln(n!) - ((n + 0.5) * ln(n) - n + 0.5 * ln(2*pi)) +// For n >= 20, the 4-term series is accurate to < 2e-15. +inline double StirlingLogFactorialRemainder(double n) { + assert(n >= 1); + const double inv = 1.0 / n; + const double inv2 = inv * inv; + return inv * ((1.0 / 12.0) - + inv2 * ((1.0 / 360.0) - + inv2 * ((1.0 / 1260.0) - inv2 * (1.0 / 1680.0)))); +} + } // namespace random_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/random/internal/fastmath_test.cc b/absl/random/internal/fastmath_test.cc index cd33d7a..89f22f1 100644 --- a/absl/random/internal/fastmath_test.cc +++ b/absl/random/internal/fastmath_test.cc
@@ -95,4 +95,51 @@ } } +TEST(FastMathTest, StirlingLogFactorialRemainder) { + using absl::random_internal::StirlingLogFactorialRemainder; + + // High-precision reference values of + // R(n) = ln(n!) - ((n + 0.5) * ln(n) - n + 0.5 * ln(2*pi)) + // verifying the documented < 2e-15 accuracy bound for n >= 20 without + // cancellation in std::lgamma. + EXPECT_NEAR(StirlingLogFactorialRemainder(20.0), 4.16631969199692246e-3, + 2e-15); + EXPECT_NEAR(StirlingLogFactorialRemainder(25.0), 3.33315563672809288e-3, + 2e-15); + EXPECT_NEAR(StirlingLogFactorialRemainder(50.0), 1.66664444698336551e-3, + 2e-15); + EXPECT_NEAR(StirlingLogFactorialRemainder(100.0), 8.33330555634914683e-4, + 2e-15); + EXPECT_NEAR(StirlingLogFactorialRemainder(1000.0), 8.33333305555563492e-5, + 2e-15); + + // Cancellation-free positive telescoping check across k = 20..99: + // R(k) - R(k + 1) = (k + 0.5) * ln((k + 1) / k) - 1 + // = sum_{m >= 1} 1 / ((2m + 1) * (2k + 1)^(2m)). + for (int k = 20; k < 100; ++k) { + const double d = static_cast<double>(k); + const double z = 1.0 / (2.0 * d + 1.0); + const double z2 = z * z; + double expected_diff = 0.0; + double z_pow = z2; + for (int m = 1; m <= 6; ++m) { + expected_diff += z_pow / static_cast<double>(2 * m + 1); + z_pow *= z2; + } + EXPECT_NEAR( + StirlingLogFactorialRemainder(d) - StirlingLogFactorialRemainder(d + 1), + expected_diff, 2e-15); + } + + // Cross-check against std::lgamma with tolerance wide enough for ~44 bits of + // cancellation in std::lgamma(d + 1) - (d + 0.5) * std::log(d). + constexpr double kLog2PI = 1.83787706640934548356; + for (int i = 20; i < 100; ++i) { + const double d = static_cast<double>(i); + const double expected = + std::lgamma(d + 1.0) - ((d + 0.5) * std::log(d) - d + 0.5 * kLog2PI); + EXPECT_NEAR(StirlingLogFactorialRemainder(d), expected, 1e-12); + } +} + } // namespace
diff --git a/absl/random/poisson_distribution.cc b/absl/random/poisson_distribution.cc new file mode 100644 index 0000000..0e5b234 --- /dev/null +++ b/absl/random/poisson_distribution.cc
@@ -0,0 +1,87 @@ +// 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/poisson_distribution.h" + +#include <cassert> +#include <cmath> + +#include "absl/base/config.h" +#include "absl/random/internal/fastmath.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +double PoissonLogRatioTerm(double x, double d, double mean) { + const double s = x + mean; + const double y = d / s; + const double rem = StirlingLogFactorialRemainder(x); + if (std::abs(y) <= 0.1) { + // Use ln(mean / x) = -2 * (y + y^3/3 + y^5/5 + ...), where the linear + // terms in (x + 0.5) * ln(mean / x) + (x - mean) cancel algebraically: + // -(d + 1) * y - (2 * x + 1) * y^3 * (1/3 + y^2/5 + ...). + // For |y| <= 0.1, the omitted inner series remainder is + // < 0.1^17 / (17 * 0.99) < 1e-18, giving relative truncation error + // < 1e-16 (< 0.5 ULP) in g(x, mean) after scaling by 2 * x + 1. + const double y2 = y * y; + const double poly = + (1.0 / 3.0) + + y2 * ((1.0 / 5.0) + + y2 * ((1.0 / 7.0) + + y2 * ((1.0 / 9.0) + + y2 * ((1.0 / 11.0) + + y2 * ((1.0 / 13.0) + y2 * (1.0 / 15.0)))))); + return -(d + 1.0) * y - (s + d + 1.0) * (y * y2) * poly - rem; + } + return (x + 0.5) * std::log(mean / x) + d - rem; +} + +double PoissonLogRatio(double x, double d, double mean, double lmu, + double g_mode) { + assert(x >= 0.0); + if (x < 20.0) { + // Exact ln(k!) for k = 0..19. + static constexpr double kLogFactorial[20] = { + 0.0, + 0.0, + 0.69314718055994530942, + 1.79175946922805500081, + 3.17805383034794561965, + 4.78749174278204599425, + 6.57925121201010099506, + 8.52516136106541430017, + 10.60460290274525022842, + 12.80182748008146961121, + 15.10441257307551529523, + 17.50230784587388583929, + 19.98721449566188614952, + 22.55216385312342288557, + 25.19122118273868150009, + 27.89927138384089156609, + 30.67186010608067280376, + 33.50507345013688888401, + 36.39544520803305357622, + 39.33988418719949403622, + }; + constexpr double kLog2PI = 1.83787706640934548356; + return x * lmu - mean - kLogFactorial[static_cast<int>(x)] + + 0.5 * (kLog2PI + lmu) - g_mode; + } + return PoissonLogRatioTerm(x, d, mean) - g_mode; +} + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/random/poisson_distribution.h b/absl/random/poisson_distribution.h index ae2e095..8c0ed1d 100644 --- a/absl/random/poisson_distribution.h +++ b/absl/random/poisson_distribution.h
@@ -23,14 +23,34 @@ #include <ostream> #include "absl/base/config.h" +#include "absl/random/bernoulli_distribution.h" #include "absl/random/internal/fast_uniform_bits.h" -#include "absl/random/internal/fastmath.h" #include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" #include "absl/random/internal/traits.h" namespace absl { ABSL_NAMESPACE_BEGIN +namespace random_internal { + +// Ratio-of-uniforms computes variates in IEEE-754 `double`, which represents +// consecutive integers exactly up to 2^53 (~9e15). Cap `mean` at 1e15 so that +// variates around `mean` preserve unit integer resolution. +inline constexpr double kPoissonMaxMean = 1e15; + +// Computes g(x, mean) = (x + 0.5) * ln(mean / x) + (x - mean) - R(x), where +// d = x - mean and R(x) is the Stirling log-factorial remainder. Because +// ln(P(X = x)) = g(x, mean) - 0.5 * ln(2 * pi * mean), the difference +// g(x, mean) - g(mode, mean) equals ln(P(X = x) / P(X = mode)) without +// subtracting large O(mean * ln(mean)) terms. +double PoissonLogRatioTerm(double x, double d, double mean); + +// Computes ln(P(X = x) / P(X = mode)) for integer x >= 0, given d = x - mean, +// lmu = ln(mean), and g_mode = PoissonLogRatioTerm(mode, mode - mean, mean). +double PoissonLogRatio(double x, double d, double mean, double lmu, + double g_mode); + +} // namespace random_internal // absl::poisson_distribution: // Generates discrete variates conforming to a Poisson distribution. @@ -76,11 +96,11 @@ friend class poisson_distribution; double mean_; - double emu_; // e ^ -mean_ + double emu_; // exp(-mean_) for Knuth, -expm1(-mean_) for tiny mean double lmu_; // ln(mean_) double s_; double log_k_; - int split_; + int split_; // -1: tiny mean, 0: ratio-of-uniforms, >0: Knuth splits static_assert(random_internal::IsIntegral<IntType>::value, "Class-template absl::poisson_distribution<> must be " @@ -133,15 +153,18 @@ template <typename IntType> poisson_distribution<IntType>::param_type::param_type(double mean) - : mean_(mean), split_(0) { + : mean_(mean), emu_(0.0), lmu_(0.0), s_(0.0), log_k_(0.0), split_(0) { assert(mean >= 0); assert(mean <= static_cast<double>((std::numeric_limits<result_type>::max)())); - // As a defensive measure, avoid large values of the mean. The rejection - // algorithm used does not support very large values well. It my be worth - // changing algorithms to better deal with these cases. - assert(mean <= 1e10); - if (mean_ < 10) { + assert(mean <= random_internal::kPoissonMaxMean); + if (mean_ < 1e-4) { + // For tiny lambda, exp(-lambda) loses relative precision near 1.0 (and + // rounds to >= 1 - 2^-53 for lambda < 1.665e-16). Use exact Bernoulli + + // arrival-time thinning via -expm1(-lambda). + split_ = -1; + emu_ = -std::expm1(-mean_); + } else if (mean_ < 10) { // For small lambda, use the knuth method. split_ = 1; emu_ = std::exp(-mean_); @@ -157,8 +180,8 @@ lmu_ = std::log(mean_); double a = mean_ + 0.5; s_ = kSA + std::sqrt(k2E * a); - const double mode = std::ceil(mean_) - 1; - log_k_ = lmu_ * mode - absl::random_internal::StirlingLogFactorial(mode); + const double mode = std::ceil(mean_) - 1.0; + log_k_ = random_internal::PoissonLogRatioTerm(mode, mode - mean_, mean_); } } @@ -172,10 +195,32 @@ using random_internal::GenerateRealFromBits; using random_internal::GenerateSignedTag; - if (p.split_ != 0) { + if (p.split_ < 0) { + // Exact Poisson sampling for tiny mean (< 1e-4) via arrival-time thinning: + // P(X >= 1) = 1 - exp(-mean) = -expm1(-mean). Conditional on X >= 1, the + // first arrival time T1 satisfies rem = mean - T1 = log1p(V * expm1(mean)) + // for V ~ Uniform[0, 1), and (X - 1 | T1) ~ Poisson(rem). + if (p.mean_ == 0.0) return 0; + const result_type max_n = (max)(); + result_type n = 0; + double rem = p.mean_; + double prob = p.emu_; + while (bernoulli_distribution(prob)(g)) { + ++n; + if (n == max_n) return max_n; + const double v = + GenerateRealFromBits<double, GeneratePositiveTag, true>(fast_u64_(g)); + rem = std::log1p(v * std::expm1(rem)); + if (rem == 0.0) break; + prob = -std::expm1(-rem); + } + return n; + } + + if (p.split_ > 0) { // Use Knuth's algorithm with range splitting to avoid floating-point // errors. Knuth's algorithm is: Ui is a sequence of uniform variates on - // (0,1); return the number of variates required for product(Ui) < + // [0, 1); return the number of variates required for product(Ui) <= // exp(-lambda). // // The expected number of variates required for Knuth's method can be @@ -186,15 +231,17 @@ // lambda = [2, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17] // n = [3, 8, 13, 15, 16, 18, 19, 21, 22, 24, 25] // + const result_type max_n = (max)(); result_type n = 0; for (int split = p.split_; split > 0; --split) { double r = 1.0; - do { + for (;;) { r *= GenerateRealFromBits<double, GeneratePositiveTag, true>( - fast_u64_(g)); // U(-1, 0) + fast_u64_(g)); // U[0, 1) + if (r <= p.emu_) break; ++n; - } while (r > p.emu_); - --n; + if (n == max_n) return max_n; + } } return n; } @@ -208,26 +255,31 @@ // P(floor(x) = k | u^2 < f(floor(x))/k), where // f(m) = lambda^m exp(-lambda)/ m!, for 0 <= m, and f(m) = 0 otherwise, // and k = max(f). - const double a = p.mean_ + 0.5; + const double a_int = std::floor(p.mean_); + const double mean_frac = p.mean_ - a_int; + const double a_frac = mean_frac + 0.5; for (;;) { const double u = GenerateRealFromBits<double, GeneratePositiveTag, false>( fast_u64_(g)); // U(0, 1) const double v = GenerateRealFromBits<double, GenerateSignedTag, false>( fast_u64_(g)); // U(-1, 1) - const double x = std::floor(p.s_ * v / u + a); + const double dx = std::floor(p.s_ * v / u + a_frac); + const double x = a_int + dx; if (x < 0) continue; // f(negative) = 0 - const double rhs = x * p.lmu_; - // clang-format off - double s = (x <= 1.0) ? 0.0 - : (x == 2.0) ? 0.693147180559945 - : absl::random_internal::StirlingLogFactorial(x); - // clang-format on - const double lhs = 2.0 * std::log(u) + p.log_k_ + s; - if (lhs < rhs) { - return x > static_cast<double>((max)()) - ? (max)() - : static_cast<result_type>(x); // f(x)/k >= u^2 + const double d = dx - mean_frac; + if (2.0 * std::log(u) < + random_internal::PoissonLogRatio(x, d, p.mean_, p.lmu_, p.log_k_)) { + constexpr double kMax = + static_cast<double>((std::numeric_limits<result_type>::max)()); + if constexpr (std::numeric_limits<result_type>::digits > + std::numeric_limits<double>::digits) { + // For integers wider than double's significand (e.g. 64-bit, 128-bit), + // kMax rounds up to a power of two, which is one past (max)(). + return x >= kMax ? (max)() : static_cast<result_type>(x); + } else { + return x > kMax ? (max)() : static_cast<result_type>(x); + } } } }
diff --git a/absl/random/poisson_distribution_test.cc b/absl/random/poisson_distribution_test.cc index e8ee364..fa5d6a7 100644 --- a/absl/random/poisson_distribution_test.cc +++ b/absl/random/poisson_distribution_test.cc
@@ -18,11 +18,13 @@ #include <cmath> #include <cstddef> #include <cstdint> +#include <initializer_list> #include <iterator> #include <limits> #include <random> #include <sstream> #include <string> +#include <utility> #include <vector> #include "gmock/gmock.h" @@ -80,7 +82,7 @@ TYPED_TEST(PoissonDistributionInterfaceTest, SerializeTest) { using param_type = typename absl::poisson_distribution<TypeParam>::param_type; const double kMax = - std::min(1e10 /* assertion limit */, + std::min(1e15 /* assertion limit */, static_cast<double>(std::numeric_limits<TypeParam>::max())); const double kParams[] = { @@ -568,4 +570,263 @@ EXPECT_EQ(121, dist(urbg)); } +TEST(PoissonDistributionTest, NarrowIntKnuthClampsWithoutOverflow) { + // sequence_urbg returning all-ones produces U ~ 1.0 - 2^-53 > exp(-mean/6), + // forcing Knuth accumulation past int8_t::max() (127) and uint8_t::max() + // (255). Previously ++n overflowed int8_t (UB) and wrapped modulo 256. + absl::random_internal::sequence_urbg max_urbg({~uint64_t{0}}); + absl::poisson_distribution<int8_t> dist_i8(50.0); + EXPECT_EQ(dist_i8(max_urbg), (std::numeric_limits<int8_t>::max)()); + + absl::poisson_distribution<uint8_t> dist_u8(50.0); + EXPECT_EQ(dist_u8(max_urbg), (std::numeric_limits<uint8_t>::max)()); + + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + for (int i = 0; i < 5000; ++i) { + const int8_t v = dist_i8(rng); + EXPECT_GE(v, 0); + EXPECT_LE(v, (std::numeric_limits<int8_t>::max)()); + } +} + +TEST(PoissonDistributionTest, Uint64KnuthSamplesAccurately) { + using testing::DoubleNear; + using testing::Eq; + using testing::Gt; + + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + const auto sample_mean = [&rng](double mean, size_t samples) { + absl::poisson_distribution<uint64_t> dist(mean); + double sum = 0.0; + for (size_t i = 0; i < samples; ++i) { + sum += static_cast<double>(dist(rng)); + } + return sum / static_cast<double>(samples); + }; + + EXPECT_THAT(sample_mean(0.0, 1000), Eq(0.0)); + // Regression for uint64_t wraparound of `max_n + 1` in Knuth/split-Knuth. + EXPECT_THAT(sample_mean(1.0, 20000), DoubleNear(1.0, 0.05)); + EXPECT_THAT(sample_mean(5.0, 20000), DoubleNear(5.0, 0.1)); + EXPECT_THAT(sample_mean(20.0, 20000), DoubleNear(20.0, 0.2)); + EXPECT_THAT(sample_mean(50.0, 20000), DoubleNear(50.0, 0.3)); + + absl::poisson_distribution<uint64_t> dist_one(1.0); + uint64_t max_seen = 0; + for (int i = 0; i < 100; ++i) { + max_seen = std::max(max_seen, dist_one(rng)); + } + EXPECT_THAT(max_seen, Gt(0u)); +} + +TEST(PoissonDistributionTest, TinyMeanGeneratesNonZeroSamples) { + using testing::DoubleNear; + using testing::Eq; + using testing::Gt; + + const auto sample_with_seq = [](auto tag, double mean, + std::initializer_list<uint64_t> seq) { + using IntType = decltype(tag); + absl::random_internal::sequence_urbg urbg(seq); + absl::poisson_distribution<IntType> dist(mean); + return dist(urbg); + }; + + // mean == 0.0 always produces 0. + EXPECT_THAT(sample_with_seq(int{}, 0.0, {0ULL}), Eq(0)); + + // Previously all 0 < mean < 1.665e-16 produced 0 identically because + // exp(-mean) rounded to >= 1 - 2^-53. + EXPECT_THAT(sample_with_seq(int{}, 1e-18, {0ULL}), Eq(1)); + EXPECT_THAT(sample_with_seq(uint64_t{}, 1e-20, {0ULL}), Eq(1)); + EXPECT_THAT(sample_with_seq( + int64_t{}, std::numeric_limits<double>::denorm_min(), {0ULL}), + Eq(1)); + EXPECT_THAT(sample_with_seq(uint64_t{}, 1e-20, {~uint64_t{0}}), Eq(0)); + + // Verify X >= 2 is reachable with exact thinning (not truncated to {0, 1}): + // three 0s accept bernoulli(1e-20); 0x8000... sets v=0.5 -> rem=0.5e-20; + // three 0s accept bernoulli(0.5e-20); final 0 sets v=0 -> rem=0 and stops. + EXPECT_THAT(sample_with_seq(uint64_t{}, 1e-20, + {0ULL, 0ULL, 0ULL, 0x8000000000000000ULL, 0ULL, + 0ULL, 0ULL, 0ULL}), + Eq(2u)); + + // Statistical rate check inside the tiny-mean path (< 1e-4). + constexpr double kTinyMean = 5e-5; + constexpr size_t kSamples = 1000000; + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + absl::poisson_distribution<int> dist(kTinyMean); + size_t sum = 0; + size_t nonzero = 0; + for (size_t i = 0; i < kSamples; ++i) { + const int x = dist(rng); + EXPECT_GE(x, 0); + sum += static_cast<size_t>(x); + if (x > 0) ++nonzero; + } + EXPECT_THAT(nonzero, Gt(0u)); + EXPECT_THAT(static_cast<double>(sum) / static_cast<double>(kSamples), + DoubleNear(kTinyMean, 2.5e-5)); +} + +TEST(PoissonDistributionTest, LargeMeanModeAcceptanceNotClipped) { + using testing::Pair; + + // u = 1 - 2^-53 (~0ULL) and v = +2^-64 (0ULL) proposes x = mean (a mode for + // integer mean). Without cancellation-free log-ratio evaluation, u near 1.0 + // was clipped/rejected at mean = 1e10. + constexpr uint64_t kUMax = ~uint64_t{0}; + const auto draw_seq = [](double mean, std::initializer_list<uint64_t> seq) { + absl::random_internal::sequence_urbg urbg(seq); + absl::poisson_distribution<int64_t> dist(mean); + const int64_t sample = dist(urbg); + return std::make_pair(sample, urbg.invocations()); + }; + + EXPECT_THAT(draw_seq(1e10, {kUMax, 0ULL}), + Pair(int64_t{10000000000LL}, size_t{2})); + // v = -2^-17 shifts dx to -1, proposing the other integer mode (mean - 1). + constexpr uint64_t kNegPow2Minus17 = + (uint64_t{1} << 63) | (uint64_t{1} << (63 - 17)); + EXPECT_THAT(draw_seq(1e10, {kUMax, kNegPow2Minus17}), + Pair(int64_t{9999999999LL}, size_t{2})); + EXPECT_THAT(draw_seq(1e12, {kUMax, 0ULL}), + Pair(int64_t{1000000000000LL}, size_t{2})); + EXPECT_THAT(draw_seq(1e15, {kUMax, 0ULL}), + Pair(int64_t{1000000000000000LL}, size_t{2})); + + // Fractional means (mean_frac != 0) have unique mode floor(mean) = ceil(mean) + // - 1. Verify a_int, mean_frac, a_frac = mean_frac + 0.5, d = dx - mean_frac, + // and non-integer mode acceptance near both ends of the ratio-of-uniforms + // range. + constexpr uint64_t kNegPow2Minus25 = + (uint64_t{1} << 63) | (uint64_t{1} << (63 - 25)); + constexpr uint64_t kNegPow2Minus2 = + (uint64_t{1} << 63) | (uint64_t{1} << (63 - 2)); + const double kMaxFracMean = std::nextafter(1e15, 0.0); + + // For mean = 51.5 (a_frac = 1.0, mode = 51), v = -2^-25 proposes dx = 0 + // (x = 51, accepted), whereas v = +2^-64 proposes dx = +1 (x = 52) and + // v = -0.25 proposes dx = -1 (x = 50), both rejected at u = 1 - 2^-53. + EXPECT_THAT(draw_seq(51.5, {kUMax, kNegPow2Minus25}), + Pair(int64_t{51}, size_t{2})); + EXPECT_THAT(draw_seq(51.5, {kUMax, 0ULL, kUMax, kNegPow2Minus25}), + Pair(int64_t{51}, size_t{4})); + EXPECT_THAT(draw_seq(51.5, {kUMax, kNegPow2Minus2, kUMax, kNegPow2Minus25}), + Pair(int64_t{51}, size_t{4})); + + // For mean = 1e10 + 0.375 (a_frac = 0.875, mode = 1e10), v = +2^-64 proposes + // dx = 0 (x = 1e10, accepted). + EXPECT_THAT(draw_seq(1e10 + 0.375, {kUMax, 0ULL}), + Pair(int64_t{10000000000LL}, size_t{2})); + + // For mean = nextafter(1e15, 0) = 999999999999999.875 (a_frac = 1.375, + // mode = 999999999999999), v = -2^-25 proposes dx = 0 (mode, accepted). + EXPECT_THAT(draw_seq(kMaxFracMean, {kUMax, kNegPow2Minus25}), + Pair(int64_t{999999999999999LL}, size_t{2})); +} + +TEST(PoissonDistributionTest, LargeMeanUnbiasedMoments) { + using testing::DoubleNear; + using testing::Lt; + using testing::Pair; + + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL); + const auto check_large_mean = [&rng](double mean) { + constexpr size_t kSamples = 100000; + absl::poisson_distribution<int64_t> dist(mean); + std::vector<double> offsets; + offsets.reserve(kSamples); + for (size_t i = 0; i < kSamples; ++i) { + offsets.push_back(static_cast<double>(dist(rng)) - mean); + } + const auto m = absl::random_internal::ComputeDistributionMoments(offsets); + const double z = std::abs(absl::random_internal::ZScore(0.0, m)); + return std::make_pair(z, m.variance); + }; + + const double kMaxFracMean = std::nextafter(1e15, 0.0); + EXPECT_THAT(check_large_mean(51.5), + Pair(Lt(4.0), DoubleNear(51.5, 51.5 * 0.02))); + EXPECT_THAT(check_large_mean(1e10), + Pair(Lt(4.0), DoubleNear(1e10, 1e10 * 0.02))); + EXPECT_THAT(check_large_mean(1e10 + 0.375), + Pair(Lt(4.0), DoubleNear(1e10 + 0.375, (1e10 + 0.375) * 0.02))); + EXPECT_THAT(check_large_mean(1e12), + Pair(Lt(4.0), DoubleNear(1e12, 1e12 * 0.02))); + EXPECT_THAT(check_large_mean(1e15), + Pair(Lt(4.0), DoubleNear(1e15, 1e15 * 0.02))); + EXPECT_THAT(check_large_mean(kMaxFracMean), + Pair(Lt(4.0), DoubleNear(kMaxFracMean, kMaxFracMean * 0.02))); +} + +TEST(PoissonDistributionTest, LogRatioAccuracyAtBoundaryAndLargeMean) { + using testing::DoubleNear; + + const auto eval_log_ratio = [](double x, double mean) { + const double mode = std::ceil(mean) - 1.0; + const double g_mode = + absl::random_internal::PoissonLogRatioTerm(mode, mode - mean, mean); + return absl::random_internal::PoissonLogRatio(x, x - mean, mean, + std::log(mean), g_mode); + }; + + // Exact check at x = 0, 1, 19, 20 for mean = 51.0 (mode = 50). + const auto exact_ratio = [](double x, double mean) { + const double mode = std::ceil(mean) - 1.0; + return (x - mode) * std::log(mean) - + (std::lgamma(x + 1.0) - std::lgamma(mode + 1.0)); + }; + EXPECT_THAT(eval_log_ratio(0.0, 51.0), + DoubleNear(exact_ratio(0.0, 51.0), 1e-12)); + EXPECT_THAT(eval_log_ratio(1.0, 51.0), + DoubleNear(exact_ratio(1.0, 51.0), 1e-12)); + EXPECT_THAT(eval_log_ratio(19.0, 51.0), + DoubleNear(exact_ratio(19.0, 51.0), 1e-12)); + EXPECT_THAT(eval_log_ratio(20.0, 51.0), + DoubleNear(exact_ratio(20.0, 51.0), 1e-12)); + + // Both modes (mean - 1 and mean) have log-ratio 0 at large integer mean. + EXPECT_THAT(eval_log_ratio(1e10 - 1.0, 1e10), DoubleNear(0.0, 1e-14)); + EXPECT_THAT(eval_log_ratio(1e10, 1e10), DoubleNear(0.0, 1e-14)); + EXPECT_THAT(eval_log_ratio(1e12, 1e12), DoubleNear(0.0, 1e-14)); + EXPECT_THAT(eval_log_ratio(1e15, 1e15), DoubleNear(0.0, 1e-14)); + + // Fractional mean = 51.5 (mode = 51): check small-x table boundary and + // cancellation-free log-ratios around the unique mode. + EXPECT_THAT(eval_log_ratio(0.0, 51.5), + DoubleNear(exact_ratio(0.0, 51.5), 1e-12)); + EXPECT_THAT(eval_log_ratio(19.0, 51.5), + DoubleNear(exact_ratio(19.0, 51.5), 1e-12)); + EXPECT_THAT(eval_log_ratio(20.0, 51.5), + DoubleNear(exact_ratio(20.0, 51.5), 1e-12)); + EXPECT_THAT(eval_log_ratio(50.0, 51.5), + DoubleNear(std::log(51.0 / 51.5), 1e-14)); + EXPECT_THAT(eval_log_ratio(51.0, 51.5), DoubleNear(0.0, 1e-14)); + EXPECT_THAT(eval_log_ratio(52.0, 51.5), + DoubleNear(std::log(51.5 / 52.0), 1e-14)); + + // Large fractional means: check exact mode and +/-1 adjacent ratios via + // cancellation-free log1p. + constexpr double kFracMean1e10 = 1e10 + 0.375; + EXPECT_THAT(eval_log_ratio(1e10 - 1.0, kFracMean1e10), + DoubleNear(std::log1p(-0.375 / kFracMean1e10), 1e-14)); + EXPECT_THAT(eval_log_ratio(1e10, kFracMean1e10), DoubleNear(0.0, 1e-14)); + EXPECT_THAT(eval_log_ratio(1e10 + 1.0, kFracMean1e10), + DoubleNear(std::log1p(-0.625 / (1e10 + 1.0)), 1e-14)); + + const double kMaxFracMean = std::nextafter(1e15, 0.0); + const double kMaxFracMode = std::ceil(kMaxFracMean) - 1.0; + const double kMaxFracPart = kMaxFracMean - kMaxFracMode; + EXPECT_THAT(eval_log_ratio(kMaxFracMode - 1.0, kMaxFracMean), + DoubleNear(std::log1p(-kMaxFracPart / kMaxFracMean), 1e-17)); + EXPECT_THAT(eval_log_ratio(kMaxFracMode, kMaxFracMean), + DoubleNear(0.0, 1e-17)); + EXPECT_THAT( + eval_log_ratio(kMaxFracMode + 1.0, kMaxFracMean), + DoubleNear(std::log1p((kMaxFracPart - 1.0) / (kMaxFracMode + 1.0)), + 1e-17)); +} + } // namespace