1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // REQUIRES: long_tests
10
11 // <random>
12
13 // template<class _IntType = int>
14 // class uniform_int_distribution
15
16 // template<class _URNG> result_type operator()(_URNG& g);
17
18 #include <random>
19 #include <cassert>
20 #include <climits>
21 #include <cstddef>
22 #include <limits>
23 #include <numeric>
24 #include <vector>
25
26 #include "test_macros.h"
27
28 // The __int128 conversions to/from floating point crash on MinGW on x86_64.
29 // This is fixed in Clang 14 by https://reviews.llvm.org/D110413.
30 #if defined(__x86_64__) && defined(__MINGW32__) && defined(__clang_major__) && __clang_major__ < 14
31 #define TEST_BUGGY_I128_FP
32 #endif
33
34 template <class T>
sqr(T x)35 T sqr(T x) {
36 return x * x;
37 }
38
39 template <class ResultType, class EngineType>
test_statistics(ResultType a,ResultType b)40 void test_statistics(ResultType a, ResultType b) {
41 ASSERT_SAME_TYPE(typename std::uniform_int_distribution<ResultType>::result_type, ResultType);
42
43 EngineType g;
44 std::uniform_int_distribution<ResultType> dist(a, b);
45 assert(dist.a() == a);
46 assert(dist.b() == b);
47 std::vector<ResultType> u;
48 for (int i = 0; i < 10000; ++i) {
49 ResultType v = dist(g);
50 assert(a <= v && v <= b);
51 u.push_back(v);
52 }
53
54 // Quick check: The chance of getting *no* hits in any given tenth of the range
55 // is (0.9)^10000, or "ultra-astronomically low."
56 bool bottom_tenth = false;
57 bool top_tenth = false;
58 for (std::size_t i = 0; i < u.size(); ++i) {
59 bottom_tenth = bottom_tenth || (u[i] <= (a + (b / 10) - (a / 10)));
60 top_tenth = top_tenth || (u[i] >= (b - (b / 10) + (a / 10)));
61 }
62 assert(bottom_tenth); // ...is populated
63 assert(top_tenth); // ...is populated
64
65 // Now do some more involved statistical math.
66 double mean = std::accumulate(u.begin(), u.end(), 0.0) / u.size();
67 double var = 0;
68 double skew = 0;
69 double kurtosis = 0;
70 for (std::size_t i = 0; i < u.size(); ++i) {
71 double dbl = (u[i] - mean);
72 double d2 = dbl * dbl;
73 var += d2;
74 skew += dbl * d2;
75 kurtosis += d2 * d2;
76 }
77 var /= u.size();
78 double dev = std::sqrt(var);
79 skew /= u.size() * dev * var;
80 kurtosis /= u.size() * var * var;
81
82 double expected_mean = double(a) + double(b)/2 - double(a)/2;
83 double expected_var = (sqr(double(b) - double(a) + 1) - 1) / 12;
84
85 double range = double(b) - double(a) + 1.0;
86 assert(range > range / 10); // i.e., it's not infinity
87
88 assert(std::abs(mean - expected_mean) < range / 100);
89 assert(std::abs(var - expected_var) < expected_var / 50);
90 assert(-0.1 < skew && skew < 0.1);
91 assert(1.6 < kurtosis && kurtosis < 2.0);
92 }
93
94 template <class ResultType, class EngineType>
test_statistics()95 void test_statistics() {
96 test_statistics<ResultType, EngineType>(0, std::numeric_limits<ResultType>::max());
97 }
98
main(int,char **)99 int main(int, char**)
100 {
101 test_statistics<int, std::minstd_rand0>();
102 test_statistics<int, std::minstd_rand>();
103 test_statistics<int, std::mt19937>();
104 test_statistics<int, std::mt19937_64>();
105 test_statistics<int, std::ranlux24_base>();
106 test_statistics<int, std::ranlux48_base>();
107 test_statistics<int, std::ranlux24>();
108 test_statistics<int, std::ranlux48>();
109 test_statistics<int, std::knuth_b>();
110 test_statistics<int, std::minstd_rand0>(-6, 106);
111 test_statistics<int, std::minstd_rand>(5, 100);
112
113 test_statistics<short, std::minstd_rand0>();
114 test_statistics<int, std::minstd_rand0>();
115 test_statistics<long, std::minstd_rand0>();
116 test_statistics<long long, std::minstd_rand0>();
117
118 test_statistics<unsigned short, std::minstd_rand0>();
119 test_statistics<unsigned int, std::minstd_rand0>();
120 test_statistics<unsigned long, std::minstd_rand0>();
121 test_statistics<unsigned long long, std::minstd_rand0>();
122
123 test_statistics<short, std::minstd_rand0>(SHRT_MIN, SHRT_MAX);
124
125 #if defined(_LIBCPP_VERSION) // extension
126 test_statistics<int8_t, std::minstd_rand0>();
127 test_statistics<uint8_t, std::minstd_rand0>();
128
129 #if !defined(TEST_HAS_NO_INT128) && !defined(TEST_BUGGY_I128_FP)
130 test_statistics<__int128_t, std::minstd_rand0>();
131 test_statistics<__uint128_t, std::minstd_rand0>();
132
133 test_statistics<__int128_t, std::minstd_rand0>(-100, 900);
134 test_statistics<__int128_t, std::minstd_rand0>(0, UINT64_MAX);
135 test_statistics<__int128_t, std::minstd_rand0>(std::numeric_limits<__int128_t>::min(), std::numeric_limits<__int128_t>::max());
136 test_statistics<__uint128_t, std::minstd_rand0>(0, UINT64_MAX);
137 #endif
138 #endif
139
140 return 0;
141 }
142