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