diff options
author | Thiago Macieira <thiago.macieira@intel.com> | 2020-09-16 17:01:03 -0700 |
---|---|---|
committer | Thiago Macieira <thiago.macieira@intel.com> | 2020-10-20 22:45:06 -0700 |
commit | 21d39168170c6833512c4a5f53985272741bd7e7 (patch) | |
tree | c17c8c016a94a48e7ae45a99805b0c728c96e64a /src/corelib/global | |
parent | 74bf2cd21d33f3b96df1ceb9219773c2c464840a (diff) |
QRandomGenerator: add 64-bit bounded() versions
Unlike the 32-bit version, we can't go to a bigger integer type to do
the multiplication with. So instead accept looping. Both libstdc++ and
libc++ implement std::uniform_int_distribution this way anyway, but in a
far more complex way.
There is no looping if the "highest" is a power of two. The worst-case
scenario is when "highest" is one past a power of two (like 65). In that
case, we'll loop until the number is in range. Since all bits have equal
probability of being zero or one, there's a 50-50 chance that the most
significant useful bit will be set[*], in which case we'll need to loop
and we again get the same probability. So on average, we only need two
iterations to get an acceptable result.
[*] There's also a possibility that the other bits are such that the
number is still in range. For 65, we'd need the other 5 bits to be zero
(64 is a valid result), but the probability of that is only 1/2^5 =
3.125%. The bigger "highest" is, the closer we get to zero, so
approximate by saying that never happens and instead calculate that the
most significant useful bit is the controlling one.
[ChangeLog][QtCore][QRandomGenerator] Added 64-bit versions of the
bounded() functions. They are useful in conjunction with Qt 6's 64-bit
container sizes, so code that used to call bounded(list.size()) in Qt 5
will continue to compile and work in Qt 6.
Fixes: QTBUG-86318
Change-Id: I3eb349b832c14610895efffd16356927fe78fd02
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Diffstat (limited to 'src/corelib/global')
-rw-r--r-- | src/corelib/global/qrandom.cpp | 96 | ||||
-rw-r--r-- | src/corelib/global/qrandom.h | 58 |
2 files changed, 152 insertions, 2 deletions
diff --git a/src/corelib/global/qrandom.cpp b/src/corelib/global/qrandom.cpp index 9a6e781b99..d12d8cd287 100644 --- a/src/corelib/global/qrandom.cpp +++ b/src/corelib/global/qrandom.cpp @@ -876,7 +876,8 @@ inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::sel \a highest (exclusive). The same result may also be obtained by using \l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{\c std::uniform_int_distribution} with parameters 0 and \c{highest - 1}. That class can also be used to obtain - quantities larger than 32 bits. + quantities larger than 32 bits; for 64 bits, the 64-bit bounded() overload + can be used too. For example, to obtain a value between 0 and 255 (inclusive), one would write: @@ -905,6 +906,45 @@ inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::sel */ /*! + \fn quint64 QRandomGenerator::bounded(quint64 highest) + \overload + + Generates one random 64-bit quantity in the range between 0 (inclusive) and + \a highest (exclusive). The same result may also be obtained by using + \l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{\c std::uniform_int_distribution<quint64>} + with parameters 0 and \c{highest - 1}. + + Note that this function cannot be used to obtain values in the full 64-bit + range of \c{quint64}. Instead, use generate64(). + + \note This function is implemented as a loop, which depends on the random + value obtained. On the long run, on average it should loop just under 2 + times, but if the random generator is defective, this function may take + considerably longer to execute. + + \sa generate(), generate64(), generateDouble() + */ + +/*! + \fn qint64 QRandomGenerator::bounded(qint64 highest) + \overload + + Generates one random 64-bit quantity in the range between 0 (inclusive) and + \a highest (exclusive). \a highest must be positive. + + Note that this function cannot be used to obtain values in the full 64-bit + range of \c{qint64}. Instead, use generate64() and cast to qint64 or instead + use the unsigned version of this function. + + \note This function is implemented as a loop, which depends on the random + value obtained. On the long run, on average it should loop just under 2 + times, but if the random generator is defective, this function may take + considerably longer to execute. + + \sa generate(), generate64(), generateDouble() + */ + +/*! \fn quint32 QRandomGenerator::bounded(quint32 lowest, quint32 highest) \overload @@ -943,6 +983,60 @@ inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::sel */ /*! + \fn quint64 QRandomGenerator::bounded(quint64 lowest, quint64 highest) + \overload + + Generates one random 64-bit quantity in the range between \a lowest + (inclusive) and \a highest (exclusive). The \a highest parameter must be + greater than \a lowest. + + The same result may also be obtained by using + \l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{\c std::uniform_int_distribution<quint64>} + with parameters \a lowest and \c{\a highest - 1}. + + Note that this function cannot be used to obtain values in the full 64-bit + range of \c{quint64}. Instead, use generate64(). + + \note This function is implemented as a loop, which depends on the random + value obtained. On the long run, on average it should loop just under 2 + times, but if the random generator is defective, this function may take + considerably longer to execute. + + \sa generate(), generate64(), generateDouble() + */ + +/*! + \fn qint64 QRandomGenerator::bounded(qint64 lowest, qint64 highest) + \overload + + Generates one random 64-bit quantity in the range between \a lowest + (inclusive) and \a highest (exclusive), both of which may be negative, but + \a highest must be greater than \a lowest. + + Note that this function cannot be used to obtain values in the full 64-bit + range of \c{qint64}. Instead, use generate64() and cast to qint64. + + \note This function is implemented as a loop, which depends on the random + value obtained. On the long run, on average it should loop just under 2 + times, but if the random generator is defective, this function may take + considerably longer to execute. + + \sa generate(), generate64(), generateDouble() + */ + +/*! + \fn qint64 QRandomGenerator::bounded(int lowest, qint64 highest) + \fn qint64 QRandomGenerator::bounded(qint64 lowest, int highest) + \fn quint64 QRandomGenerator::bounded(unsigned lowest, quint64 highest) + \fn quint64 QRandomGenerator::bounded(quint64 lowest, unsigned highest) + \overload + + This function exists to help with overload resolution when the types of the + parameters don't exactly match. They will promote the smaller type to the + type of the larger one and call the correct overload. + */ + +/*! \fn QRandomGenerator *QRandomGenerator::system() \threadsafe diff --git a/src/corelib/global/qrandom.h b/src/corelib/global/qrandom.h index 29cb24d1f5..d6b8bd742e 100644 --- a/src/corelib/global/qrandom.h +++ b/src/corelib/global/qrandom.h @@ -40,7 +40,7 @@ #ifndef QRANDOM_H #define QRANDOM_H -#include <QtCore/qglobal.h> +#include <QtCore/qalgorithms.h> #include <algorithm> // for std::generate #include <random> // for std::mt19937 @@ -135,6 +135,44 @@ public: return bounded(highest - lowest) + lowest; } + quint64 bounded(quint64 highest); + + quint64 bounded(quint64 lowest, quint64 highest) + { + Q_ASSERT(highest > lowest); + return bounded(highest - lowest) + lowest; + } + + qint64 bounded(qint64 highest) + { + Q_ASSERT(highest > 0); + return qint64(bounded(quint64(0), quint64(highest))); + } + + qint64 bounded(qint64 lowest, qint64 highest) + { + return bounded(highest - lowest) + lowest; + } + + // these functions here only to help with ambiguous overloads + qint64 bounded(int lowest, qint64 highest) + { + return bounded(qint64(lowest), qint64(highest)); + } + qint64 bounded(qint64 lowest, int highest) + { + return bounded(qint64(lowest), qint64(highest)); + } + + quint64 bounded(unsigned lowest, quint64 highest) + { + return bounded(quint64(lowest), quint64(highest)); + } + quint64 bounded(quint64 lowest, unsigned highest) + { + return bounded(quint64(lowest), quint64(highest)); + } + template <typename UInt, IfValidUInt<UInt> = true> void fillRange(UInt *buffer, qsizetype count) { @@ -249,6 +287,24 @@ public: #endif // Q_QDOC }; +inline quint64 QRandomGenerator::bounded(quint64 highest) +{ + // Implement an algorithm similar to libc++'s uniform_int_distribution: + // loop around getting a random number, mask off any bits that "highest" + // will never need, then check if it's higher than "highest". The number of + // times the loop will run is unbounded but the probability of terminating + // is better than 1/2 on each iteration. Therefore, the average loop count + // should be less than 2. + + const int width = qCountLeadingZeroBits(highest - 1); + const quint64 mask = (quint64(1) << (std::numeric_limits<quint64>::digits - width)) - 1; + quint64 v; + do { + v = generate64() & mask; + } while (v >= highest); + return v; +} + inline QRandomGenerator *QRandomGenerator::system() { return QRandomGenerator64::system(); |