about summary refs log tree commit diff
path: root/absl/base
diff options
context:
space:
mode:
Diffstat (limited to 'absl/base')
-rw-r--r--absl/base/internal/exponential_biased.cc52
-rw-r--r--absl/base/internal/exponential_biased.h6
2 files changed, 10 insertions, 48 deletions
diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc
index 3007f9b46b86..7786c303cdd1 100644
--- a/absl/base/internal/exponential_biased.cc
+++ b/absl/base/internal/exponential_biased.cc
@@ -27,7 +27,16 @@
 namespace absl {
 namespace base_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
 int64_t ExponentialBiased::GetSkipCount(int64_t mean) {
   if (ABSL_PREDICT_FALSE(!initialized_)) {
     Initialize();
@@ -63,47 +72,6 @@ int64_t ExponentialBiased::GetStride(int64_t mean) {
   return GetSkipCount(mean - 1) + 1;
 }
 
-// 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
-int64_t ExponentialBiased::Get(int64_t mean) {
-  if (ABSL_PREDICT_FALSE(!initialized_)) {
-    Initialize();
-  }
-
-  uint64_t rng = NextRandom(rng_);
-  rng_ = 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;
-  }
-  int64_t value = std::max<int64_t>(1, std::round(interval));
-  bias_ = interval - value;
-  return value;
-}
-
 void ExponentialBiased::Initialize() {
   // We don't get well distributed numbers from `this` so we call NextRandom() a
   // bunch to mush the bits around. We use a global_rand to handle the case
diff --git a/absl/base/internal/exponential_biased.h b/absl/base/internal/exponential_biased.h
index 571505d32677..6701e695ef0e 100644
--- a/absl/base/internal/exponential_biased.h
+++ b/absl/base/internal/exponential_biased.h
@@ -96,12 +96,6 @@ class ExponentialBiased {
   // `GetSkipCount()` depends mostly on what best fits the use case.
   int64_t GetStride(int64_t mean);
 
-  // Generates a rounded exponentially distributed random variable
-  // by rounding the value to the nearest integer.
-  // The result will be in the range [0, int64_t max / 2].
-  ABSL_DEPRECATED("Use GetSkipCount() or GetStride() instead")
-  int64_t Get(int64_t mean);
-
   // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1]
   //
   // This is public to enable testing.