Replace stateful rounding bias in ExponentialBiased with `mean + 0.5` floor scaling.

`ExponentialBiased::GetSkipCount(mean)` previously compensated for the `-0.5` truncation offset of `floor(-ln(u) * mean)` by rounding to the nearest integer (`std::rint`) and carrying a cumulative rounding-error term (`bias_`):
- Nearest-integer rounding gives `0` (`GetStride(period) == 1`) a half-width bin `[0, 0.5)` while every `k >= 1` has width `1.0`, halving `P(GetSkipCount(m) == 0)` to `1 / (2*m + 2/3) ~= 0.5 / (m + 1)`. This under-samples the first event on every new thread by ~2x, introduces a ~2x post-sample refractory dip, and negatively correlates consecutive draws via `bias_`.
- Using only 26 PRNG bits with `+ 1.0` also floored `P(GetSkipCount(m) == 0)` at `2^-26` for `m >> 2^26` and capped strides at `~18 * period`.

Pre-adding `+0.5` to `mean` before truncating (`floor(-ln(u) * (mean + 0.5))`, using all 48 PRNG bits mapped to bin midpoints `(rng_ + 0.5) * 2^-48`) cancels `floor`'s `-0.5` fractional offset in expectation on every draw (`E[stride] = period + 1 / (12 * period) + O(period^-3)`) while producing an exact memoryless geometric distribution with full-width bins from `0` upward, lower ALU/FP cost (no `std::rint` or `bias_` load/store), and smaller TLS state (`16` B instead of `24` B). Also replace the assertion-less `printf` demo tests with non-flaky distribution shape, mean, first-draw, and lag-1 independence tests.

PiperOrigin-RevId: 1020795145
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc
index 8682ca1..6f5125b 100644
--- a/absl/profiling/internal/exponential_biased.cc
+++ b/absl/profiling/internal/exponential_biased.cc
@@ -16,10 +16,8 @@
 
 #include <stdint.h>
 
-#include <algorithm>
 #include <atomic>
 #include <cmath>
-#include <limits>
 
 #include "absl/base/attributes.h"
 #include "absl/base/config.h"
@@ -29,48 +27,42 @@
 ABSL_NAMESPACE_BEGIN
 namespace profiling_internal {
 
-// The algorithm generates a random number between 0 and 1 and applies the
-// inverse cumulative distribution function for an exponential. Specifically:
-// Let m be the inverse of the sample period, then the probability
-// distribution function is m*exp(-mx) so the CDF is
-// p = 1 - exp(-mx), so
-// q = 1 - p = exp(-mx)
-// log_e(q) = -mx
-// -log_e(q)/m = x
-// log_2(q) * (-log_e(2) * 1/m) = x
-// In the code, q is actually in the range 1 to 2**26, hence the -26 below
+// Generates a memoryless geometric skip count on {0, 1, 2, ...} by applying
+// `floor(-ln(u) * (mean + 0.5))` to a uniform variate `u` in `(0, 1)`. The
+// `+0.5` scale shift cancels the `-0.5` average fractional part discarded by
+// `floor` (`E[skip] = mean + 1 / (12 * (mean + 0.5)) + O(mean^-3)`).
 int64_t ExponentialBiased::GetSkipCount(int64_t mean) {
+  if (ABSL_PREDICT_FALSE(mean <= 0)) {
+    return 0;
+  }
   if (ABSL_PREDICT_FALSE(!initialized_)) {
     Initialize();
   }
 
-  uint64_t rng = NextRandom(rng_);
-  rng_ = rng;
+  rng_ = NextRandom(rng_);
 
-  // Take the top 26 bits as the random number
-  // (This plus the 1<<58 sampling bound give a max possible step of
-  // 5194297183973780480 bytes.)
-  // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
-  // under piii debug for some binaries.
-  double q = static_cast<uint32_t>(rng >> (kPrngNumBits - 26)) + 1.0;
-  // Put the computed p-value through the CDF of a geometric.
-  double interval = bias_ + (std::log2(q) - 26) * (-std::log(2.0) * mean);
-  // Very large values of interval overflow int64_t. To avoid that, we will
-  // cheat and clamp any huge values to (int64_t max)/2. This is a potential
-  // source of bias, but the mean would need to be such a large value that it's
-  // not likely to come up. For example, with a mean of 1e18, the probability of
-  // hitting this condition is about 1/1000. For a mean of 1e17, standard
-  // calculators claim that this event won't happen.
-  if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
-    // Assume huge values are bias neutral, retain bias for next call.
-    return std::numeric_limits<int64_t>::max() / 2;
+  // Map the 48-bit PRNG output to the midpoint of its uniform bin in (0, 1).
+  // Every midpoint `(rng_ + 0.5) * 2^-48` has at most 49 significand bits and
+  // is therefore represented without rounding in IEEE-754 `double`.
+  constexpr double kInvPrngMod =
+      1.0 / static_cast<double>(uint64_t{1} << kPrngNumBits);
+  const double u = (static_cast<double>(rng_) + 0.5) * kInvPrngMod;
+  const double interval = -std::log(u) * (static_cast<double>(mean) + 0.5);
+
+  // Clamp extreme values so casting `interval` to `int64_t` (and adding 1 in
+  // `GetStride()`) cannot overflow. `1 << 62` is an exact power of two in
+  // IEEE-754 `double`.
+  constexpr int64_t kMaxSkip = int64_t{1} << 62;
+  if (ABSL_PREDICT_FALSE(interval >= static_cast<double>(kMaxSkip))) {
+    return kMaxSkip;
   }
-  double value = std::rint(interval);
-  bias_ = interval - value;
-  return static_cast<int64_t>(value);
+  return static_cast<int64_t>(interval);
 }
 
 int64_t ExponentialBiased::GetStride(int64_t mean) {
+  if (ABSL_PREDICT_FALSE(mean <= 1)) {
+    return 1;
+  }
   return GetSkipCount(mean - 1) + 1;
 }
 
diff --git a/absl/profiling/internal/exponential_biased.h b/absl/profiling/internal/exponential_biased.h
index d31f778..8823598 100644
--- a/absl/profiling/internal/exponential_biased.h
+++ b/absl/profiling/internal/exponential_biased.h
@@ -25,13 +25,14 @@
 namespace profiling_internal {
 
 // ExponentialBiased provides a small and fast random number generator for a
-// rounded exponential distribution. This generator manages very little state,
-// and imposes no synchronization overhead. This makes it useful in specialized
-// scenarios requiring minimum overhead, such as stride based periodic sampling.
+// memoryless geometric distribution (the discrete analog of an exponential
+// distribution). This generator manages very little state, and imposes no
+// synchronization overhead. This makes it useful in specialized scenarios
+// requiring minimum overhead, such as stride-based periodic sampling.
 //
 // ExponentialBiased provides two closely related functions, GetSkipCount() and
-// GetStride(), both returning a rounded integer defining a number of events
-// required before some event with a given mean probability occurs.
+// GetStride(), returning the number of events to skip (`>= 0`) or the number
+// of events required (`>= 1`) before an event with a given mean occurs.
 //
 // The distribution is useful to generate a random wait time or some periodic
 // event with a given mean probability. For example, if an action is supposed to
@@ -44,32 +45,13 @@
 //   }
 //
 //   void Frobber::Frob(int arg) {
-//     if (--stride == 0) {
+//     if (--stride_ == 0) {
 //       SampleFrob(arg);
 //       stride_ = exponential_biased_.GetStride(1000);
 //     }
 //     ...
 //   }
 //
-// The rounding of the return value creates a bias, especially for smaller means
-// where the distribution of the fraction is not evenly distributed. We correct
-// this bias by tracking the fraction we rounded up or down on each iteration,
-// effectively tracking the distance between the cumulative value, and the
-// rounded cumulative value. For example, given a mean of 2:
-//
-//   raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923
-//   raw = 0.14624, cumulative = 1.77701, rounded = 2, bias =  0.14624
-//   raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805
-//   raw = 0.24206, cumulative = 6.95101, rounded = 7, bias =  0.24206
-//   etc...
-//
-// Adjusting with rounding bias is relatively trivial:
-//
-//    double value = bias_ + exponential_distribution(mean)();
-//    double rounded_value = std::rint(value);
-//    bias_ = value - rounded_value;
-//    return rounded_value;
-//
 // This class is thread-compatible.
 class ExponentialBiased {
  public:
@@ -107,7 +89,6 @@
   void Initialize();
 
   uint64_t rng_{0};
-  double bias_{0};
   bool initialized_{false};
 };
 
diff --git a/absl/profiling/internal/exponential_biased_test.cc b/absl/profiling/internal/exponential_biased_test.cc
index 3471b07..1961b3f 100644
--- a/absl/profiling/internal/exponential_biased_test.cc
+++ b/absl/profiling/internal/exponential_biased_test.cc
@@ -14,20 +14,12 @@
 
 #include "absl/profiling/internal/exponential_biased.h"
 
-#include <stddef.h>
-
-#include <algorithm>
-#include <cmath>
 #include <cstdint>
-#include <cstdio>
-#include <string>
-#include <vector>
 
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include "absl/base/attributes.h"
 #include "absl/base/config.h"
-#include "absl/strings/str_cat.h"
 
 using ::testing::Ge;
 
@@ -36,197 +28,104 @@
 namespace profiling_internal {
 namespace {
 
-MATCHER_P2(IsBetween, a, b,
-           absl::StrCat(std::string(negation ? "isn't" : "is"), " between ", a,
-                        " and ", b)) {
-  return a <= arg && arg <= b;
-}
-
-// Tests of the quality of the random numbers generated
-// This uses the Anderson Darling test for uniformity.
-// See "Evaluating the Anderson-Darling Distribution" by Marsaglia
-// for details.
-
-// Short cut version of ADinf(z), z>0 (from Marsaglia)
-// This returns the p-value for Anderson Darling statistic in
-// the limit as n-> infinity. For finite n, apply the error fix below.
-double AndersonDarlingInf(double z) {
-  if (z < 2) {
-    return exp(-1.2337141 / z) / sqrt(z) *
-           (2.00012 +
-            (0.247105 -
-             (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 * z) * z) * z) *
-                 z) *
-                z);
-  }
-  return exp(
-      -exp(1.0776 -
-           (2.30695 -
-            (0.43424 - (0.082433 - (0.008056 - 0.0003146 * z) * z) * z) * z) *
-               z));
-}
-
-// Corrects the approximation error in AndersonDarlingInf for small values of n
-// Add this to AndersonDarlingInf to get a better approximation
-// (from Marsaglia)
-double AndersonDarlingErrFix(int n, double x) {
-  if (x > 0.8) {
-    return (-130.2137 +
-            (745.2337 -
-             (1705.091 - (1950.646 - (1116.360 - 255.7844 * x) * x) * x) * x) *
-                x) /
-           n;
-  }
-  double cutoff = 0.01265 + 0.1757 / n;
-  if (x < cutoff) {
-    double t = x / cutoff;
-    t = sqrt(t) * (1 - t) * (49 * t - 102);
-    return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n;
-  } else {
-    double t = (x - cutoff) / (0.8 - cutoff);
-    t = -0.00022633 +
-        (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 * t) * t) * t) * t) *
-            t;
-    return t * (0.04213 + 0.01365 / n) / n;
-  }
-}
-
-// Returns the AndersonDarling p-value given n and the value of the statistic
-double AndersonDarlingPValue(int n, double z) {
-  double ad = AndersonDarlingInf(z);
-  double errfix = AndersonDarlingErrFix(n, ad);
-  return ad + errfix;
-}
-
-double AndersonDarlingStatistic(const std::vector<double>& random_sample) {
-  size_t n = random_sample.size();
-  double ad_sum = 0;
-  for (size_t i = 0; i < n; i++) {
-    ad_sum += (2 * i + 1) *
-              std::log(random_sample[i] * (1 - random_sample[n - 1 - i]));
-  }
-  const auto n_as_double = static_cast<double>(n);
-  double ad_statistic = -n_as_double - 1 / n_as_double * ad_sum;
-  return ad_statistic;
-}
-
-// Tests if the array of doubles is uniformly distributed.
-// Returns the p-value of the Anderson Darling Statistic
-// for the given set of sorted random doubles
-// See "Evaluating the Anderson-Darling Distribution" by
-// Marsaglia and Marsaglia for details.
-double AndersonDarlingTest(const std::vector<double>& random_sample) {
-  double ad_statistic = AndersonDarlingStatistic(random_sample);
-  double p = AndersonDarlingPValue(static_cast<int>(random_sample.size()),
-                                   ad_statistic);
-  return p;
-}
-
-TEST(ExponentialBiasedTest, CoinTossDemoWithGetSkipCount) {
+// Non-positive arguments must return the minimum valid skip (0) or stride (1),
+// and extreme arguments must clamp without signed integer overflow.
+TEST(ExponentialBiasedTest, NonPositiveParametersAndClamp) {
   ExponentialBiased eb;
-  for (int runs = 0; runs < 10; ++runs) {
-    for (int64_t flips = eb.GetSkipCount(1); flips > 0; --flips) {
-      printf("head...");
-    }
-    printf("tail\n");
-  }
-  int heads = 0;
-  for (int i = 0; i < 10000000; i += 1 + eb.GetSkipCount(1)) {
-    ++heads;
-  }
-  printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000);
+  EXPECT_EQ(eb.GetSkipCount(0), 0);
+  EXPECT_EQ(eb.GetSkipCount(-5), 0);
+  EXPECT_EQ(eb.GetStride(1), 1);
+  EXPECT_EQ(eb.GetStride(0), 1);
+  EXPECT_EQ(eb.GetStride(-5), 1);
+  EXPECT_GE(eb.GetStride(int64_t{1} << 62), 1);
 }
 
-// In simplified idealized world, `GetSkipCount(m) == 0` translates to
-// `-log(X) * m + B <= 1/2`, where X is a uniform random number in (0, 1],
-// and B is uniform random number in [-0.5, 0.5). Let U = 0.5 - B, that makes
-// U a uniform random number in (0, 1]. After exponentiation we get
-// `X >= exp(-U / m)`. Probability of this is `1 - exp(-U / m)`, so we have to
-// integrate for all possible values of U: `1 - m * (1 - exp(-1 / m))`. For
-// simplicity take just two terms of Taylor series expansion:
-// `1/(2*m) - 1/(6*m^2)`. Reciprocal of that is `2*m + 2/3 + O(1/m)`. If we use
-// more math tricks we can get "exact" approximation, but result will still be
-// `2*m + 2/3 + O(1/m)`.
-TEST(ExponentialBiasedTest, OnePerNDemoWithGetSkipCount) {
+// Empirical mean skip count must match the requested mean across scales.
+TEST(ExponentialBiasedTest, MeanMatchesRequestedValue) {
   ExponentialBiased eb;
-  int n = 22;
-  int rounds = 220000;
-  int hits = 0;
-  for (int i = 0; i < rounds; i++) {
-    if (eb.GetSkipCount(n / 2) == 0) ++hits;
+  constexpr int kDraws = 100000;
+  for (int64_t mean :
+       {int64_t{10}, int64_t{100}, int64_t{1000}, int64_t{1} << 20}) {
+    double sum = 0;
+    for (int i = 0; i < kDraws; ++i) {
+      sum += static_cast<double>(eb.GetSkipCount(mean));
+    }
+    EXPECT_NEAR(sum / kDraws, static_cast<double>(mean), 0.05 * mean);
   }
-  double inverse_hit_rate = rounds / static_cast<double>(hits);
-  printf("N = %d, rounds = %d, inverse hit rate = %f (should be ~= N + 0.67)\n",
-         n, rounds, inverse_hit_rate);
 }
 
-// Large requested mean flattens density function near zero, making it almost
-// linear.
-TEST(ExponentialBiasedTest, OneOfNDemoWithGetSkipCount) {
+// Stride frequencies must match the geometric PMF
+// `P(S = s) = p * (1 - p)^(s - 1)` across individual buckets, including
+// `s = 1`.
+TEST(ExponentialBiasedTest, StrideFollowsGeometricDistribution) {
   ExponentialBiased eb;
-  int n = 6;
-  int large_mean = 10000000;
-  int rounds = n * 10000;
-  std::vector<int> hits(static_cast<size_t>(n), 0);
-  for (int i = 0; i < rounds; i++) {
-    int64_t v = eb.GetSkipCount(large_mean);
-    int64_t a = v % n;
-    ++hits[static_cast<size_t>(a)];
+  constexpr int64_t kPeriod = 10;
+  constexpr double kP = 1.0 / kPeriod;
+  constexpr int kDraws = 200000;
+
+  int counts[11] = {};
+  for (int i = 0; i < kDraws; ++i) {
+    int64_t s = eb.GetStride(kPeriod);
+    if (s <= 10) ++counts[s];
   }
-  printf("N = %d, rounds = %d, mean = %d\n", n, rounds, large_mean);
-  for (int i = 0; i < n; i++) {
-    printf("  inverse hit rate for %d: %f (should be ~= N)\n", i,
-           rounds / static_cast<double>(hits[static_cast<size_t>(i)]));
+
+  double expected_prob = kP;
+  for (int s = 1; s <= 10; ++s) {
+    EXPECT_NEAR(static_cast<double>(counts[s]) / kDraws, expected_prob, 0.006)
+        << "stride = " << s;
+    expected_prob *= (1.0 - kP);
   }
 }
 
-TEST(ExponentialBiasedTest, SampleDemoWithStride) {
+TEST(ExponentialBiasedTest, FirstAndConsecutiveDrawsAreUnbiased) {
+  constexpr int64_t kPeriod = 10;
+  constexpr double kExpectedProb = 1.0 / kPeriod;
+  constexpr int kTrials = 200000;
+
+  // The very first draw on a new thread/generator must sample immediately
+  // (`stride == 1`) with probability `1 / kPeriod`.
+  int first_draw_ones = 0;
+  for (int i = 0; i < kTrials; ++i) {
+    ExponentialBiased fresh;
+    if (fresh.GetStride(kPeriod) == 1) ++first_draw_ones;
+  }
+  EXPECT_NEAR(static_cast<double>(first_draw_ones) / kTrials, kExpectedProb,
+              0.01);
+
+  // Because a geometric process is memoryless, the draw immediately following
+  // `stride == 1` must still hit `stride == 1` with probability `1 / kPeriod`
+  // (no post-sample refractory dip from stateful rounding).
   ExponentialBiased eb;
-  int64_t stride = eb.GetStride(10);
-  int samples = 0;
-  for (int i = 0; i < 10000000; ++i) {
-    if (--stride == 0) {
-      ++samples;
-      stride = eb.GetStride(10);
-    }
+  int ones = 0;
+  int ones_after_one = 0;
+  bool prev_was_one = false;
+  for (int i = 0; i < kTrials; ++i) {
+    bool is_one = (eb.GetStride(kPeriod) == 1);
+    if (prev_was_one && is_one) ++ones_after_one;
+    if (prev_was_one) ++ones;
+    prev_was_one = is_one;
   }
-  printf("Samples = %d (%f%%)\n", samples, 100.0 * samples / 10000000);
+  EXPECT_NEAR(static_cast<double>(ones_after_one) / ones, kExpectedProb, 0.02);
 }
 
+// `NextRandom` outputs must stay within 48 bits and distribute uniformly across
+// high-bit buckets, which drive the geometric inverse-CDF transform.
+TEST(ExponentialBiasedTest, NextRandomIsUniform) {
+  uint64_t x = 1;
+  for (int i = 0; i < 20; ++i) {
+    x = ExponentialBiased::NextRandom(x);
+  }
 
-// Testing that NextRandom generates uniform random numbers. Applies the
-// Anderson-Darling test for uniformity
-TEST(ExponentialBiasedTest, TestNextRandom) {
-  for (auto n : std::vector<size_t>({
-           10,  // Check short-range correlation
-           100, 1000,
-           10000  // Make sure there's no systemic error
-       })) {
-    uint64_t x = 1;
-    // This assumes that the prng returns 48 bit numbers
-    uint64_t max_prng_value = static_cast<uint64_t>(1) << 48;
-    // Initialize.
-    for (int i = 1; i <= 20; i++) {
-      x = ExponentialBiased::NextRandom(x);
-    }
-    std::vector<uint64_t> int_random_sample(n);
-    // Collect samples
-    for (size_t i = 0; i < n; i++) {
-      int_random_sample[i] = x;
-      x = ExponentialBiased::NextRandom(x);
-    }
-    // First sort them...
-    std::sort(int_random_sample.begin(), int_random_sample.end());
-    std::vector<double> random_sample(n);
-    // Convert them to uniform randoms (in the range [0,1])
-    for (size_t i = 0; i < n; i++) {
-      random_sample[i] =
-          static_cast<double>(int_random_sample[i]) / max_prng_value;
-    }
-    // Now compute the Anderson-Darling statistic
-    double ad_pvalue = AndersonDarlingTest(random_sample);
-    EXPECT_GT(std::min(ad_pvalue, 1 - ad_pvalue), 0.0001)
-        << "prng is not uniform: n = " << n << " p = " << ad_pvalue;
+  constexpr int kBuckets = 16;
+  constexpr int kDraws = 160000;
+  int counts[kBuckets] = {};
+  for (int i = 0; i < kDraws; ++i) {
+    x = ExponentialBiased::NextRandom(x);
+    ASSERT_EQ(x >> ExponentialBiased::kPrngNumBits, 0u);
+    ++counts[x >> (ExponentialBiased::kPrngNumBits - 4)];
+  }
+  for (int count : counts) {
+    EXPECT_NEAR(static_cast<double>(count) / kDraws, 1.0 / kBuckets, 0.005);
   }
 }