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 --- src/corelib/global/qrandom.h | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) (limited to 'src') 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::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::digits; + x >>= std::numeric_limits::digits - std::numeric_limits::digits; + return double(x) / double(limit); } static qreal bounded(qreal sup) -- cgit v1.2.3