src/unittest/test_random.cpp

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