Rigorous test for fix of issue 11598

results

rigorTest.d results:

Results for testableUniform = [33250, 33500, 33250]
Results for badUniform = [49890, 25242, 24868]
Test2 on testableUniform
---
i = 127
[78384, 78339, 78909, 79118, 78588, 78742, 78444, 78463, 78801, 78662, 79283, 79246, 78706, 78751, 78583, 79204, 79110, 78740, 78674, 78260, 78697, 79052, 79020, 79511, 78883, 78177, 78734, 79346, 78440, 79061, 78854, 78621, 78769, 78668, 78412, 78607, 78477, 78367, 78547, 78977, 78936, 79108, 79217, 78726, 78455, 78689, 78939, 78591, 78679, 78689, 78675, 78562, 78989, 79033, 78658, 78507, 78719, 78543, 78185, 78727, 78731, 78583, 78933, 78690, 78421, 78761, 78619, 78693, 78857, 78220, 78730, 79194, 78643, 78917, 78706, 78713, 78598, 79003, 78941, 78846, 78757, 78718, 78471, 78900, 79086, 78531, 78760, 78274, 78396, 78556, 78642, 79116, 78951, 79005, 78730, 78666, 79000, 78593, 79103, 78593, 78688, 78446, 78985, 78368, 78576, 78999, 78558, 78899, 78888, 78146, 78740, 79008, 78640, 78665, 79081, 78602, 78578, 78546, 78359, 78345, 79310, 78865, 79353, 79101, 78845, 78265, 78643]
---
i = 128
[78456, 78364, 77356, 78000, 78594, 78276, 78063, 78014, 77646, 77849, 77593, 77989, 77611, 78167, 77992, 78166, 78077, 78029, 77992, 78430, 77828, 77926, 78082, 77637, 78452, 78440, 77816, 77770, 78060, 78148, 78038, 78484, 77901, 77873, 78012, 78369, 78355, 78376, 77466, 77525, 78224, 77987, 77860, 78599, 78419, 78567, 77978, 78091, 78530, 78149, 78140, 78595, 78622, 77923, 78142, 77743, 78085, 77843, 77898, 78379, 78236, 78320, 77649, 77893, 78162, 78668, 77991, 78355, 77857, 77793, 78103, 78409, 78493, 78018, 78344, 78241, 77944, 78039, 78263, 78266, 78602, 78401, 78140, 78176, 77934, 78165, 77936, 78158, 78167, 78380, 78056, 77859, 78011, 78405, 77998, 78261, 78180, 78228, 77699, 78051, 78318, 78050, 77983, 77792, 78336, 77790, 78312, 78194, 78244, 78245, 77741, 78226, 78231, 78185, 78417, 78341, 77806, 78395, 78059, 78167, 77840, 77905, 78411, 78435, 78631, 78427, 78312, 78360]
---
i = 129
[77723, 77898, 77813, 77609, 77467, 78336, 77521, 77426, 77377, 77427, 77397, 77839, 77486, 77792, 77289, 77261, 77599, 77923, 77408, 77656, 77114, 77789, 77207, 77352, 77523, 77612, 77785, 77573, 77295, 77438, 77131, 76811, 77379, 77384, 77323, 77907, 77589, 77163, 77497, 77942, 77689, 77712, 77054, 77603, 77475, 77943, 77419, 77166, 77291, 77490, 77294, 77345, 77803, 77259, 77615, 77749, 77271, 77420, 77160, 77414, 77884, 77507, 77621, 77244, 77658, 77366, 77777, 77385, 77882, 77105, 77710, 77613, 77635, 77603, 76951, 76924, 77050, 77504, 78199, 77587, 77552, 77378, 77485, 77440, 77401, 77576, 77609, 77116, 77350, 77675, 77168, 77202, 77437, 77715, 77745, 77609, 77765, 76973, 77401, 77783, 77392, 77198, 78014, 77814, 77244, 77641, 77768, 77359, 77790, 77332, 77782, 78135, 77500, 77817, 77091, 77655, 77792, 77655, 77528, 77351, 77915, 77723, 77578, 77835, 76983, 77619, 77962, 77329, 77380]
---
Test2 on badUniform
---
i = 127
[116719, 116825, 78305, 78546, 78002, 78164, 77828, 77837, 78147, 78011, 78621, 78647, 78121, 78142, 77971, 78577, 78477, 78102, 78059, 77617, 78058, 78444, 78412, 78914, 78226, 77583, 78100, 78760, 77865, 78436, 78247, 78029, 78178, 78048, 77793, 77992, 77871, 77742, 77975, 78338, 78336, 78442, 78618, 78129, 77875, 78064, 78313, 77965, 78064, 78108, 78114, 77957, 78364, 78453, 78072, 77868, 78116, 77907, 77587, 78107, 78137, 77946, 78307, 78117, 77791, 78093, 78006, 78081, 78195, 77616, 78119, 78600, 78014, 78305, 78116, 78064, 77954, 78389, 78299, 78176, 78102, 78087, 77819, 78285, 78465, 77943, 78176, 77683, 77808, 77943, 78027, 78481, 78345, 78383, 78063, 78013, 78379, 77967, 78508, 77959, 78061, 77796, 78345, 77757, 77944, 78381, 77963, 78269, 78312, 77534, 78170, 78374, 78038, 78055, 78465, 78026, 77975, 77931, 77760, 77767, 78700, 78292, 78717, 78461, 78243, 77694, 78021]
---
i = 128
[78396, 78393, 77333, 77939, 78553, 78270, 78059, 78058, 77630, 77877, 77645, 77899, 77567, 78193, 78003, 78159, 78121, 78063, 78030, 78402, 77853, 77929, 78047, 77688, 78470, 78446, 77773, 77799, 78016, 78176, 78020, 78454, 77846, 77806, 77987, 78386, 78341, 78340, 77477, 77505, 78265, 78001, 77813, 78589, 78359, 78559, 78033, 78097, 78509, 78098, 78061, 78566, 78628, 77864, 78120, 77771, 78042, 77824, 77867, 78390, 78183, 78259, 77651, 77896, 78148, 78696, 78018, 78343, 77902, 77819, 78087, 78425, 78534, 77999, 78316, 78301, 78008, 78017, 78322, 78332, 78681, 78437, 78176, 78215, 77954, 78154, 77888, 78135, 78178, 78351, 78084, 77840, 78015, 78482, 77976, 78297, 78138, 78256, 77683, 78050, 78393, 78080, 78025, 77801, 78330, 77824, 78284, 78248, 78273, 78262, 77745, 78228, 78276, 78143, 78413, 78286, 77853, 78389, 78051, 78194, 77812, 77921, 78440, 78423, 78578, 78444, 78275, 78358]
---
i = 129
[78067, 78312, 78444, 78050, 78359, 78227, 78388, 77835, 78623, 78321, 77795, 78457, 78324, 78124, 78010, 78432, 78115, 77771, 77962, 78116, 78001, 78544, 77841, 78298, 78215, 78048, 77637, 77788, 77847, 78544, 77976, 77848, 77997, 78385, 78102, 78145, 77980, 78098, 78156, 77992, 78314, 78252, 77965, 78046, 78109, 78495, 78214, 77679, 78029, 78569, 77829, 78214, 78004, 77871, 78426, 78502, 78042, 77446, 77557, 78306, 78036, 77826, 78318, 77767, 78029, 78496, 78355, 77864, 78797, 77564, 78089, 78421, 78434, 78127, 77941, 77994, 77865, 78359, 78470, 77869, 78334, 78125, 78281, 78351, 77914, 78477, 78180, 77874, 78288, 77765, 78138, 78075, 77897, 78146, 78149, 78271, 78029, 77748, 78137, 77906, 77937, 77777, 78261, 78455, 77799, 78459, 78366, 77845, 78294, 78107, 78095, 78496, 78224, 78249, 77776, 78207, 77839, 78344, 78203, 78368, 78303, 78350, 78093, 78432, 77881, 78277, 77922, 38794, 39098]
---

rigorTest.d

import std.random, std.stdio, std.traits, std.conv, std.range;

void main() {
    test1!testableUniform();
    test1!badUniform();
    test2!testableUniform();
    test2!badUniform();
}

void test1(alias Fn)() {
    Random rng = rndGen;

    auto uintQuarter = ((uint.max)/4);
    auto upper = 3 * uintQuarter;

    auto bottomThird = upper / 3;
    auto upperThird = upper - bottomThird;

    size_t[3] thirdCounts = [0,0,0];

    foreach(_; iota(100_000)) {
        auto roll = Fn(0, upper, rng);
        if(roll < bottomThird) {
            thirdCounts[0]++;
        } else if(roll < upperThird) {
            thirdCounts[1]++;
        } else {
            thirdCounts[2]++;
        }
    }

    writeln("Results for ", __traits(identifier, Fn), " = ", thirdCounts[]);
}

void test2(alias Fn)() {
    auto limitedUniform(T1,T2,RandomGen)(T1 a, T2 b, ref RandomGen rng) {
        return Fn!ubyte(a,b,rng);
    }

    Random rng = rndGen;

    writeln("Test2 on ", __traits(identifier, Fn));
    writeln("---");

    foreach(i; iota(127, 130)) {
        writeln("i = ", i);

        size_t[] counts = new size_t[](i);
        foreach(_; iota(10_000_000)) {
            auto roll = limitedUniform(cast(ubyte) 0, cast(ubyte) i, rng);
            counts[roll]++;
        }
        writeln(counts);
        writeln("---");
    }
}

alias NormalUT = typeof(unsigned(2 - 1));
auto testableUniform(UpperType = NormalUT, T1, T2, RandomGen)
(T1 a, T2 b, ref RandomGen rng)
{
    alias ResultType = Unqual!(CommonType!(T1, T2));
    ResultType lower = a;

    UpperType upperDist = cast(UpperType)(b - lower);
    
    assert(upperDist != 0);
    if (upperDist == 1) return lower;

    static assert(UpperType.min == 0);

    UpperType offset, rnum, bucketFront;
    do
    {
        rnum = uniform!UpperType(rng);
        offset = cast(UpperType)(rnum % upperDist);
        bucketFront = cast(UpperType)(rnum - offset);
    } // while we're in an unfair bucket...
    while (bucketFront > (UpperType.max - (upperDist - 1)));

    return cast(ResultType)(lower + offset);
}


auto badUniform(UpperType = NormalUT, T1, T2, RandomGen)
(T1 a, T2 b, ref RandomGen rng)
{
    alias ResultType = Unqual!(CommonType!(T1, T2));
    ResultType lower = a;

    UpperType upperDist = cast(UpperType)(b - lower);
    
    assert(upperDist != 0);
    if (upperDist == 1) return lower;

    static assert(UpperType.min == 0);

    UpperType offset, rnum, bucketFront;

    // FAIL TO REROLL!
    rnum = uniform!UpperType(rng);
    offset = cast(UpperType)(rnum % upperDist);
    bucketFront = cast(UpperType)(rnum - offset);

    return cast(ResultType)(lower + offset);
}