From 7f4fe64af80fe3c84db8ea938276c3690573c45e Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 25 Nov 2019 10:40:20 -0800 Subject: Export of internal Abseil changes -- 44efc1bb0e0a47eabf0569eaab81c66710d5b9c3 by Mark Barolak : Update "strings::Substitute" to "absl::Substitute" in the absl::Substitute error messages. PiperOrigin-RevId: 282388042 -- 9ec7e9385f5469473f76857dc5b067d869bbc65b by Abseil Team : Remove deprecated ExponentialBiased::Get() PiperOrigin-RevId: 282045123 GitOrigin-RevId: 44efc1bb0e0a47eabf0569eaab81c66710d5b9c3 Change-Id: I915bf0ff5fa7ac2bd5f9fb653d1fbd9ece6af9fc --- absl/base/internal/exponential_biased.cc | 52 ++++++-------------------------- absl/base/internal/exponential_biased.h | 6 ---- 2 files changed, 10 insertions(+), 48 deletions(-) (limited to 'absl/base') diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc index 3007f9b..7786c30 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(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(std::numeric_limits::max() / 2)) { - // Assume huge values are bias neutral, retain bias for next call. - return std::numeric_limits::max() / 2; - } - int64_t value = std::max(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 571505d..6701e69 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. -- cgit v1.2.3