<html>
<head>
<base href="https://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - uniform_real_distribution isn't uniform."
href="https://llvm.org/bugs/show_bug.cgi?id=23168">23168</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>uniform_real_distribution isn't uniform.
</td>
</tr>
<tr>
<th>Product</th>
<td>libc++
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>All Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>art@blahonga.org
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu, mclow.lists@gmail.com
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Looking at the implementation of uniform_real_distribution it's quite obvious
that it isn't respecting the pigeonhole principle. And since lots of other
distributions are built on top of uniform_real_distribution, all those other
distributions are broken too.
Here's a very simple test:
$ cat urd.cxx
#include <random>
#include <iostream>
#include <stdio.h>
#include <assert.h>
int
main()
{
std::default_random_engine gen;
double from = 0x1p52, to = from + 2;
std::uniform_real_distribution<double> dis(from, to);
long long bucket[3] = { 0 };
int i;
for (i = 0; i < 1000000; i++) {
double r = dis(gen);
unsigned int b = (int)(r - from);
if (b >= 3) {
printf("foo: %d %f\n", b, r);
}
assert(b < 3);
bucket[b]++;
}
for (i = 0; i < 3; i++) {
printf("%lld\n", bucket[i]);
}
return 0;
}
$ c++ -v
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.1.0
Thread model: posix
$ c++ -std=c++11 -o foo urd.cxx && ./foo
249701
500046
250253
I looked through the code available on the svn trunk on the web and it hasn't
changed enough to fix this.
The reason 0x1p52 is the start of the range is because at [2^52,2^53) doubles
have exactly integer precision which allows the generator only three possible
output values. Any other range could be chosen and display the same problem as
long as we constrict the generator to few (non 2^n) outputs. Three possible
outputs will display the greatest bias in the output.
GCC libstdc++ is broken too in the exact same way.
FYI. A while ago I started an attempt to make a decent solution to a small part
of this problem because it's harder than it looks:
<a href="https://github.com/art4711/random-double/blob/master/rd.c">https://github.com/art4711/random-double/blob/master/rd.c</a></pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>