QRandomGenerator: improve floating-point random generation

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 <lars.knoll@qt.io>
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>

1 files changed, 10 insertions, 2 deletions

diff --git a/src/corelib/global/qrandom.h b/src/corelib/global/qrandom.h
index 7f96cd6749..2259f2657a 100644
--- a/src/corelib/global/qrandom.h
+++ b/src/corelib/global/qrandom.h
@@ -62,8 +62,16 @@ public:
     static Q_CORE_EXPORT quint64 generate64();
     static double generateDouble()
     {
-        // use get64() to get enough bits
-        return double(generate64()) / ((std::numeric_limits<quint64>::max)() + double(1.0));
+        // IEEE 754 double precision has:
+        //   1 bit      sign
+        //  10 bits     exponent
+        //  53 bits     mantissa
+        // In order for our result to be normalized in the range [0, 1), we
+        // need exactly 53 bits of random data. Use generate64() to get enough.
+        quint64 x = generate64();
+        quint64 limit = Q_UINT64_C(1) << std::numeric_limits<double>::digits;
+        x >>= std::numeric_limits<quint64>::digits - std::numeric_limits<double>::digits;
+        return double(x) / double(limit);
     }
 
     static qreal bounded(qreal sup)