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/tools/qlist.h | |
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/tools/qlist.h')
0 files changed, 0 insertions, 0 deletions