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