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