1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/random/distributions.h"
16
17 #include <cmath>
18 #include <cstdint>
19 #include <random>
20 #include <vector>
21
22 #include "gtest/gtest.h"
23 #include "absl/random/internal/distribution_test_util.h"
24 #include "absl/random/random.h"
25
26 namespace {
27
28 constexpr int kSize = 400000;
29
30 class RandomDistributionsTest : public testing::Test {};
31
32
33 struct Invalid {};
34
35 template <typename A, typename B>
36 auto InferredUniformReturnT(int)
37 -> decltype(absl::Uniform(std::declval<absl::InsecureBitGen&>(),
38 std::declval<A>(), std::declval<B>()));
39
40 template <typename, typename>
41 Invalid InferredUniformReturnT(...);
42
43 template <typename TagType, typename A, typename B>
44 auto InferredTaggedUniformReturnT(int)
45 -> decltype(absl::Uniform(std::declval<TagType>(),
46 std::declval<absl::InsecureBitGen&>(),
47 std::declval<A>(), std::declval<B>()));
48
49 template <typename, typename, typename>
50 Invalid InferredTaggedUniformReturnT(...);
51
52 // Given types <A, B, Expect>, CheckArgsInferType() verifies that
53 //
54 // absl::Uniform(gen, A{}, B{})
55 //
56 // returns the type "Expect".
57 //
58 // This interface can also be used to assert that a given absl::Uniform()
59 // overload does not exist / will not compile. Given types <A, B>, the
60 // expression
61 //
62 // decltype(absl::Uniform(..., std::declval<A>(), std::declval<B>()))
63 //
64 // will not compile, leaving the definition of InferredUniformReturnT<A, B> to
65 // resolve (via SFINAE) to the overload which returns type "Invalid". This
66 // allows tests to assert that an invocation such as
67 //
68 // absl::Uniform(gen, 1.23f, std::numeric_limits<int>::max() - 1)
69 //
70 // should not compile, since neither type, float nor int, can precisely
71 // represent both endpoint-values. Writing:
72 //
73 // CheckArgsInferType<float, int, Invalid>()
74 //
75 // will assert that this overload does not exist.
76 template <typename A, typename B, typename Expect>
CheckArgsInferType()77 void CheckArgsInferType() {
78 static_assert(
79 absl::conjunction<
80 std::is_same<Expect, decltype(InferredUniformReturnT<A, B>(0))>,
81 std::is_same<Expect,
82 decltype(InferredUniformReturnT<B, A>(0))>>::value,
83 "");
84 static_assert(
85 absl::conjunction<
86 std::is_same<Expect, decltype(InferredTaggedUniformReturnT<
87 absl::IntervalOpenOpenTag, A, B>(0))>,
88 std::is_same<Expect,
89 decltype(InferredTaggedUniformReturnT<
90 absl::IntervalOpenOpenTag, B, A>(0))>>::value,
91 "");
92 }
93
94 template <typename A, typename B, typename ExplicitRet>
95 auto ExplicitUniformReturnT(int) -> decltype(
96 absl::Uniform<ExplicitRet>(*std::declval<absl::InsecureBitGen*>(),
97 std::declval<A>(), std::declval<B>()));
98
99 template <typename, typename, typename ExplicitRet>
100 Invalid ExplicitUniformReturnT(...);
101
102 template <typename TagType, typename A, typename B, typename ExplicitRet>
103 auto ExplicitTaggedUniformReturnT(int) -> decltype(absl::Uniform<ExplicitRet>(
104 std::declval<TagType>(), *std::declval<absl::InsecureBitGen*>(),
105 std::declval<A>(), std::declval<B>()));
106
107 template <typename, typename, typename, typename ExplicitRet>
108 Invalid ExplicitTaggedUniformReturnT(...);
109
110 // Given types <A, B, Expect>, CheckArgsReturnExpectedType() verifies that
111 //
112 // absl::Uniform<Expect>(gen, A{}, B{})
113 //
114 // returns the type "Expect", and that the function-overload has the signature
115 //
116 // Expect(URBG&, Expect, Expect)
117 template <typename A, typename B, typename Expect>
CheckArgsReturnExpectedType()118 void CheckArgsReturnExpectedType() {
119 static_assert(
120 absl::conjunction<
121 std::is_same<Expect,
122 decltype(ExplicitUniformReturnT<A, B, Expect>(0))>,
123 std::is_same<Expect, decltype(ExplicitUniformReturnT<B, A, Expect>(
124 0))>>::value,
125 "");
126 static_assert(
127 absl::conjunction<
128 std::is_same<Expect,
129 decltype(ExplicitTaggedUniformReturnT<
130 absl::IntervalOpenOpenTag, A, B, Expect>(0))>,
131 std::is_same<Expect, decltype(ExplicitTaggedUniformReturnT<
132 absl::IntervalOpenOpenTag, B, A,
133 Expect>(0))>>::value,
134 "");
135 }
136
TEST_F(RandomDistributionsTest,UniformTypeInference)137 TEST_F(RandomDistributionsTest, UniformTypeInference) {
138 // Infers common types.
139 CheckArgsInferType<uint16_t, uint16_t, uint16_t>();
140 CheckArgsInferType<uint32_t, uint32_t, uint32_t>();
141 CheckArgsInferType<uint64_t, uint64_t, uint64_t>();
142 CheckArgsInferType<int16_t, int16_t, int16_t>();
143 CheckArgsInferType<int32_t, int32_t, int32_t>();
144 CheckArgsInferType<int64_t, int64_t, int64_t>();
145 CheckArgsInferType<float, float, float>();
146 CheckArgsInferType<double, double, double>();
147
148 // Explicitly-specified return-values override inferences.
149 CheckArgsReturnExpectedType<int16_t, int16_t, int32_t>();
150 CheckArgsReturnExpectedType<uint16_t, uint16_t, int32_t>();
151 CheckArgsReturnExpectedType<int16_t, int16_t, int64_t>();
152 CheckArgsReturnExpectedType<int16_t, int32_t, int64_t>();
153 CheckArgsReturnExpectedType<int16_t, int32_t, double>();
154 CheckArgsReturnExpectedType<float, float, double>();
155 CheckArgsReturnExpectedType<int, int, int16_t>();
156
157 // Properly promotes uint16_t.
158 CheckArgsInferType<uint16_t, uint32_t, uint32_t>();
159 CheckArgsInferType<uint16_t, uint64_t, uint64_t>();
160 CheckArgsInferType<uint16_t, int32_t, int32_t>();
161 CheckArgsInferType<uint16_t, int64_t, int64_t>();
162 CheckArgsInferType<uint16_t, float, float>();
163 CheckArgsInferType<uint16_t, double, double>();
164
165 // Properly promotes int16_t.
166 CheckArgsInferType<int16_t, int32_t, int32_t>();
167 CheckArgsInferType<int16_t, int64_t, int64_t>();
168 CheckArgsInferType<int16_t, float, float>();
169 CheckArgsInferType<int16_t, double, double>();
170
171 // Invalid (u)int16_t-pairings do not compile.
172 // See "CheckArgsInferType" comments above, for how this is achieved.
173 CheckArgsInferType<uint16_t, int16_t, Invalid>();
174 CheckArgsInferType<int16_t, uint32_t, Invalid>();
175 CheckArgsInferType<int16_t, uint64_t, Invalid>();
176
177 // Properly promotes uint32_t.
178 CheckArgsInferType<uint32_t, uint64_t, uint64_t>();
179 CheckArgsInferType<uint32_t, int64_t, int64_t>();
180 CheckArgsInferType<uint32_t, double, double>();
181
182 // Properly promotes int32_t.
183 CheckArgsInferType<int32_t, int64_t, int64_t>();
184 CheckArgsInferType<int32_t, double, double>();
185
186 // Invalid (u)int32_t-pairings do not compile.
187 CheckArgsInferType<uint32_t, int32_t, Invalid>();
188 CheckArgsInferType<int32_t, uint64_t, Invalid>();
189 CheckArgsInferType<int32_t, float, Invalid>();
190 CheckArgsInferType<uint32_t, float, Invalid>();
191
192 // Invalid (u)int64_t-pairings do not compile.
193 CheckArgsInferType<uint64_t, int64_t, Invalid>();
194 CheckArgsInferType<int64_t, float, Invalid>();
195 CheckArgsInferType<int64_t, double, Invalid>();
196
197 // Properly promotes float.
198 CheckArgsInferType<float, double, double>();
199 }
200
TEST_F(RandomDistributionsTest,UniformExamples)201 TEST_F(RandomDistributionsTest, UniformExamples) {
202 // Examples.
203 absl::InsecureBitGen gen;
204 EXPECT_NE(1, absl::Uniform(gen, static_cast<uint16_t>(0), 1.0f));
205 EXPECT_NE(1, absl::Uniform(gen, 0, 1.0));
206 EXPECT_NE(1, absl::Uniform(absl::IntervalOpenOpen, gen,
207 static_cast<uint16_t>(0), 1.0f));
208 EXPECT_NE(1, absl::Uniform(absl::IntervalOpenOpen, gen, 0, 1.0));
209 EXPECT_NE(1, absl::Uniform(absl::IntervalOpenOpen, gen, -1, 1.0));
210 EXPECT_NE(1, absl::Uniform<double>(absl::IntervalOpenOpen, gen, -1, 1));
211 EXPECT_NE(1, absl::Uniform<float>(absl::IntervalOpenOpen, gen, 0, 1));
212 EXPECT_NE(1, absl::Uniform<float>(gen, 0, 1));
213 }
214
TEST_F(RandomDistributionsTest,UniformNoBounds)215 TEST_F(RandomDistributionsTest, UniformNoBounds) {
216 absl::InsecureBitGen gen;
217
218 absl::Uniform<uint8_t>(gen);
219 absl::Uniform<uint16_t>(gen);
220 absl::Uniform<uint32_t>(gen);
221 absl::Uniform<uint64_t>(gen);
222 }
223
TEST_F(RandomDistributionsTest,UniformNonsenseRanges)224 TEST_F(RandomDistributionsTest, UniformNonsenseRanges) {
225 // The ranges used in this test are undefined behavior.
226 // The results are arbitrary and subject to future changes.
227 absl::InsecureBitGen gen;
228
229 // <uint>
230 EXPECT_EQ(0, absl::Uniform<uint64_t>(gen, 0, 0));
231 EXPECT_EQ(1, absl::Uniform<uint64_t>(gen, 1, 0));
232 EXPECT_EQ(0, absl::Uniform<uint64_t>(absl::IntervalOpenOpen, gen, 0, 0));
233 EXPECT_EQ(1, absl::Uniform<uint64_t>(absl::IntervalOpenOpen, gen, 1, 0));
234
235 constexpr auto m = (std::numeric_limits<uint64_t>::max)();
236
237 EXPECT_EQ(m, absl::Uniform(gen, m, m));
238 EXPECT_EQ(m, absl::Uniform(gen, m, m - 1));
239 EXPECT_EQ(m - 1, absl::Uniform(gen, m - 1, m));
240 EXPECT_EQ(m, absl::Uniform(absl::IntervalOpenOpen, gen, m, m));
241 EXPECT_EQ(m, absl::Uniform(absl::IntervalOpenOpen, gen, m, m - 1));
242 EXPECT_EQ(m - 1, absl::Uniform(absl::IntervalOpenOpen, gen, m - 1, m));
243
244 // <int>
245 EXPECT_EQ(0, absl::Uniform<int64_t>(gen, 0, 0));
246 EXPECT_EQ(1, absl::Uniform<int64_t>(gen, 1, 0));
247 EXPECT_EQ(0, absl::Uniform<int64_t>(absl::IntervalOpenOpen, gen, 0, 0));
248 EXPECT_EQ(1, absl::Uniform<int64_t>(absl::IntervalOpenOpen, gen, 1, 0));
249
250 constexpr auto l = (std::numeric_limits<int64_t>::min)();
251 constexpr auto r = (std::numeric_limits<int64_t>::max)();
252
253 EXPECT_EQ(l, absl::Uniform(gen, l, l));
254 EXPECT_EQ(r, absl::Uniform(gen, r, r));
255 EXPECT_EQ(r, absl::Uniform(gen, r, r - 1));
256 EXPECT_EQ(r - 1, absl::Uniform(gen, r - 1, r));
257 EXPECT_EQ(l, absl::Uniform(absl::IntervalOpenOpen, gen, l, l));
258 EXPECT_EQ(r, absl::Uniform(absl::IntervalOpenOpen, gen, r, r));
259 EXPECT_EQ(r, absl::Uniform(absl::IntervalOpenOpen, gen, r, r - 1));
260 EXPECT_EQ(r - 1, absl::Uniform(absl::IntervalOpenOpen, gen, r - 1, r));
261
262 // <double>
263 const double e = std::nextafter(1.0, 2.0); // 1 + epsilon
264 const double f = std::nextafter(1.0, 0.0); // 1 - epsilon
265 const double g = std::numeric_limits<double>::denorm_min();
266
267 EXPECT_EQ(1.0, absl::Uniform(gen, 1.0, e));
268 EXPECT_EQ(1.0, absl::Uniform(gen, 1.0, f));
269 EXPECT_EQ(0.0, absl::Uniform(gen, 0.0, g));
270
271 EXPECT_EQ(e, absl::Uniform(absl::IntervalOpenOpen, gen, 1.0, e));
272 EXPECT_EQ(f, absl::Uniform(absl::IntervalOpenOpen, gen, 1.0, f));
273 EXPECT_EQ(g, absl::Uniform(absl::IntervalOpenOpen, gen, 0.0, g));
274 }
275
276 // TODO(lar): Validate properties of non-default interval-semantics.
TEST_F(RandomDistributionsTest,UniformReal)277 TEST_F(RandomDistributionsTest, UniformReal) {
278 std::vector<double> values(kSize);
279
280 absl::InsecureBitGen gen;
281 for (int i = 0; i < kSize; i++) {
282 values[i] = absl::Uniform(gen, 0, 1.0);
283 }
284
285 const auto moments =
286 absl::random_internal::ComputeDistributionMoments(values);
287 EXPECT_NEAR(0.5, moments.mean, 0.02);
288 EXPECT_NEAR(1 / 12.0, moments.variance, 0.02);
289 EXPECT_NEAR(0.0, moments.skewness, 0.02);
290 EXPECT_NEAR(9 / 5.0, moments.kurtosis, 0.02);
291 }
292
TEST_F(RandomDistributionsTest,UniformInt)293 TEST_F(RandomDistributionsTest, UniformInt) {
294 std::vector<double> values(kSize);
295
296 absl::InsecureBitGen gen;
297 for (int i = 0; i < kSize; i++) {
298 const int64_t kMax = 1000000000000ll;
299 int64_t j = absl::Uniform(absl::IntervalClosedClosed, gen, 0, kMax);
300 // convert to double.
301 values[i] = static_cast<double>(j) / static_cast<double>(kMax);
302 }
303
304 const auto moments =
305 absl::random_internal::ComputeDistributionMoments(values);
306 EXPECT_NEAR(0.5, moments.mean, 0.02);
307 EXPECT_NEAR(1 / 12.0, moments.variance, 0.02);
308 EXPECT_NEAR(0.0, moments.skewness, 0.02);
309 EXPECT_NEAR(9 / 5.0, moments.kurtosis, 0.02);
310
311 /*
312 // NOTE: These are not supported by absl::Uniform, which is specialized
313 // on integer and real valued types.
314
315 enum E { E0, E1 }; // enum
316 enum S : int { S0, S1 }; // signed enum
317 enum U : unsigned int { U0, U1 }; // unsigned enum
318
319 absl::Uniform(gen, E0, E1);
320 absl::Uniform(gen, S0, S1);
321 absl::Uniform(gen, U0, U1);
322 */
323 }
324
TEST_F(RandomDistributionsTest,Exponential)325 TEST_F(RandomDistributionsTest, Exponential) {
326 std::vector<double> values(kSize);
327
328 absl::InsecureBitGen gen;
329 for (int i = 0; i < kSize; i++) {
330 values[i] = absl::Exponential<double>(gen);
331 }
332
333 const auto moments =
334 absl::random_internal::ComputeDistributionMoments(values);
335 EXPECT_NEAR(1.0, moments.mean, 0.02);
336 EXPECT_NEAR(1.0, moments.variance, 0.025);
337 EXPECT_NEAR(2.0, moments.skewness, 0.1);
338 EXPECT_LT(5.0, moments.kurtosis);
339 }
340
TEST_F(RandomDistributionsTest,PoissonDefault)341 TEST_F(RandomDistributionsTest, PoissonDefault) {
342 std::vector<double> values(kSize);
343
344 absl::InsecureBitGen gen;
345 for (int i = 0; i < kSize; i++) {
346 values[i] = absl::Poisson<int64_t>(gen);
347 }
348
349 const auto moments =
350 absl::random_internal::ComputeDistributionMoments(values);
351 EXPECT_NEAR(1.0, moments.mean, 0.02);
352 EXPECT_NEAR(1.0, moments.variance, 0.02);
353 EXPECT_NEAR(1.0, moments.skewness, 0.025);
354 EXPECT_LT(2.0, moments.kurtosis);
355 }
356
TEST_F(RandomDistributionsTest,PoissonLarge)357 TEST_F(RandomDistributionsTest, PoissonLarge) {
358 constexpr double kMean = 100000000.0;
359 std::vector<double> values(kSize);
360
361 absl::InsecureBitGen gen;
362 for (int i = 0; i < kSize; i++) {
363 values[i] = absl::Poisson<int64_t>(gen, kMean);
364 }
365
366 const auto moments =
367 absl::random_internal::ComputeDistributionMoments(values);
368 EXPECT_NEAR(kMean, moments.mean, kMean * 0.015);
369 EXPECT_NEAR(kMean, moments.variance, kMean * 0.015);
370 EXPECT_NEAR(std::sqrt(kMean), moments.skewness, kMean * 0.02);
371 EXPECT_LT(2.0, moments.kurtosis);
372 }
373
TEST_F(RandomDistributionsTest,Bernoulli)374 TEST_F(RandomDistributionsTest, Bernoulli) {
375 constexpr double kP = 0.5151515151;
376 std::vector<double> values(kSize);
377
378 absl::InsecureBitGen gen;
379 for (int i = 0; i < kSize; i++) {
380 values[i] = absl::Bernoulli(gen, kP);
381 }
382
383 const auto moments =
384 absl::random_internal::ComputeDistributionMoments(values);
385 EXPECT_NEAR(kP, moments.mean, 0.01);
386 }
387
TEST_F(RandomDistributionsTest,Beta)388 TEST_F(RandomDistributionsTest, Beta) {
389 constexpr double kAlpha = 2.0;
390 constexpr double kBeta = 3.0;
391 std::vector<double> values(kSize);
392
393 absl::InsecureBitGen gen;
394 for (int i = 0; i < kSize; i++) {
395 values[i] = absl::Beta(gen, kAlpha, kBeta);
396 }
397
398 const auto moments =
399 absl::random_internal::ComputeDistributionMoments(values);
400 EXPECT_NEAR(0.4, moments.mean, 0.01);
401 }
402
TEST_F(RandomDistributionsTest,Zipf)403 TEST_F(RandomDistributionsTest, Zipf) {
404 std::vector<double> values(kSize);
405
406 absl::InsecureBitGen gen;
407 for (int i = 0; i < kSize; i++) {
408 values[i] = absl::Zipf<int64_t>(gen, 100);
409 }
410
411 // The mean of a zipf distribution is: H(N, s-1) / H(N,s).
412 // Given the parameter v = 1, this gives the following function:
413 // (Hn(100, 1) - Hn(1,1)) / (Hn(100,2) - Hn(1,2)) = 6.5944
414 const auto moments =
415 absl::random_internal::ComputeDistributionMoments(values);
416 EXPECT_NEAR(6.5944, moments.mean, 2000) << moments;
417 }
418
TEST_F(RandomDistributionsTest,Gaussian)419 TEST_F(RandomDistributionsTest, Gaussian) {
420 std::vector<double> values(kSize);
421
422 absl::InsecureBitGen gen;
423 for (int i = 0; i < kSize; i++) {
424 values[i] = absl::Gaussian<double>(gen);
425 }
426
427 const auto moments =
428 absl::random_internal::ComputeDistributionMoments(values);
429 EXPECT_NEAR(0.0, moments.mean, 0.02);
430 EXPECT_NEAR(1.0, moments.variance, 0.04);
431 EXPECT_NEAR(0, moments.skewness, 0.2);
432 EXPECT_NEAR(3.0, moments.kurtosis, 0.5);
433 }
434
TEST_F(RandomDistributionsTest,LogUniform)435 TEST_F(RandomDistributionsTest, LogUniform) {
436 std::vector<double> values(kSize);
437
438 absl::InsecureBitGen gen;
439 for (int i = 0; i < kSize; i++) {
440 values[i] = absl::LogUniform<int64_t>(gen, 0, (1 << 10) - 1);
441 }
442
443 // The mean is the sum of the fractional means of the uniform distributions:
444 // [0..0][1..1][2..3][4..7][8..15][16..31][32..63]
445 // [64..127][128..255][256..511][512..1023]
446 const double mean = (0 + 1 + 1 + 2 + 3 + 4 + 7 + 8 + 15 + 16 + 31 + 32 + 63 +
447 64 + 127 + 128 + 255 + 256 + 511 + 512 + 1023) /
448 (2.0 * 11.0);
449
450 const auto moments =
451 absl::random_internal::ComputeDistributionMoments(values);
452 EXPECT_NEAR(mean, moments.mean, 2) << moments;
453 }
454
455 } // namespace
456