Fix `discrete_distribution` normalization, aliasing, and range overflow.
* Add a defensive `{1.0}` fallback for all-zero weight vectors (violating
`[rand.dist.samp.discrete]`'s `S > 0` precondition) instead of dividing
`0.0 / 0.0` (`NaN`), and pre-scale by the maximum weight when finite weights
overflow `double` summation (normalizing whenever the rescaled sum differs
from `1.0`).
* Accumulate weights with Neumaier compensated summation (in both the initial
and overflow-rescaled passes) and tighten the normalization skip tolerance to
a constant `16 * eps` on the non-overflowing path so `O(eps)` summation error
preserves bit-exact stream round-trips even for large non-power-of-two `n`
without allowing `n * (1 - sum)` to grow quadratically with `n`.
* Preserve `q[i].first` for any residual `under` entries after the alias loop
and alias only the remaining `1.0 - q[i].first` mass to `nonzero_idx`
(`q[i].second = nonzero_idx`), preventing zero or tiny nonzero weights from
being inflated to `1.0`.
* In the unary-operation constructor, guard against `xmax - xmin` overflowing
to `+inf` on wide finite ranges (such as `[-1.7e308, 1.7e308]`) by falling
back to an overflow-free convex midpoint combination
(`w_lo * xmin + w_hi * xmax`) while keeping the existing formula bit-identical
on finite spans.
PiperOrigin-RevId: 1022529302
diff --git a/absl/random/discrete_distribution.cc b/absl/random/discrete_distribution.cc
index 247faa8..cb69384 100644
--- a/absl/random/discrete_distribution.cc
+++ b/absl/random/discrete_distribution.cc
@@ -17,8 +17,7 @@
#include <cassert>
#include <cmath>
#include <cstddef>
-#include <iterator>
-#include <numeric>
+#include <limits>
#include <utility>
#include <vector>
@@ -27,6 +26,28 @@
namespace absl {
ABSL_NAMESPACE_BEGIN
namespace random_internal {
+namespace {
+
+// Adds a non-negative finite `value` into a Neumaier compensated sum
+// (`sum + compensation`). If the running sum overflows to infinity, records
+// infinity in `sum` and clears `compensation` so `sum + compensation` remains
+// `+inf` rather than `NaN`.
+void NeumaierAdd(double value, double& sum, double& compensation) {
+ const double t = sum + value;
+ if (!std::isfinite(t)) {
+ sum = t;
+ compensation = 0.0;
+ return;
+ }
+ if (sum >= value) {
+ compensation += (sum - t) + value;
+ } else {
+ compensation += (value - t) + sum;
+ }
+ sum = t;
+}
+
+} // namespace
// Initializes the distribution table for Walker's Aliasing algorithm, described
// in Knuth, Vol 2. as well as in https://en.wikipedia.org/wiki/Alias_method
@@ -37,11 +58,44 @@
assert(!probabilities->empty());
// Step 1. Normalize the input probabilities to 1.0.
- double sum = std::accumulate(std::begin(*probabilities),
- std::end(*probabilities), 0.0);
- if (std::fabs(sum - 1.0) > 1e-6) {
- // Scale `probabilities` only when the sum is too far from 1.0. Scaling
- // unconditionally will alter the probabilities slightly.
+ double max_weight = 0.0;
+ size_t nonzero_idx = 0;
+ double sum = 0.0;
+ double compensation = 0.0;
+ for (size_t i = 0; i < probabilities->size(); ++i) {
+ const double w = (*probabilities)[i];
+ assert(w >= 0.0 && std::isfinite(w));
+ if (w > max_weight) {
+ max_weight = w;
+ nonzero_idx = i;
+ }
+ NeumaierAdd(w, sum, compensation);
+ }
+ if (max_weight == 0.0) {
+ // Defensive fallback when all weights are zero (violating
+ // [rand.dist.samp.discrete]'s S > 0 precondition): behave like an empty
+ // weight list, returning outcome 0 with probability 1 instead of NaN.
+ probabilities->assign(1, 1.0);
+ return {{1.0, 0}};
+ }
+
+ sum += compensation;
+ const bool overflowed = !std::isfinite(sum);
+ if (overflowed) {
+ sum = 0.0;
+ compensation = 0.0;
+ for (double& item : *probabilities) {
+ item /= max_weight;
+ NeumaierAdd(item, sum, compensation);
+ }
+ sum += compensation;
+ }
+ constexpr double kTol = 16.0 * std::numeric_limits<double>::epsilon();
+ if ((overflowed && sum != 1.0) || std::fabs(sum - 1.0) > kTol) {
+ // Scale `probabilities` unless they already sum to 1.0 within rounding
+ // error (such as during stream round-trip deserialization). On the
+ // overflow-rescaled path, normalize whenever `sum != 1.0` so small
+ // secondary weights cannot leave the maximum entry at 1.0.
for (double& item : *probabilities) {
item = item / sum;
}
@@ -92,13 +146,16 @@
}
// Due to rounding errors, there may be un-paired elements in either
- // collection; these should all be values near 1.0. For these values, set `q`
- // to 1.0 and set the alternate to the identity.
+ // collection. For `over` elements (`q[i].first >= 1.0`), clamp acceptance to
+ // 1.0 and set the alternate to the identity. For `under` elements
+ // (`0.0 <= q[i].first < 1.0`), preserve `q[i].first` and alias only the
+ // remaining `1.0 - q[i].first` mass to `nonzero_idx` so zero or tiny weights
+ // can never be inflated to 1.0.
for (auto i : over) {
q[i] = {1.0, i};
}
for (auto i : under) {
- q[i] = {1.0, i};
+ q[i].second = nonzero_idx;
}
return q;
}
diff --git a/absl/random/discrete_distribution.h b/absl/random/discrete_distribution.h
index 35d42c8..19729d2 100644
--- a/absl/random/discrete_distribution.h
+++ b/absl/random/discrete_distribution.h
@@ -16,6 +16,7 @@
#define ABSL_RANDOM_DISCRETE_DISTRIBUTION_H_
#include <cassert>
+#include <cmath>
#include <cstddef>
#include <initializer_list>
#include <istream>
@@ -75,12 +76,26 @@
explicit param_type(size_t nw, double xmin, double xmax,
UnaryOperation fw) {
if (nw > 0) {
+ assert(std::isfinite(xmin) && std::isfinite(xmax) && xmin < xmax);
p_.reserve(nw);
- double delta = (xmax - xmin) / static_cast<double>(nw);
- assert(delta > 0);
- double t = delta * 0.5;
- for (size_t i = 0; i < nw; ++i) {
- p_.push_back(fw(xmin + i * delta + t));
+ const double span = xmax - xmin;
+ if (std::isfinite(span)) {
+ const double delta = span / static_cast<double>(nw);
+ assert(delta > 0);
+ const double t = delta * 0.5;
+ for (size_t i = 0; i < nw; ++i) {
+ p_.push_back(fw(xmin + static_cast<double>(i) * delta + t));
+ }
+ } else {
+ // `xmax - xmin` overflowed (`xmin < 0 < xmax`); compute each
+ // midpoint as an overflow-free convex combination of `xmin` and
+ // `xmax`.
+ const double dnw = static_cast<double>(nw);
+ for (size_t i = 0; i < nw; ++i) {
+ const double w_hi = (static_cast<double>(i) + 0.5) / dnw;
+ const double w_lo = (static_cast<double>(nw - 1 - i) + 0.5) / dnw;
+ p_.push_back(fw(w_lo * xmin + w_hi * xmax));
+ }
}
}
init();
diff --git a/absl/random/discrete_distribution_test.cc b/absl/random/discrete_distribution_test.cc
index 9d961f7..8005e4b 100644
--- a/absl/random/discrete_distribution_test.cc
+++ b/absl/random/discrete_distribution_test.cc
@@ -18,6 +18,7 @@
#include <cstddef>
#include <cstdint>
#include <iterator>
+#include <limits>
#include <numeric>
#include <random>
#include <sstream>
@@ -249,4 +250,254 @@
EXPECT_THAT(output, testing::ElementsAre(3, 3, 0, 3, 0, 4));
}
+TEST(DiscreteDistributionTest, AllZeroLargeAndNearUnitWeights) {
+ using testing::DoubleEq;
+ using testing::ElementsAre;
+ using testing::Gt;
+ using testing::Lt;
+ using testing::Pointwise;
+
+ absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL);
+
+ // Defensive fallback when all weights are zero (violating
+ // [rand.dist.samp.discrete]'s S > 0 precondition): behave like an empty
+ // weight list and produce {1.0}.
+ absl::discrete_distribution<int> all_zero({0.0, 0.0, 0.0});
+ EXPECT_THAT(all_zero.probabilities(), ElementsAre(1.0));
+ EXPECT_EQ(all_zero(rng), 0);
+
+ // Finite weights whose sum overflows double still normalize accurately.
+ absl::discrete_distribution<int> huge({0.5e308, 1.5e308});
+ EXPECT_THAT(huge.probabilities(), ElementsAre(0.25, 0.75));
+
+ // Overflowing weights where secondary weights sum to <= 16*eps * max_weight
+ // must still normalize by the rescaled sum so the dominant entry is < 1.0
+ // and matches the non-overflowing half-scaled distribution.
+ constexpr double kMax = (std::numeric_limits<double>::max)();
+ {
+ absl::discrete_distribution<int> dominant_overflow({kMax, 1e293});
+ absl::discrete_distribution<int> dominant_scaled({0.5 * kMax, 0.5 * 1e293});
+ EXPECT_THAT(dominant_overflow.probabilities(),
+ ElementsAre(Lt(1.0), Gt(0.0)));
+ EXPECT_THAT(dominant_overflow.probabilities(),
+ Pointwise(DoubleEq(), dominant_scaled.probabilities()));
+ }
+ {
+ absl::discrete_distribution<int> multi_overflow(
+ {kMax, 1e293, 1e293, 1e293, 1e293, 1e293, 1e293});
+ absl::discrete_distribution<int> multi_scaled(
+ {0.5 * kMax, 0.5 * 1e293, 0.5 * 1e293, 0.5 * 1e293, 0.5 * 1e293,
+ 0.5 * 1e293, 0.5 * 1e293});
+ EXPECT_THAT(multi_overflow.probabilities(),
+ ElementsAre(Lt(1.0), Gt(0.0), Gt(0.0), Gt(0.0), Gt(0.0),
+ Gt(0.0), Gt(0.0)));
+ EXPECT_THAT(multi_overflow.probabilities(),
+ Pointwise(DoubleEq(), multi_scaled.probabilities()));
+ }
+
+ // Zero-weight outcomes in a near-1.0 weight vector must never be sampled.
+ std::vector<double> near_unit(2000, 0.0);
+ near_unit[0] = 0.5 - 5e-7;
+ near_unit[1] = 0.5;
+ absl::discrete_distribution<int> sparse(near_unit.begin(), near_unit.end());
+ for (int i = 0; i < 20000; ++i) {
+ const int v = sparse(rng);
+ EXPECT_LE(v, 1);
+ }
+}
+
+TEST(DiscreteDistributionTest, StrandedUnderPreservesAcceptance) {
+ using testing::AnyOf;
+ using testing::DoubleEq;
+ using testing::DoubleNear;
+ using testing::Each;
+ using testing::ElementsAre;
+ using testing::Gt;
+ using testing::Pair;
+
+ constexpr double kEps = std::numeric_limits<double>::epsilon();
+ absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ULL);
+
+ // Sum is 1.0 - 6*eps (within 16*eps tolerance), so InitDiscreteDistribution
+ // skips rescaling and `over` empties leaving index 1 stranded in `under`.
+ // Both tiny nonzero (1e-300) and stranded `under` entries must keep their
+ // exact acceptance probabilities rather than being inflated to 1.0.
+ {
+ std::vector<double> p = {1e-300, 0.5 - 4.0 * kEps, 0.5 - 2.0 * kEps};
+ const auto q = absl::random_internal::InitDiscreteDistribution(&p);
+ EXPECT_THAT(q, ElementsAre(Pair(DoubleEq(3.0 * 1e-300), 2),
+ Pair(DoubleEq(1.0 - 18.0 * kEps), 2),
+ Pair(DoubleEq(0.5 - 6.0 * kEps), 1)));
+ EXPECT_LT(q[1].first, 1.0);
+
+ absl::discrete_distribution<int> dist(p.begin(), p.end());
+ std::vector<int> counts(3, 0);
+ for (int i = 0; i < 20000; ++i) {
+ const int v = dist(rng);
+ ASSERT_GE(v, 0);
+ ASSERT_LT(static_cast<size_t>(v), counts.size());
+ ++counts[static_cast<size_t>(v)];
+ }
+ EXPECT_THAT(counts, ElementsAre(0, Gt(0), Gt(0)));
+ }
+
+ // Same setup with an exact 0.0 weight at index 0.
+ {
+ std::vector<double> p = {0.0, 0.5 - 4.0 * kEps, 0.5 - 2.0 * kEps};
+ const auto q = absl::random_internal::InitDiscreteDistribution(&p);
+ EXPECT_THAT(q,
+ ElementsAre(Pair(0.0, 2), Pair(DoubleEq(1.0 - 18.0 * kEps), 2),
+ Pair(DoubleEq(0.5 - 6.0 * kEps), 1)));
+ EXPECT_LT(q[1].first, 1.0);
+
+ absl::discrete_distribution<int> dist(p.begin(), p.end());
+ std::vector<int> counts(3, 0);
+ for (int i = 0; i < 20000; ++i) {
+ const int v = dist(rng);
+ ASSERT_GE(v, 0);
+ ASSERT_LT(static_cast<size_t>(v), counts.size());
+ ++counts[static_cast<size_t>(v)];
+ }
+ EXPECT_THAT(counts, ElementsAre(0, Gt(0), Gt(0)));
+ }
+
+ // Both 0.0 and 1e-300 together in a near-1.0 vector within tolerance.
+ {
+ std::vector<double> p = {0.0, 1e-300, 0.5 - 4.0 * kEps, 0.5 - 2.0 * kEps};
+ const auto q = absl::random_internal::InitDiscreteDistribution(&p);
+ EXPECT_THAT(q, ElementsAre(Pair(0.0, 2), Pair(DoubleEq(4.0 * 1e-300), 3),
+ Pair(DoubleEq(1.0 - 24.0 * kEps), 3),
+ Pair(DoubleEq(1.0 - 8.0 * kEps), 2)));
+ EXPECT_LT(q[2].first, 1.0);
+
+ absl::discrete_distribution<int> dist(p.begin(), p.end());
+ std::vector<int> counts(4, 0);
+ for (int i = 0; i < 20000; ++i) {
+ const int v = dist(rng);
+ ASSERT_GE(v, 0);
+ ASSERT_LT(static_cast<size_t>(v), counts.size());
+ ++counts[static_cast<size_t>(v)];
+ }
+ EXPECT_THAT(counts, ElementsAre(0, 0, Gt(0), Gt(0)));
+ }
+
+ // All entries start strictly under 1.0 (`over` is empty from the start),
+ // stranding multiple `under` entries simultaneously; every entry preserves
+ // its `q[i].first < 1.0` and aliases its remainder to `nonzero_idx` (3).
+ {
+ std::vector<double> p = {0.25 - 2.0 * kEps, 0.25 - 2.0 * kEps,
+ 0.25 - 2.0 * kEps, 0.25 - kEps};
+ const auto q = absl::random_internal::InitDiscreteDistribution(&p);
+ EXPECT_THAT(q, ElementsAre(Pair(DoubleEq(1.0 - 8.0 * kEps), 3),
+ Pair(DoubleEq(1.0 - 8.0 * kEps), 3),
+ Pair(DoubleEq(1.0 - 8.0 * kEps), 3),
+ Pair(DoubleEq(1.0 - 4.0 * kEps), 3)));
+ for (const auto& entry : q) {
+ EXPECT_LT(entry.first, 1.0);
+ }
+ }
+
+ // Deficit 1e-13 at n=2000 exceeds constant 16*eps tolerance (whereas a
+ // linear 4*n*eps tolerance would skip rescaling), keeping both 0.0 and
+ // 1e-300 entries uninflated.
+ {
+ std::vector<double> p(2000, 0.0);
+ p[1] = 1e-300;
+ p[2] = 0.5 - 1e-13;
+ p[3] = 0.5;
+ const auto q = absl::random_internal::InitDiscreteDistribution(&p);
+ EXPECT_THAT(p[3], Gt(0.5));
+ EXPECT_THAT(q[0], Pair(0.0, AnyOf(2, 3)));
+ EXPECT_THAT(q[1], Pair(DoubleNear(2000.0 * 1e-300, 1e-309), AnyOf(2, 3)));
+
+ absl::discrete_distribution<int> dist(p.begin(), p.end());
+ std::vector<int> samples;
+ samples.reserve(20000);
+ for (int i = 0; i < 20000; ++i) {
+ samples.push_back(dist(rng));
+ }
+ EXPECT_THAT(samples, Each(AnyOf(2, 3)));
+ }
+}
+
+TEST(DiscreteDistributionTest, UnaryOpConstructorOverflowRange) {
+ using testing::DoubleEq;
+ using testing::ElementsAre;
+
+ {
+ std::vector<double> args;
+ absl::discrete_distribution<int> dist(4, -1e308, 1e308, [&](double x) {
+ args.push_back(x);
+ return static_cast<double>(args.size());
+ });
+ EXPECT_THAT(args, ElementsAre(DoubleEq(-7.5e307), DoubleEq(-2.5e307),
+ DoubleEq(2.5e307), DoubleEq(7.5e307)));
+ EXPECT_THAT(dist.probabilities(), ElementsAre(0.1, 0.2, 0.3, 0.4));
+ }
+
+ {
+ std::vector<double> args;
+ const double weights[] = {1.0, 2.0, 1.0};
+ absl::discrete_distribution<int> dist(3, -1.7e308, 1.7e308, [&](double x) {
+ const double w = weights[args.size()];
+ args.push_back(x);
+ return w;
+ });
+ EXPECT_THAT(args,
+ ElementsAre(DoubleEq(-1.7e308 * (2.0 / 3.0)), DoubleEq(0.0),
+ DoubleEq(1.7e308 * (2.0 / 3.0))));
+ EXPECT_THAT(dist.probabilities(), ElementsAre(0.25, 0.5, 0.25));
+ }
+
+ {
+ std::vector<double> args;
+ absl::discrete_distribution<int> dist(1, -1.7e308, 1.7e308, [&](double x) {
+ args.push_back(x);
+ return 1.0;
+ });
+ EXPECT_THAT(args, ElementsAre(DoubleEq(0.0)));
+ EXPECT_THAT(dist.probabilities(), ElementsAre(1.0));
+ }
+
+ {
+ std::vector<double> args;
+ absl::discrete_distribution<int> dist(4, -1.5e308, 0.5e308, [&](double x) {
+ args.push_back(x);
+ return 1.0;
+ });
+ EXPECT_THAT(args, ElementsAre(DoubleEq(-1.25e308), DoubleEq(-7.5e307),
+ DoubleEq(-2.5e307), DoubleEq(2.5e307)));
+ EXPECT_THAT(dist.probabilities(), ElementsAre(0.25, 0.25, 0.25, 0.25));
+ }
+}
+
+TEST(DiscreteDistributionTest, LargeNonPowerOfTwoSerializationRoundTrip) {
+ auto verify_round_trip = [](const std::vector<double>& weights) {
+ absl::discrete_distribution<int> before(weights.begin(), weights.end());
+ std::stringstream ss;
+ ss << before;
+ absl::discrete_distribution<int> after;
+ ss >> after;
+ EXPECT_FALSE(ss.fail());
+ EXPECT_EQ(before, after);
+ };
+
+ for (size_t n : {size_t{1000}, size_t{10000}}) {
+ verify_round_trip(std::vector<double>(n, 1.0));
+
+ std::vector<double> varied(n);
+ for (size_t i = 0; i < n; ++i) {
+ varied[i] = 1.0 + static_cast<double>((i * 31) % 997) * 0.13;
+ }
+ verify_round_trip(varied);
+ }
+
+ // Overflow-rescaled large non-power-of-two distribution also round-trips.
+ std::vector<double> huge(1000);
+ for (size_t i = 0; i < huge.size(); ++i) {
+ huge[i] = 1e307 * static_cast<double>(1 + (i % 7));
+ }
+ verify_round_trip(huge);
+}
+
} // namespace