Creation of LTS branch "lts_2019_08_08"20190808

  - 9ee91d3e430fb33a4590486573792eb0fa146c2d Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 8efba58a3b656e9b41fb0471ae6453425a61c520 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - b49b8d16b67ec6912899684b732e6367f258cfdb Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 67222ffc4c83d918ce8395aa61769eeb77df4c4d Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - c5c4db4f5191fe5e76cbf68dcc71fb28702f7d2b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
  - 14550beb3b7b97195e483fb74b5efb906395c31e Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 52e88ee56b72cf32bc66534d942c7398ce481331 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 36d37ab992038f52276ca66b9da80c1cf0f57dc2 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - ad1485c8986246b2ae9105e512738d0e97aec887 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - f3840bc5e33ce4932e35986cf3718450c6f02af2 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 278b26058c036833a4f7f3047d3f4d9296527f87 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - c6c3c1b498e4ee939b24be59cae29d59c3863be8 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 44efe96dfca674a17b45ca53fc77fb69f1e29bf4 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 3c98fcc0461bd2a4b9c149d4748a7373a225cf4b Merge pull request #340 from jtsylve/macos_cxx17_fix by Matt Calabrese <38107210+mattcalabrese-google@users.noreply.github.com>
  - 74d91756c11bc22f9b0108b94da9326f7f9e376f Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - e6b050212c859fbaf67abac76105da10ec348274 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - c964fcffac27bd4a9ff67fe393410dd1146ef8b8 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 72e09a54d993b192db32be14c65adf7e9bd08c31 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - d65e19dfcd8697076f68598c0131c6930cdcd74d Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 5162fc83d2f3b79a9753ed59594c43966afdd37a Merge pull request #336 from shields/patch-2 by Shaindel Schwartz <31392632+shaindelschwartz@users.noreply.github.com>
  - 0389f7bf58fa41f35b3ad60be61d32f31e4f8ed6 Merge pull request #335 from shields/patch-1 by Shaindel Schwartz <31392632+shaindelschwartz@users.noreply.github.com>
  - e9324d926a9189e222741fce6e676f0944661a72 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 43ef2148c0936ebf7cb4be6b19927a9d9d145b8f Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - a13d3df2b3ba68aeead92e2d078fba0510d55024 Merge pull request #323 from gosnik/master by Gennadiy Rozental <rogeeff@google.com>
  - 310a11865c97c5cdcc42a4ee2c2e3578423afe69 Merge pull request #324 from RasPat1/patch-1 by Gennadiy Rozental <rogeeff@google.com>
  - 8f11724067248acc330b4d1f12f0c76d03f2cfb1 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - b1dd425423380126f6441ce4fbb6f8f6c75b793a Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 361cb8a9db2f2130442389fd80593255be26d681 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 0238ab0a831f179518c1a814f9584e99da2d75a3 Merge pull request #321 from christoph-cullmann/c4245_fix... by Xiaoyi Zhang <zhangxy988@gmail.com>
  - 61c9bf3e3e1c28a4aa6d7f1be4b37fd473bb5529 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - bc9101f9982391019521161a36179b52555ed212 Merge pull request #320 from christoph-cullmann/master by Xiaoyi Zhang <zhangxy988@gmail.com>
  - 2f76a9bf50046e396138cc8eeb3cdc17b7a5ac24 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 4adaf5490921f13028b55018c9f550277de5aebb Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 27c30ec671cb7b5ba84c4e79feff7fd0b0ac6338 Avoid undefined behavior when nullptr is passed to memcpy... by Roman Gershman <romange@gmail.com>
  - ce65f5ac3cbf897bb5e3de1a51d80fd00866abaa Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - a18fc7461e7409c2ad64e28537261db1e02e76fa Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 8a394b19c149cab50534b04c5e21d42bc2217a7d Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - daf381e8535a1f1f1b8a75966a74e7cca63dee89 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - fa00c321073c7ea40a4fc3dfc8a06309eae3d025 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 436ba6c4a0ea3a06eca6e055f9c8d296bf3bae12 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 0cbdc774b97f7e80ab60dbe2ed4eaca3b2e33fc8 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 27c2f6e2f3b5929fbd322b0f0ca392eb02efd9f8 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - aa468ad75539619b47979911297efbb629c52e44 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - cd86d0d20ab167c33b23d3875db68d1d4bad3a3b Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 33841c5c963aa9c3f096ef8e6c1e71624b941940 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - ca3f87560a0eef716195cadf66dc6b938a579ec6 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - d902eb869bcfacc1bad14933ed9af4bed006d481 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - a02f62f456f2c4a7ecf2be3104fe0c6e16fbad9a Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 0b545b460141b882b244a1efcef7621d59278160 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - dbae8764fbd429bf7d7745e24bcf73962177a7c0 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 044da8a29c923506af0f0b46bc46f43c1e1300b5 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 6cc6ac44e065b9e8975fadfd6ccb99cbcf89aac4 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 666fc1266bccfd8e6eaaa084e7b42580bb8eb199 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 93dfcf74cb5fccae3da07897d8613ae6cab958a0 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 2c8421e1c6cef0da9e8a20b01c15256ec9ec116d Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 5b65c4af5107176555b23a638e5947686410ac1f Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - eab2078b53c9e3d9d240135c09d27e3393acb50a Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 253eb7416421661873afbaa33828a850db978541 [CMake] Set correct flags for clang-cl (#278) by Loo Rong Jie <loorongjie@gmail.com>
  - e75672f6afc7e8f23ee7b532e86d1b3b9be3984e Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - bf29470384a101b307873b26d358433138c857fc Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 6fd827124facd8336981e73218997f9e73029b4f Merge pull request #280 from chiumichael/master by Derek Mauro <761129+derekmauro@users.noreply.github.com>
  - 7c7754fb3ed9ffb57d35fe8658f3ba4d73a31e72 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 256be563447a315f2a7993ec669460ba475fa86a Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 88a152ae747c3c42dc9167d46c590929b048d436 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - c1cecb25a94c075725e9d2640f6b978a8f61957b Implement Span::first and Span::last from C++20 (#274) by Girts <girtsf@users.noreply.github.com>
  - 38b704384cd2f17590b3922b97744be0b43622c9 Changed HTTP URLs to HTTPS where possible (#270) by nik7273 <nik8470@gmail.com>
  - febc5ee6a92d0eb7dac1fceaa6c648cf6521b4dc Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 9fdf5e5b805412cb2a2e624d3e9a11588120465f Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 419f3184f8ebcdb23105295eadd2a569f3351eb9 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - b312c3cb53a0aad75a85ac2bf57c4a614fbd48d4 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 308ce31528a7edfa39f5f6d36142278a0ae1bf45 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 93d155bc4414f6c121bb1f19dba9fdb27c8943bc Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 426eaa4aa44e4580418bee46c1bd13911151bfb1 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 2901ec32a919311384d6ad4194e2d927c06831f7 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - d78310fe5a82f2e0e6e16509ef8079c8d7e4674e Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - a4cb1c8ba61531a63f9d309eea01ac1d43d8371d Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 540e2537b92cd4abfae6ceddfe24304345461f32 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 89ea0c5ff34aaa5855cfc7aa41f323b8a0ef0ede Merge pull request #255 from uilianries/hotfix/conan by ahedberg <ahedberg@google.com>
  - 5e0dcf72c64fae912184d2e0de87195fe8f0a425 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 0dffca4e36791c7beeda04da10460b534283948a Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 6b4201f9ef650637510a21b8d6cbcc3bee4a606f Fix GCC8 warnings by Boris Staletic <boris.staletic@gmail.com>
  - 0b1e6d417b414aad9282e32e8c49c719edeb63c1 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - efccc502606bed768e50a6cd5806d8eb13e4e935 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 5e6a78131f7bd5940218462c07d88cdefdd75dbe Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 5eea0f713c14ac17788b83e496f11903f8e2bbb0 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 66f9becbb98ecc083f4db349b4b1e0ca9de93b15 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 018b4db1d73ec8238e6dc4b17fd9e1fd7468d0ed Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 9449ae94397f2fd683851348e25ed8c93f75b3b9 Merge pull request #243 from ThomsonTan/FixIntrinsic by Alex Strelnikov <strel@google.com>
  - b16aeb6756bdab08cdf12d40baab5b51f7d15b16 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 7ffbe09f3d85504bd018783bbe1e2c12992fe47c Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 01b471d9f3ebef27f5aaca14b66509099fa8cd6c Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 7bd8f36c741c7cbe311611d7981bf38ba04c6fef Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 968a34ffdaadd7db062a9621dfbdf8b2d16e05af Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 3e2e9b5557e76d098de4b8a2a659125b98ca519b Merge pull request #231 from uilianries/feature/conan by Mark Barolak <mbxx@users.noreply.github.com>
  - 111ca7060a6ff50115ca85b59f6b5d8c8c5e9105 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 389ec3f906f018661a5308458d623d01f96d7b23 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 8fbcdb90952c57828c4a9c2f6d79fcd7cae9088f Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 455dc17ba1af9635f0b60155bc565bc572a1e722 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - f197d7c72a54064cfde5a2058f1513a4a0ee36fb Export of internal Abseil changes. by Abseil Team <absl-team@google.com>
  - 284378a71b32dfb3af4e3661f585e671d1b603a3 Export of internal Abseil changes. by Abseil Team <absl-team@google.com>

GitOrigin-RevId: 9ee91d3e430fb33a4590486573792eb0fa146c2d
Change-Id: Ia06e548bc106cc9d136f6c65714be6645317aced

1 files changed, 423 insertions, 0 deletions

diff --git a/absl/random/zipf_distribution_test.cc b/absl/random/zipf_distribution_test.cc
new file mode 100644
index 00000000..4d4a0fcf
--- /dev/null
+++ b/absl/random/zipf_distribution_test.cc
@@ -0,0 +1,423 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/random/zipf_distribution.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <iterator>
+#include <random>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/internal/raw_logging.h"
+#include "absl/random/internal/chi_square.h"
+#include "absl/random/internal/sequence_urbg.h"
+#include "absl/random/random.h"
+#include "absl/strings/str_cat.h"
+#include "absl/strings/str_replace.h"
+#include "absl/strings/strip.h"
+
+namespace {
+
+using ::absl::random_internal::kChiSquared;
+using ::testing::ElementsAre;
+
+template <typename IntType>
+class ZipfDistributionTypedTest : public ::testing::Test {};
+
+using IntTypes = ::testing::Types<int, int8_t, int16_t, int32_t, int64_t,
+                                  uint8_t, uint16_t, uint32_t, uint64_t>;
+TYPED_TEST_CASE(ZipfDistributionTypedTest, IntTypes);
+
+TYPED_TEST(ZipfDistributionTypedTest, SerializeTest) {
+  using param_type = typename absl::zipf_distribution<TypeParam>::param_type;
+
+  constexpr int kCount = 1000;
+  absl::InsecureBitGen gen;
+  for (const auto& param : {
+           param_type(),
+           param_type(32),
+           param_type(100, 3, 2),
+           param_type(std::numeric_limits<TypeParam>::max(), 4, 3),
+           param_type(std::numeric_limits<TypeParam>::max() / 2),
+       }) {
+    // Validate parameters.
+    const auto k = param.k();
+    const auto q = param.q();
+    const auto v = param.v();
+
+    absl::zipf_distribution<TypeParam> before(k, q, v);
+    EXPECT_EQ(before.k(), param.k());
+    EXPECT_EQ(before.q(), param.q());
+    EXPECT_EQ(before.v(), param.v());
+
+    {
+      absl::zipf_distribution<TypeParam> via_param(param);
+      EXPECT_EQ(via_param, before);
+    }
+
+    // Validate stream serialization.
+    std::stringstream ss;
+    ss << before;
+    absl::zipf_distribution<TypeParam> after(4, 5.5, 4.4);
+
+    EXPECT_NE(before.k(), after.k());
+    EXPECT_NE(before.q(), after.q());
+    EXPECT_NE(before.v(), after.v());
+    EXPECT_NE(before.param(), after.param());
+    EXPECT_NE(before, after);
+
+    ss >> after;
+
+    EXPECT_EQ(before.k(), after.k());
+    EXPECT_EQ(before.q(), after.q());
+    EXPECT_EQ(before.v(), after.v());
+    EXPECT_EQ(before.param(), after.param());
+    EXPECT_EQ(before, after);
+
+    // Smoke test.
+    auto sample_min = after.max();
+    auto sample_max = after.min();
+    for (int i = 0; i < kCount; i++) {
+      auto sample = after(gen);
+      EXPECT_GE(sample, after.min());
+      EXPECT_LE(sample, after.max());
+      if (sample > sample_max) sample_max = sample;
+      if (sample < sample_min) sample_min = sample;
+    }
+    ABSL_INTERNAL_LOG(INFO,
+                      absl::StrCat("Range: ", +sample_min, ", ", +sample_max));
+  }
+}
+
+class ZipfModel {
+ public:
+  ZipfModel(size_t k, double q, double v) : k_(k), q_(q), v_(v) {}
+
+  double mean() const { return mean_; }
+
+  // For the other moments of the Zipf distribution, see, for example,
+  // http://mathworld.wolfram.com/ZipfDistribution.html
+
+  // PMF(k) = (1 / k^s) / H(N,s)
+  // Returns the probability that any single invocation returns k.
+  double PMF(size_t i) { return i >= hnq_.size() ? 0.0 : hnq_[i] / sum_hnq_; }
+
+  // CDF = H(k, s) / H(N,s)
+  double CDF(size_t i) {
+    if (i >= hnq_.size()) {
+      return 1.0;
+    }
+    auto it = std::begin(hnq_);
+    double h = 0.0;
+    for (const auto end = it; it != end; it++) {
+      h += *it;
+    }
+    return h / sum_hnq_;
+  }
+
+  // The InverseCDF returns the k values which bound p on the upper and lower
+  // bound. Since there is no closed-form solution, this is implemented as a
+  // bisction of the cdf.
+  std::pair<size_t, size_t> InverseCDF(double p) {
+    size_t min = 0;
+    size_t max = hnq_.size();
+    while (max > min + 1) {
+      size_t target = (max + min) >> 1;
+      double x = CDF(target);
+      if (x > p) {
+        max = target;
+      } else {
+        min = target;
+      }
+    }
+    return {min, max};
+  }
+
+  // Compute the probability totals, which are based on the generalized harmonic
+  // number, H(N,s).
+  //   H(N,s) == SUM(k=1..N, 1 / k^s)
+  //
+  // In the limit, H(N,s) == zetac(s) + 1.
+  //
+  // NOTE: The mean of a zipf distribution could be computed here as well.
+  // Mean :=  H(N, s-1) / H(N,s).
+  // Given the parameter v = 1, this gives the following function:
+  // (Hn(100, 1) - Hn(1,1)) / (Hn(100,2) - Hn(1,2)) = 6.5944
+  //
+  void Init() {
+    if (!hnq_.empty()) {
+      return;
+    }
+    hnq_.clear();
+    hnq_.reserve(std::min(k_, size_t{1000}));
+
+    sum_hnq_ = 0;
+    double qm1 = q_ - 1.0;
+    double sum_hnq_m1 = 0;
+    for (size_t i = 0; i < k_; i++) {
+      // Partial n-th generalized harmonic number
+      const double x = v_ + i;
+
+      // H(n, q-1)
+      const double hnqm1 =
+          (q_ == 2.0) ? (1.0 / x)
+                      : (q_ == 3.0) ? (1.0 / (x * x)) : std::pow(x, -qm1);
+      sum_hnq_m1 += hnqm1;
+
+      // H(n, q)
+      const double hnq =
+          (q_ == 2.0) ? (1.0 / (x * x))
+                      : (q_ == 3.0) ? (1.0 / (x * x * x)) : std::pow(x, -q_);
+      sum_hnq_ += hnq;
+      hnq_.push_back(hnq);
+      if (i > 1000 && hnq <= 1e-10) {
+        // The harmonic number is too small.
+        break;
+      }
+    }
+    assert(sum_hnq_ > 0);
+    mean_ = sum_hnq_m1 / sum_hnq_;
+  }
+
+ private:
+  const size_t k_;
+  const double q_;
+  const double v_;
+
+  double mean_;
+  std::vector<double> hnq_;
+  double sum_hnq_;
+};
+
+using zipf_u64 = absl::zipf_distribution<uint64_t>;
+
+class ZipfTest : public testing::TestWithParam<zipf_u64::param_type>,
+                 public ZipfModel {
+ public:
+  ZipfTest() : ZipfModel(GetParam().k(), GetParam().q(), GetParam().v()) {}
+
+  absl::InsecureBitGen rng_;
+};
+
+TEST_P(ZipfTest, ChiSquaredTest) {
+  const auto& param = GetParam();
+  Init();
+
+  size_t trials = 10000;
+
+  // Find the split-points for the buckets.
+  std::vector<size_t> points;
+  std::vector<double> expected;
+  {
+    double last_cdf = 0.0;
+    double min_p = 1.0;
+    for (double p = 0.01; p < 1.0; p += 0.01) {
+      auto x = InverseCDF(p);
+      if (points.empty() || points.back() < x.second) {
+        const double p = CDF(x.second);
+        points.push_back(x.second);
+        double q = p - last_cdf;
+        expected.push_back(q);
+        last_cdf = p;
+        if (q < min_p) {
+          min_p = q;
+        }
+      }
+    }
+    if (last_cdf < 0.999) {
+      points.push_back(std::numeric_limits<size_t>::max());
+      double q = 1.0 - last_cdf;
+      expected.push_back(q);
+      if (q < min_p) {
+        min_p = q;
+      }
+    } else {
+      points.back() = std::numeric_limits<size_t>::max();
+      expected.back() += (1.0 - last_cdf);
+    }
+    // The Chi-Squared score is not completely scale-invariant; it works best
+    // when the small values are in the small digits.
+    trials = static_cast<size_t>(8.0 / min_p);
+  }
+  ASSERT_GT(points.size(), 0);
+
+  // Generate n variates and fill the counts vector with the count of their
+  // occurrences.
+  std::vector<int64_t> buckets(points.size(), 0);
+  double avg = 0;
+  {
+    zipf_u64 dis(param);
+    for (size_t i = 0; i < trials; i++) {
+      uint64_t x = dis(rng_);
+      ASSERT_LE(x, dis.max());
+      ASSERT_GE(x, dis.min());
+      avg += static_cast<double>(x);
+      auto it = std::upper_bound(std::begin(points), std::end(points),
+                                 static_cast<size_t>(x));
+      buckets[std::distance(std::begin(points), it)]++;
+    }
+    avg = avg / static_cast<double>(trials);
+  }
+
+  // Validate the output using the Chi-Squared test.
+  for (auto& e : expected) {
+    e *= trials;
+  }
+
+  // The null-hypothesis is that the distribution is a poisson distribution with
+  // the provided mean (not estimated from the data).
+  const int dof = static_cast<int>(expected.size()) - 1;
+
+  // NOTE: This test runs about 15x per invocation, so a value of 0.9995 is
+  // approximately correct for a test suite failure rate of 1 in 100.  In
+  // practice we see failures slightly higher than that.
+  const double threshold = absl::random_internal::ChiSquareValue(dof, 0.9999);
+
+  const double chi_square = absl::random_internal::ChiSquare(
+      std::begin(buckets), std::end(buckets), std::begin(expected),
+      std::end(expected));
+
+  const double p_actual =
+      absl::random_internal::ChiSquarePValue(chi_square, dof);
+
+  // Log if the chi_squared value is above the threshold.
+  if (chi_square > threshold) {
+    ABSL_INTERNAL_LOG(INFO, "values");
+    for (size_t i = 0; i < expected.size(); i++) {
+      ABSL_INTERNAL_LOG(INFO, absl::StrCat(points[i], ": ", buckets[i],
+                                           " vs. E=", expected[i]));
+    }
+    ABSL_INTERNAL_LOG(INFO, absl::StrCat("trials ", trials));
+    ABSL_INTERNAL_LOG(INFO,
+                      absl::StrCat("mean ", avg, " vs. expected ", mean()));
+    ABSL_INTERNAL_LOG(INFO, absl::StrCat(kChiSquared, "(data, ", dof, ") = ",
+                                         chi_square, " (", p_actual, ")"));
+    ABSL_INTERNAL_LOG(INFO,
+                      absl::StrCat(kChiSquared, " @ 0.9995 = ", threshold));
+    FAIL() << kChiSquared << " value of " << chi_square
+           << " is above the threshold.";
+  }
+}
+
+std::vector<zipf_u64::param_type> GenParams() {
+  using param = zipf_u64::param_type;
+  const auto k = param().k();
+  const auto q = param().q();
+  const auto v = param().v();
+  const uint64_t k2 = 1 << 10;
+  return std::vector<zipf_u64::param_type>{
+      // Default
+      param(k, q, v),
+      // vary K
+      param(4, q, v), param(1 << 4, q, v), param(k2, q, v),
+      // vary V
+      param(k2, q, 0.5), param(k2, q, 1.5), param(k2, q, 2.5), param(k2, q, 10),
+      // vary Q
+      param(k2, 1.5, v), param(k2, 3, v), param(k2, 5, v), param(k2, 10, v),
+      // Vary V & Q
+      param(k2, 1.5, 0.5), param(k2, 3, 1.5), param(k, 10, 10)};
+}
+
+std::string ParamName(
+    const ::testing::TestParamInfo<zipf_u64::param_type>& info) {
+  const auto& p = info.param;
+  std::string name = absl::StrCat("k_", p.k(), "__q_", absl::SixDigits(p.q()),
+                                  "__v_", absl::SixDigits(p.v()));
+  return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}});
+}
+
+INSTANTIATE_TEST_SUITE_P(All, ZipfTest, ::testing::ValuesIn(GenParams()),
+                         ParamName);
+
+// NOTE: absl::zipf_distribution is not guaranteed to be stable.
+TEST(ZipfDistributionTest, StabilityTest) {
+  // absl::zipf_distribution stability relies on
+  // absl::uniform_real_distribution, std::log, std::exp, std::log1p
+  absl::random_internal::sequence_urbg urbg(
+      {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull,
+       0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull,
+       0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull,
+       0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull});
+
+  std::vector<int> output(10);
+
+  {
+    absl::zipf_distribution<int32_t> dist;
+    std::generate(std::begin(output), std::end(output),
+                  [&] { return dist(urbg); });
+    EXPECT_THAT(output, ElementsAre(10031, 0, 0, 3, 6, 0, 7, 47, 0, 0));
+  }
+  urbg.reset();
+  {
+    absl::zipf_distribution<int32_t> dist(std::numeric_limits<int32_t>::max(),
+                                          3.3);
+    std::generate(std::begin(output), std::end(output),
+                  [&] { return dist(urbg); });
+    EXPECT_THAT(output, ElementsAre(44, 0, 0, 0, 0, 1, 0, 1, 3, 0));
+  }
+}
+
+TEST(ZipfDistributionTest, AlgorithmBounds) {
+  absl::zipf_distribution<int32_t> dist;
+
+  // Small values from absl::uniform_real_distribution map to larger Zipf
+  // distribution values.
+  const std::pair<uint64_t, int32_t> kInputs[] = {
+      {0xffffffffffffffff, 0x0}, {0x7fffffffffffffff, 0x0},
+      {0x3ffffffffffffffb, 0x1}, {0x1ffffffffffffffd, 0x4},
+      {0xffffffffffffffe, 0x9},  {0x7ffffffffffffff, 0x12},
+      {0x3ffffffffffffff, 0x25}, {0x1ffffffffffffff, 0x4c},
+      {0xffffffffffffff, 0x99},  {0x7fffffffffffff, 0x132},
+      {0x3fffffffffffff, 0x265}, {0x1fffffffffffff, 0x4cc},
+      {0xfffffffffffff, 0x999},  {0x7ffffffffffff, 0x1332},
+      {0x3ffffffffffff, 0x2665}, {0x1ffffffffffff, 0x4ccc},
+      {0xffffffffffff, 0x9998},  {0x7fffffffffff, 0x1332f},
+      {0x3fffffffffff, 0x2665a}, {0x1fffffffffff, 0x4cc9e},
+      {0xfffffffffff, 0x998e0},  {0x7ffffffffff, 0x133051},
+      {0x3ffffffffff, 0x265ae4}, {0x1ffffffffff, 0x4c9ed3},
+      {0xffffffffff, 0x98e223},  {0x7fffffffff, 0x13058c4},
+      {0x3fffffffff, 0x25b178e}, {0x1fffffffff, 0x4a062b2},
+      {0xfffffffff, 0x8ee23b8},  {0x7ffffffff, 0x10b21642},
+      {0x3ffffffff, 0x1d89d89d}, {0x1ffffffff, 0x2fffffff},
+      {0xffffffff, 0x45d1745d},  {0x7fffffff, 0x5a5a5a5a},
+      {0x3fffffff, 0x69ee5846},  {0x1fffffff, 0x73ecade3},
+      {0xfffffff, 0x79a9d260},   {0x7ffffff, 0x7cc0532b},
+      {0x3ffffff, 0x7e5ad146},   {0x1ffffff, 0x7f2c0bec},
+      {0xffffff, 0x7f95adef},    {0x7fffff, 0x7fcac0da},
+      {0x3fffff, 0x7fe55ae2},    {0x1fffff, 0x7ff2ac0e},
+      {0xfffff, 0x7ff955ae},     {0x7ffff, 0x7ffcaac1},
+      {0x3ffff, 0x7ffe555b},     {0x1ffff, 0x7fff2aac},
+      {0xffff, 0x7fff9556},      {0x7fff, 0x7fffcaab},
+      {0x3fff, 0x7fffe555},      {0x1fff, 0x7ffff2ab},
+      {0xfff, 0x7ffff955},       {0x7ff, 0x7ffffcab},
+      {0x3ff, 0x7ffffe55},       {0x1ff, 0x7fffff2b},
+      {0xff, 0x7fffff95},        {0x7f, 0x7fffffcb},
+      {0x3f, 0x7fffffe5},        {0x1f, 0x7ffffff3},
+      {0xf, 0x7ffffff9},         {0x7, 0x7ffffffd},
+      {0x3, 0x7ffffffe},         {0x1, 0x7fffffff},
+  };
+
+  for (const auto& instance : kInputs) {
+    absl::random_internal::sequence_urbg urbg({instance.first});
+    EXPECT_EQ(instance.second, dist(urbg));
+  }
+}
+
+}  // namespace