3 Copyright (C) 2010-2014 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 #include "util/numeric.h"
23 #include "exceptions.h"
26 class TestRandom : public TestBase {
28 TestRandom() { TestManager::registerTestModule(this); }
29 const char *getName() { return "TestRandom"; }
31 void runTests(IGameDef *gamedef);
33 void testPseudoRandom();
34 void testPseudoRandomRange();
36 void testPcgRandomRange();
37 void testPcgRandomBytes();
38 void testPcgRandomNormalDist();
40 static const int expected_pseudorandom_results[256];
41 static const u32 expected_pcgrandom_results[256];
42 static const u8 expected_pcgrandom_bytes_result[24];
43 static const u8 expected_pcgrandom_bytes_result2[24];
46 static TestRandom g_test_instance;
48 void TestRandom::runTests(IGameDef *gamedef)
50 TEST(testPseudoRandom);
51 TEST(testPseudoRandomRange);
53 TEST(testPcgRandomRange);
54 TEST(testPcgRandomBytes);
55 TEST(testPcgRandomNormalDist);
58 ////////////////////////////////////////////////////////////////////////////////
60 void TestRandom::testPseudoRandom()
62 PseudoRandom pr(814538);
64 for (u32 i = 0; i != 256; i++)
65 UASSERTEQ(int, pr.next(), expected_pseudorandom_results[i]);
69 void TestRandom::testPseudoRandomRange()
71 PseudoRandom pr((int)time(NULL));
73 EXCEPTION_CHECK(PrngException, pr.range(2000, 6000));
74 EXCEPTION_CHECK(PrngException, pr.range(5, 1));
76 for (u32 i = 0; i != 32768; i++) {
77 int min = (pr.next() % 3000) - 500;
78 int max = (pr.next() % 3000) - 500;
82 int randval = pr.range(min, max);
83 UASSERT(randval >= min);
84 UASSERT(randval <= max);
89 void TestRandom::testPcgRandom()
91 PcgRandom pr(814538, 998877);
93 for (u32 i = 0; i != 256; i++)
94 UASSERTEQ(u32, pr.next(), expected_pcgrandom_results[i]);
98 void TestRandom::testPcgRandomRange()
100 PcgRandom pr((int)time(NULL));
102 EXCEPTION_CHECK(PrngException, pr.range(5, 1));
104 // Regression test for bug 3027
105 pr.range(pr.RANDOM_MIN, pr.RANDOM_MAX);
107 for (u32 i = 0; i != 32768; i++) {
108 int min = (pr.next() % 3000) - 500;
109 int max = (pr.next() % 3000) - 500;
113 int randval = pr.range(min, max);
114 UASSERT(randval >= min);
115 UASSERT(randval <= max);
120 void TestRandom::testPcgRandomBytes()
123 PcgRandom r(1538, 877);
125 memset(buf, 0, sizeof(buf));
126 r.bytes(buf + 5, 23);
127 UASSERT(memcmp(buf + 5, expected_pcgrandom_bytes_result,
128 sizeof(expected_pcgrandom_bytes_result)) == 0);
130 memset(buf, 0, sizeof(buf));
132 UASSERT(memcmp(buf, expected_pcgrandom_bytes_result2,
133 sizeof(expected_pcgrandom_bytes_result2)) == 0);
137 void TestRandom::testPcgRandomNormalDist()
139 static const int max = 120;
140 static const int min = -120;
141 static const int num_trials = 20;
142 static const u32 num_samples = 61000;
143 s32 bins[max - min + 1];
144 memset(bins, 0, sizeof(bins));
146 PcgRandom r(486179 + (int)time(NULL));
148 for (u32 i = 0; i != num_samples; i++) {
149 s32 randval = r.randNormalDist(min, max, num_trials);
150 UASSERT(randval <= max);
151 UASSERT(randval >= min);
152 bins[randval - min]++;
155 // Note that here we divide variance by the number of trials;
156 // this is because variance is a biased estimator.
157 int range = (max - min + 1);
158 float mean = (max + min) / 2;
159 float variance = ((range * range - 1) / 12) / num_trials;
160 float stddev = sqrt(variance);
162 static const float prediction_intervals[] = {
170 //// Simple normality test using the 68-95-99.7% rule
171 for (u32 i = 0; i != ARRLEN(prediction_intervals); i++) {
172 float deviations = i / 2.f + 1.f;
173 int lbound = myround(mean - deviations * stddev);
174 int ubound = myround(mean + deviations * stddev);
175 UASSERT(lbound >= min);
176 UASSERT(ubound <= max);
179 for (int j = lbound; j != ubound; j++)
180 accum += bins[j - min];
182 float actual = (float)accum / num_samples;
183 UASSERT(fabs(actual - prediction_intervals[i]) < 0.02);
188 const int TestRandom::expected_pseudorandom_results[256] = {
189 0x02fa, 0x60d5, 0x6c10, 0x606b, 0x098b, 0x5f1e, 0x4f56, 0x3fbd, 0x77af,
190 0x4fe9, 0x419a, 0x6fe1, 0x177b, 0x6858, 0x36f8, 0x6d83, 0x14fc, 0x2d62,
191 0x1077, 0x23e2, 0x041b, 0x7a7e, 0x5b52, 0x215d, 0x682b, 0x4716, 0x47e3,
192 0x08c0, 0x1952, 0x56ae, 0x146d, 0x4b4f, 0x239f, 0x3fd0, 0x6794, 0x7796,
193 0x7be2, 0x75b7, 0x5691, 0x28ee, 0x2656, 0x40c0, 0x133c, 0x63cd, 0x2aeb,
194 0x518f, 0x7dbc, 0x6ad8, 0x736e, 0x5b05, 0x160b, 0x589f, 0x6f64, 0x5edc,
195 0x092c, 0x0a39, 0x199e, 0x1927, 0x562b, 0x2689, 0x3ba3, 0x366f, 0x46da,
196 0x4e49, 0x0abb, 0x40a1, 0x3846, 0x40db, 0x7adb, 0x6ec1, 0x6efa, 0x01cc,
197 0x6335, 0x4352, 0x72fb, 0x4b2d, 0x509a, 0x257e, 0x2f7d, 0x5891, 0x2195,
198 0x6107, 0x5269, 0x56e3, 0x4849, 0x38f7, 0x2791, 0x04f2, 0x4e05, 0x78ff,
199 0x6bae, 0x50b3, 0x74ad, 0x31af, 0x531e, 0x7d56, 0x11c9, 0x0b5e, 0x405e,
200 0x1e15, 0x7f6a, 0x5bd3, 0x6649, 0x71b4, 0x3ec2, 0x6ab4, 0x520e, 0x6ad6,
201 0x287e, 0x10b8, 0x18f2, 0x7107, 0x46ea, 0x1d85, 0x25cc, 0x2689, 0x35c1,
202 0x3065, 0x6237, 0x3edd, 0x23d9, 0x6fb5, 0x37a1, 0x3211, 0x526a, 0x4b09,
203 0x23f1, 0x58cc, 0x2e42, 0x341f, 0x5e16, 0x3d1a, 0x5e8c, 0x7a82, 0x4635,
204 0x2bf8, 0x6577, 0x3603, 0x1daf, 0x539f, 0x2e91, 0x6bd8, 0x42d3, 0x7a93,
205 0x26e3, 0x5a91, 0x6c67, 0x1b66, 0x3ac7, 0x18bf, 0x20d8, 0x7153, 0x558d,
206 0x7262, 0x653d, 0x417d, 0x3ed3, 0x3117, 0x600d, 0x6d04, 0x719c, 0x3afd,
207 0x6ba5, 0x17c5, 0x4935, 0x346c, 0x5479, 0x6ff6, 0x1fcc, 0x1054, 0x3f14,
208 0x6266, 0x3acc, 0x3b77, 0x71d8, 0x478b, 0x20fa, 0x4e46, 0x7e77, 0x5554,
209 0x3652, 0x719c, 0x072b, 0x61ad, 0x399f, 0x621d, 0x1bba, 0x41d0, 0x7fdc,
210 0x3e6c, 0x6a2a, 0x5253, 0x094e, 0x0c10, 0x3f43, 0x73eb, 0x4c5f, 0x1f23,
211 0x12c9, 0x0902, 0x5238, 0x50c0, 0x1b77, 0x3ffd, 0x0124, 0x302a, 0x26b9,
212 0x3648, 0x30a6, 0x1abc, 0x3031, 0x4029, 0x6358, 0x6696, 0x74e8, 0x6142,
213 0x4284, 0x0c00, 0x7e50, 0x41e3, 0x3782, 0x79a5, 0x60fe, 0x2d15, 0x3ed2,
214 0x7f70, 0x2b27, 0x6366, 0x5100, 0x7c44, 0x3ee0, 0x4e76, 0x7d34, 0x3a60,
215 0x140e, 0x613d, 0x1193, 0x268d, 0x1e2f, 0x3123, 0x6d61, 0x4e0b, 0x51ce,
216 0x13bf, 0x58d4, 0x4f43, 0x05c6, 0x4d6a, 0x7eb5, 0x2921, 0x2c36, 0x1c89,
217 0x63b9, 0x1555, 0x1f41, 0x2d9f,
220 const u32 TestRandom::expected_pcgrandom_results[256] = {
221 0x48c593f8, 0x054f59f5, 0x0d062dc1, 0x23852a23, 0x7fbbc97b, 0x1f9f141e,
222 0x364e6ed8, 0x995bba58, 0xc9307dc0, 0x73fb34c4, 0xcd8de88d, 0x52e8ce08,
223 0x1c4a78e4, 0x25c0882e, 0x8a82e2e0, 0xe3bc3311, 0xb8068d42, 0x73186110,
224 0x19988df4, 0x69bd970b, 0x7214728c, 0x0aee320c, 0x2a5a536c, 0xaf48d715,
225 0x00bce504, 0xd2b8f548, 0x520df366, 0x96d8fff5, 0xa1bb510b, 0x63477049,
226 0xb85990b7, 0x7e090689, 0x275fb468, 0x50206257, 0x8bab4f8a, 0x0d6823db,
227 0x63faeaac, 0x2d92deeb, 0x2ba78024, 0x0d30f631, 0x338923a0, 0xd07248d8,
228 0xa5db62d3, 0xddba8af6, 0x0ad454e9, 0x6f0fd13a, 0xbbfde2bf, 0x91188009,
229 0x966b394d, 0xbb9d2012, 0x7e6926cb, 0x95183860, 0x5ff4c59b, 0x035f628a,
230 0xb67085ef, 0x33867e23, 0x68d1b887, 0x2e3298d7, 0x84fd0650, 0x8bc91141,
231 0x6fcb0452, 0x2836fee9, 0x2e83c0a3, 0xf1bafdc5, 0x9ff77777, 0xfdfbba87,
232 0x527aebeb, 0x423e5248, 0xd1756490, 0xe41148fa, 0x3361f7b4, 0xa2824f23,
233 0xf4e08072, 0xc50442be, 0x35adcc21, 0x36be153c, 0xc7709012, 0xf0eeb9f2,
234 0x3d73114e, 0x1c1574ee, 0x92095b9c, 0x1503d01c, 0xd6ce0677, 0x026a8ec1,
235 0x76d0084d, 0x86c23633, 0x36f75ce6, 0x08fa7bbe, 0x35f6ff2a, 0x31cc9525,
236 0x2c1a35e6, 0x8effcd62, 0xc782fa07, 0x8a86e248, 0x8fdb7a9b, 0x77246626,
237 0x5767723f, 0x3a78b699, 0xe548ce1c, 0x5820f37d, 0x148ed9b8, 0xf6796254,
238 0x32232c20, 0x392bf3a2, 0xe9af6625, 0xd40b0d88, 0x636cfa23, 0x6a5de514,
239 0xc4a69183, 0xc785c853, 0xab0de901, 0x16ae7e44, 0x376f13b5, 0x070f7f31,
240 0x34cbc93b, 0xe6184345, 0x1b7f911f, 0x631fbe4b, 0x86d6e023, 0xc689b518,
241 0x88ef4f7c, 0xddf06b45, 0xc97f18d4, 0x2aaee94b, 0x45694723, 0x6db111d2,
242 0x91974fce, 0xe33e29e2, 0xc5e99494, 0x8017e02b, 0x3ebd8143, 0x471ffb80,
243 0xc0d7ca1b, 0x4954c860, 0x48935d6a, 0xf2d27999, 0xb93d608d, 0x40696e90,
244 0x60b18162, 0x1a156998, 0x09b8bbab, 0xc80a79b6, 0x8adbcfbc, 0xc375248c,
245 0xa584e2ea, 0x5b46fe11, 0x58e84680, 0x8a8bc456, 0xd668b94f, 0x8b9035be,
246 0x278509d4, 0x6663a140, 0x81a9817a, 0xd4f9d3cf, 0x6dc5f607, 0x6ae04450,
247 0x694f22a4, 0x1d061788, 0x2e39ad8b, 0x748f4db2, 0xee569b52, 0xd157166d,
248 0xdabc161e, 0xc8d50176, 0x7e3110e5, 0x9f7d033b, 0x128df67f, 0xb0078583,
249 0xa3a75d26, 0xc1ad8011, 0x07dd89ec, 0xef04f456, 0x91bf866c, 0x6aac5306,
250 0xdd5a1573, 0xf73ff97a, 0x4e1186ad, 0xb9680680, 0xc8894515, 0xdc95a08e,
251 0xc894fd8e, 0xf84ade15, 0xd787f8c1, 0x40dcecca, 0x1b24743e, 0x1ce6ab23,
252 0x72321653, 0xb80fbaf7, 0x1bcf099b, 0x1ff26805, 0x78f66c8e, 0xf93bf51a,
253 0xfb0c06fe, 0xe50d48cf, 0x310947e0, 0x1b78804a, 0xe73e2c14, 0x8deb8381,
254 0xe576122a, 0xe5a8df39, 0x42397c5e, 0xf5503f3c, 0xbe3dbf8d, 0x1b360e5c,
255 0x9254caaf, 0x7a9f6744, 0x6d4144fa, 0xd77c65fe, 0x44ca7b12, 0xf58a4c00,
256 0x159500d0, 0x92769857, 0x7134fdd4, 0xa3fea693, 0xbd044831, 0xeded39a1,
257 0xe4570204, 0xaea37f2f, 0x9a302971, 0x620f8402, 0x1d2f3e5e, 0xf9c2f49c,
258 0x738e813a, 0xb3c92251, 0x7ecba63b, 0xbe7eebc7, 0xf800267c, 0x3fdeb760,
259 0xf12d5e7d, 0x5a18dce1, 0xb35a539c, 0xe565f057, 0x2babf38c, 0xae5800ad,
260 0x421004dd, 0x6715acb6, 0xff529b64, 0xd520d207, 0x7cb193e7, 0xe9b18e4c,
261 0xfd2a8a59, 0x47826ae3, 0x56ba43f8, 0x453b3d99, 0x8ae1675f, 0xf66f5c34,
262 0x057a6ac1, 0x010769e4, 0xa8324158, 0x410379a5, 0x5dfc8c97, 0x72848afe,
263 0x59f169e5, 0xe32acb78, 0x5dfaa9c4, 0x51bb956a,
266 const u8 TestRandom::expected_pcgrandom_bytes_result[24] = {
267 0xf3, 0x79, 0x8f, 0x31, 0xac, 0xd9, 0x34, 0xf8, 0x3c, 0x6e, 0x82, 0x37,
268 0x6b, 0x4b, 0x77, 0xe3, 0xbd, 0x0a, 0xee, 0x22, 0x79, 0x6e, 0x40, 0x00,
271 const u8 TestRandom::expected_pcgrandom_bytes_result2[24] = {
272 0x47, 0x9e, 0x08, 0x3e, 0xd4, 0x21, 0x2d, 0xf6, 0xb4, 0xb1, 0x9d, 0x7a,
273 0x60, 0x02, 0x5a, 0xb2, 0x11, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,