prng.spec.ts (5183B)
1 export const description = ` 2 Unittests for the pseudo random number generator 3 `; 4 5 import { makeTestGroup } from '../common/framework/test_group.js'; 6 import { fullU32Range } from '../webgpu/util/math.js'; 7 import { PRNG } from '../webgpu/util/prng.js'; 8 9 import { UnitTest } from './unit_test.js'; 10 11 export const g = makeTestGroup(UnitTest); 12 13 // There exist more formal tests for the quality of random number generators 14 // that are out of the scope for testing here (and are checked against the 15 // original C implementation). 16 // These tests are just intended to be smoke tests for implementation. 17 18 // Test against the reference u32 values from the original C implementation 19 // https://github.com/MersenneTwister-Lab/TinyMT/blob/master/tinymt/check32.out.txt 20 g.test('check').fn(t => { 21 const p = new PRNG(1); 22 // prettier-ignore 23 const expected = [ 24 2545341989, 981918433, 3715302833, 2387538352, 3591001365, 25 3820442102, 2114400566, 2196103051, 2783359912, 764534509, 26 643179475, 1822416315, 881558334, 4207026366, 3690273640, 27 3240535687, 2921447122, 3984931427, 4092394160, 44209675, 28 2188315343, 2908663843, 1834519336, 3774670961, 3019990707, 29 4065554902, 1239765502, 4035716197, 3412127188, 552822483, 30 161364450, 353727785, 140085994, 149132008, 2547770827, 31 4064042525, 4078297538, 2057335507, 622384752, 2041665899, 32 2193913817, 1080849512, 33160901, 662956935, 642999063, 33 3384709977, 1723175122, 3866752252, 521822317, 2292524454, 34 ]; 35 expected.forEach((_, i) => { 36 const val = p.randomU32(); 37 t.expect( 38 val === expected[i], 39 `PRNG(1) failed produced the ${i}th expected item, ${val} instead of ${expected[i]})` 40 ); 41 }); 42 }); 43 44 // Prove that generator is deterministic for at least 1000 values with different 45 // seeds. 46 g.test('deterministic_random').fn(t => { 47 fullU32Range().forEach(seed => { 48 const lhs = new PRNG(seed); 49 const rhs = new PRNG(seed); 50 for (let i = 0; i < 1000; i++) { 51 const lhs_val = lhs.random(); 52 const rhs_val = rhs.random(); 53 t.expect( 54 lhs_val === rhs_val, 55 `For seed ${seed}, the ${i}th item, PRNG was non-deterministic (${lhs_val} vs ${rhs_val})` 56 ); 57 } 58 }); 59 }); 60 61 g.test('deterministic_randomU32').fn(t => { 62 fullU32Range().forEach(seed => { 63 const lhs = new PRNG(seed); 64 const rhs = new PRNG(seed); 65 for (let i = 0; i < 1000; i++) { 66 const lhs_val = lhs.randomU32(); 67 const rhs_val = rhs.randomU32(); 68 t.expect( 69 lhs_val === rhs_val, 70 `For seed ${seed}, the ${i}th item, PRNG was non-deterministic (${lhs_val} vs ${rhs_val})` 71 ); 72 } 73 }); 74 }); 75 76 // Returns 2**k, for integer k up to and including 32. 77 function power_of_2(k: number) { 78 // The shift operator on integers returns a signed 32 bit integer. 79 // So break up this calculation to avoid wraparound. 80 if (k < 30) { 81 return 1 << k; 82 } 83 return (1 << 30) * (1 << (k - 30)); 84 } 85 86 g.test('uniformInt_range') 87 .desc('Outputs of uniformInt(N) are between 0 and N-1') 88 .fn(t => { 89 [1, 42, 99].forEach(seed => { 90 const p = new PRNG(seed); 91 for (let k = 0; k < 32; k++) { 92 const N = power_of_2(k); 93 for (let i = 0; i < 20; i++) { 94 const sample = p.uniformInt(N); 95 t.expect( 96 0 <= sample && sample < N, 97 `Sample from [0, ${N - 1}] is out of bounds: ${sample}` 98 ); 99 t.expect(sample === Math.trunc(sample), `Sample should be an integer: ${sample}`); 100 } 101 } 102 }); 103 }); 104 105 g.test('uniformInt_distribution') 106 .desc('uniformInt outputs are not biased: histogram counts are close to the expected mean') 107 .fn(t => { 108 const p = new PRNG(42); 109 const numBins = 4; 110 const numSamples = 1000; 111 const histogram = Array(numBins).fill(0); 112 for (let i = 0; i < numSamples; i++) { 113 histogram[p.uniformInt(numBins)]++; 114 } 115 // Each bin should have roughly the expected number of hits. 116 const meanCount = numSamples / numBins; 117 const toleratedMin = meanCount * 0.9; 118 const toleratedMax = meanCount * 1.1; 119 histogram.forEach(count => { 120 t.expect(count >= toleratedMin, `count is ${count}, less than tolerated min ${toleratedMin}`); 121 t.expect(count <= toleratedMax, `count is ${count}, more than tolerated min ${toleratedMax}`); 122 }); 123 }); 124 125 g.test('uniformInt_bias') 126 .desc('uniformInt does not demonstrate bias expected of randInt() % N') 127 .fn(t => { 128 const p = new PRNG(43); 129 // A bad random generator would be: randomU32() % N. 130 // For N = (2**32) * 2/3, we would expect the result to be less than N/2 about 2/3 of the time. 131 const badN = Math.trunc((1 << 15) * ((1 << 16) / 3)); 132 const halfN = badN / 2; 133 let numSmall = 0; 134 const numSamples = 1000; 135 for (let i = 0; i < numSamples; i++) { 136 const val = p.uniformInt(badN); 137 if (val < halfN) { 138 numSmall++; 139 } 140 } 141 t.expect( 142 numSmall > 0.45 * numSamples, 143 `uniformInt is biased: too few small samples (${numSmall} / ${numSamples})` 144 ); 145 t.expect( 146 numSmall < 0.55 * numSamples, 147 `uniformInt is biased: too many big samples (${numSamples - numSmall} / ${numSamples})` 148 ); 149 });