From c90d9f95d27cf12747446ce8f7ee1cefe1f0f818 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Thu, 12 Oct 2017 13:40:18 -0700 Subject: QRandomGenerator: improve floating-point random generation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The previous version was good, just not optimal. Because the input was an unsigned 64-bit number, compilers needed to generate extra code to deal with HW instructions that only convert 64-bit signed input. And that was useless because a double uniformly distributed from 0 to 1 can only have 53 bits of randomness. The previous implementation did exactly what the Microsoft libstdc++ and libc++ implementations do. In my opinion, those implementations have an imperfect distribution, which is corrected in this commit. In those, all random input bigger than 0x20000000000000 has a different frequency compared to input below that mark. For example, both 0x20000000000000 and 0x20000000000001 produce the same result (4.8828125e-4). What's more, for the libc++ and MSVC implementations, input between 0xfffffffffffff001 and 0xffffffffffffffff results in 1.0 (probability 1 in 2⁵³), even though the Standard is very clear that the result should be strictly less than 1. GCC 7's libstdc++ doesn't have this issue, whereas the versions before would enter an infinite loop. Change-Id: Ib17dde1a1dbb49a7bba8fffd14eced3c375dd2ec Reviewed-by: Lars Knoll Reviewed-by: Edward Welbourne --- .../qrandomgenerator/tst_qrandomgenerator.cpp | 50 +++++++++++++++++++++- 1 file changed, 49 insertions(+), 1 deletion(-) (limited to 'tests') diff --git a/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp b/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp index 2195bf8ec8..d1c0c8e965 100644 --- a/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp +++ b/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp @@ -97,6 +97,8 @@ private slots: void generateReal_data() { generate32_data(); } void generateReal(); + void qualityReal_data() { generate32_data(); } + void qualityReal(); void seedStdRandomEngines(); void stdUniformIntDistribution_data(); @@ -445,7 +447,7 @@ void tst_QRandomGenerator::generateReal() for (int i = 0; i < 4; ++i) { QVERIFY_3TIMES([] { qreal value = QRandomGenerator::generateDouble(); - return value > 0 && value < 1 && value != RandomValueFP; + return value >= 0 && value < 1 && value != RandomValueFP; }()); } @@ -454,6 +456,52 @@ void tst_QRandomGenerator::generateReal() QVERIFY_3TIMES(QRandomGenerator::generateDouble() != QRandomGenerator::generateDouble()); } +void tst_QRandomGenerator::qualityReal() +{ + QFETCH(uint, control); + setRNGControl(control); + + enum { + SampleSize = 160, + + // Expected value: sample size times proportion of the range: + PerfectOctile = SampleSize / 8, + PerfectHalf = SampleSize / 2, + + // Variance is (1 - proportion of range) * expected; sqrt() for standard deviations. + // Should usually be within twice that and almost never outside four times: + RangeHalf = 25, // floor(4 * sqrt((1 - 0.5) * PerfectHalf)) + RangeOctile = 16 // floor(4 * sqrt((1 - 0.125) * PerfectOctile)) + }; + + double data[SampleSize]; + std::generate(std::begin(data), std::end(data), &QRandomGenerator::generateDouble); + + int aboveHalf = 0; + int belowOneEighth = 0; + int aboveSevenEighths = 0; + for (double x : data) { + aboveHalf += x >= 0.5; + belowOneEighth += x < 0.125; + aboveSevenEighths += x >= 0.875; + + // these are strict requirements + QVERIFY(x >= 0); + QVERIFY(x < 1); + } + + qInfo("Halfway distribution: %.1f - %.1f", 100. * aboveHalf / SampleSize, 100 - 100. * aboveHalf / SampleSize); + qInfo("%.1f below 1/8 (expected 12.5%% ideally)", 100. * belowOneEighth / SampleSize); + qInfo("%.1f above 7/8 (expected 12.5%% ideally)", 100. * aboveSevenEighths / SampleSize); + + QVERIFY(aboveHalf < PerfectHalf + RangeHalf); + QVERIFY(aboveHalf > PerfectHalf - RangeHalf); + QVERIFY(aboveSevenEighths < PerfectOctile + RangeOctile); + QVERIFY(aboveSevenEighths > PerfectOctile - RangeOctile); + QVERIFY(belowOneEighth < PerfectOctile + RangeOctile); + QVERIFY(belowOneEighth > PerfectOctile - RangeOctile); +} + template void seedStdRandomEngine() { QRandomGenerator rd; -- cgit v1.2.3