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