Draw exact memoryless geometric skip counts in ExponentialBiased.

`ExponentialBiased::GetSkipCount(mean)` previously approximated a geometric distribution by rounding `-ln(u) * mean` 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` gets width `1.0`. As a result, `P(GetSkipCount(m) == 0)` was `1 / (2*m + 2/3) ~= 0.5 / (m + 1)` instead of `1 / (m + 1)`, under-sampling the first event on every new thread by ~2x, introducing a ~2x refractory dip immediately after each sampled event, and negatively correlating consecutive strides through `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`.

Evaluate the exact `Geometric(1 / (mean + 1))` inverse CDF `floor(ln(u) / ln(1 - 1 / (mean + 1)))` using all 48 PRNG bits mapped to bin midpoints `(rng_ + 0.5) * 2^-48`, and drop `bias_` (shrinking `ExponentialBiased` from 24 B to 16 B). Every integer `k >= 0` now has exact geometric probability, exact expectation `mean`, and independent memoryless draws from the first call onward.

PiperOrigin-RevId: 1020748224
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc
index 8682ca1..b843136 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,48 @@
 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 geometric skip count on {0, 1, 2, ...} with exact expectation
+// `mean` (success probability `p = 1 / (mean + 1)`) by applying the geometric
+// inverse CDF `floor(ln(u) / ln(1 - p))` to a uniform variate `u` in `(0, 1)`.
 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;
+
+  // For mean >= 2^26, `-1 / ln(1 - 1 / (mean + 1))` differs from `mean + 0.5`
+  // by `1 / (12 * (mean + 1)) < 0.1` ULP of `double(mean)`.
+  const double inv_neg_log1p =
+      (mean < (int64_t{1} << 26))
+          ? (-1.0 / std::log1p(-1.0 / (static_cast<double>(mean) + 1.0)))
+          : (static_cast<double>(mean) + 0.5);
+  const double interval = -std::log(u) * inv_neg_log1p;
+
+  // 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..127358b 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,31 +45,26 @@
 //   }
 //
 //   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;
+// `GetSkipCount(mean)` evaluates the exact geometric inverse CDF
+// `floor(ln(u) / ln(1 - 1 / (mean + 1)))` (`~= floor(-ln(u) * (mean + 0.5))`):
+//   * Truncating `-ln(u) * mean` directly (`floor`) would underestimate the
+//     mean by ~0.5, which is significant for small means.
+//   * Rounding `-ln(u) * mean` to the nearest integer (`std::rint`) with a
+//     cumulative rounding-error term gives `0` (`stride == 1`) a half-width
+//     bin `[0, 0.5)` while every `k >= 1` has width `1.0`, halving the
+//     probability of `skip == 0` (`stride == 1`) to `~0.5 / (mean + 1)` on a
+//     fresh generator and immediately after each sampled event.
+// Using `floor` with the exact geometric scale `1 / -ln(1 - 1 / (mean + 1))`
+// gives every integer `k >= 0` a full-width geometric bin, exact expectation
+// `mean`, exact `P(GetSkipCount(mean) == 0) = 1 / (mean + 1)` (`P(GetStride(N)
+// == 1) = 1 / N`), and independent memoryless draws without extra state.
 //
 // This class is thread-compatible.
 class ExponentialBiased {
@@ -107,7 +103,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..edcd9f0 100644
--- a/absl/profiling/internal/exponential_biased_test.cc
+++ b/absl/profiling/internal/exponential_biased_test.cc
@@ -137,27 +137,20 @@
   printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000);
 }
 
-// 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)`.
+// `GetSkipCount(m)` is distributed as Geometric(1 / (m + 1)) on {0, 1, ...},
+// so `P(GetSkipCount(n - 1) == 0) == 1 / n`.
 TEST(ExponentialBiasedTest, OnePerNDemoWithGetSkipCount) {
   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;
+    if (eb.GetSkipCount(n - 1) == 0) ++hits;
   }
   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);
+  printf("N = %d, rounds = %d, inverse hit rate = %f (should be ~= N)\n", n,
+         rounds, inverse_hit_rate);
+  EXPECT_THAT(inverse_hit_rate, IsBetween(20.5, 23.5));
 }
 
 // Large requested mean flattens density function near zero, making it almost
@@ -245,6 +238,95 @@
   EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0));
 }
 
+TEST(ExponentialBiasedTest, NonPositiveParameters) {
+  ExponentialBiased eb;
+  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);
+}
+
+TEST(ExponentialBiasedTest, ExactMeanAndFirstDrawProbability) {
+  // Coin toss (`mean == 1`, `period == 2`): exact P(skip == 0) = 0.5 and
+  // E[skip] = 1.0.
+  ExponentialBiased coin;
+  constexpr int kFlips = 200000;
+  int zero_skips = 0;
+  int64_t total_skips = 0;
+  for (int i = 0; i < kFlips; ++i) {
+    const int64_t skip = coin.GetSkipCount(1);
+    if (skip == 0) ++zero_skips;
+    total_skips += skip;
+  }
+  // std(zero_skips) ~= 224; std(total_skips) = sqrt(200000 * 2) ~= 632.
+  EXPECT_THAT(zero_skips, IsBetween(98000, 102000));
+  EXPECT_THAT(total_skips, IsBetween(195000, 205000));
+
+  // Freshly constructed generators must also have exact `1 / kPeriod`
+  // probability of `GetStride(kPeriod) == 1` on their very first draw
+  // (previously `~0.5 / kPeriod` due to `std::rint`'s `[0, 0.5)` zero bin).
+  constexpr int64_t kPeriod = 16;
+  constexpr int kFreshTrials = 160000;
+  int fresh_unit_strides = 0;
+  for (int i = 0; i < kFreshTrials; ++i) {
+    ExponentialBiased fresh;
+    if (fresh.GetStride(kPeriod) == 1) {
+      ++fresh_unit_strides;
+    }
+  }
+  // Expected = 10000, std ~= 96.8.
+  EXPECT_THAT(fresh_unit_strides, IsBetween(9000, 11000));
+}
+
+TEST(ExponentialBiasedTest, MemorylessNoPostSampleRefractoryDip) {
+  ExponentialBiased eb;
+  constexpr int64_t kPeriod = 8;
+  constexpr int kDraws = 640000;
+  bool prev_was_one = false;
+  int prev_one_count = 0;
+  int consecutive_ones = 0;
+  int64_t stride_sum = 0;
+  for (int i = 0; i < kDraws; ++i) {
+    const int64_t s = eb.GetStride(kPeriod);
+    ASSERT_GE(s, 1);
+    stride_sum += s;
+    if (prev_was_one) {
+      ++prev_one_count;
+      if (s == 1) ++consecutive_ones;
+    }
+    prev_was_one = (s == 1);
+  }
+  // Expected sum = 5,120,000, std = sqrt(640000 * 8 * 7) ~= 5987.
+  EXPECT_THAT(stride_sum, IsBetween(5060000, 5180000));
+  // Expected prev_one_count ~= 80000; expected consecutive_ones = 1/8 of that
+  // (~= 10000, std ~= 93.5). Under the old `std::rint` + `bias_` generator,
+  // `P(S == 1)` was ~1/14.7, yielding only ~2900 consecutive ones.
+  const double conditional_rate =
+      static_cast<double>(consecutive_ones) / prev_one_count;
+  EXPECT_THAT(conditional_rate, IsBetween(0.11, 0.14));
+}
+
+TEST(ExponentialBiasedTest, LargeMeanBranchAndClamp) {
+  ExponentialBiased eb;
+  constexpr int64_t kLargeMean = int64_t{1} << 30;
+  constexpr int kDraws = 20000;
+  double sum = 0;
+  for (int i = 0; i < kDraws; ++i) {
+    const int64_t skip = eb.GetSkipCount(kLargeMean);
+    ASSERT_GE(skip, 0);
+    sum += static_cast<double>(skip);
+  }
+  const double expected = static_cast<double>(kDraws) * kLargeMean;
+  // std / expected = 1 / sqrt(20000) ~= 0.71%.
+  EXPECT_THAT(sum, IsBetween(0.94 * expected, 1.06 * expected));
+
+  // Extreme mean near INT64_MAX must clamp cleanly without signed overflow.
+  for (int i = 0; i < 100; ++i) {
+    EXPECT_GE(eb.GetStride(int64_t{1} << 62), 1);
+  }
+}
+
 }  // namespace
 }  // namespace profiling_internal
 ABSL_NAMESPACE_END