[libc++] Bugfix to std::binomial_distribution<int>
authorAtmn Patel <a335pate@uwaterloo.ca>
Tue, 17 Mar 2020 19:52:36 +0000 (15:52 -0400)
committerLouis Dionne <ldionne@apple.com>
Tue, 17 Mar 2020 19:56:16 +0000 (15:56 -0400)
commit51b78a3e06d4ef7da8404a1c51c3ede894a42cb6
treeab6a0d081ef7af549932da914e4b8db1b9d8c96c
parent526c51e6fdc834b703e14ca851a8c95c7f1c9b2f
[libc++] Bugfix to std::binomial_distribution<int>

The current implementation of binomial_distribution is not guaranteed to
converge for certain extreme configurations of the engine and distribution.
This is due to a mistake in the implementation of the algorithm from the
given reference paper. The algorithm in the paper is guaranteed to
terminate but has redundant statements. The current implementation
simplified away the redundancy into a while loop, but it excludes the
return condition of the case where a good sample cannot be returned for
the particular sample being used from the uniform distribution, which is
what causes the infinite loop. This change guarantees termination by
recognizing that a good sample cannot be returned and returning 0 after
breaking the loop. This is also in contrast to the paper because the
return value as specified in the paper violates basic checks in at least
a subset of the extreme cases where the current implementation fails to
terminate. This default return value of 0 is satisfactory for the
extreme case known so far.

Since this is only meant to affect extreme cases where the algorithm
does not terminate anyways, the behavior is expected to remain exactly
the same for all non-extreme cases that have been terminating so far.

Fixes https://llvm.org/PR44847

Differential Revision: https://reviews.llvm.org/D74997
libcxx/include/random
libcxx/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.bin/eval.pass.cpp