https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80977
Bug ID: 80977
Summary: uniform_int_distribution downscaling throws away
perfectly good entropy
Product: gcc
Version: 7.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: gccbugs at jbapple dot com
Target Milestone: ---
https://github.com/gcc-mirror/gcc/blob/gcc-7_1_0-release/libstdc%2B%2B-v3/include/bits/uniform_int_dist.h#L218
aka
https://github.com/gcc-mirror/gcc/blob/b57fb75946b6e10a26dcc200b1975133e971212d/libstdc%2B%2B-v3/include/bits/uniform_int_dist.h#L218
uses incorrect arithmetic to downscale from a range of a URNG to a smaller
range. It calculates the size of the two ranges, maps the larger range to the
smaller range, but disregards (using rejection sampling) the overflow values.
As an example, if the URNG generates values from 81 to 87 and the
uniform_int_distribution has min of 10 and max of 11, then it uses the range
81-86 and discards any 87 that is generated. So, since
floor((87-81+1)/(11-10+1)) is 3, if 84 is generated, then the return value is
10 + (84-81)/3 = 11.
I think there are at least two errors based on one flawed assumption: that the
size of a range [x,y] is y-x, when it is actually y-x+1. Here is a
demonstration:
#include <random>
struct Three {
using result_type = int;
static result_type min() { return 80; }
static result_type max() { return 83; }
result_type operator()() { return 83; }
};
int main() {
std::uniform_int_distribution<int> u(70,71);
Three three;
return u(three);
}
Three is a lousy URNG :-). But this program doesn't return a biased value, it
instead never returns. It should be easy to map a URN with a range of [80,83]
to a uniform_int_distribution of [70,71] by x |-> 70 + (x-80)/2. Instead, 80
maps to 70, 81 to 71, and 82 and 83 to non-termination.
The declarations of __urngrange and __urange should include adding one, and
__uerange can be removed and it's uses replaced with __urange.
