[llvm-bugs] [Bug 44847] std::binomial_distribution<int> hangs

via llvm-bugs llvm-bugs at lists.llvm.org
Tue Mar 17 12:59:39 PDT 2020


https://bugs.llvm.org/show_bug.cgi?id=44847

Louis Dionne <ldionne at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
                 CC|                            |ldionne at apple.com
             Status|NEW                         |RESOLVED

--- Comment #1 from Louis Dionne <ldionne at apple.com> ---
Thanks for the report. Should be fixed by:

commit 51b78a3e06d4ef7da8404a1c51c3ede894a42cb6
Author: Atmn Patel <a335pate at uwaterloo.ca>
Date:   Tue Mar 17 15:52:36 2020 -0400

    [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

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20200317/2e721833/attachment.html>


More information about the llvm-bugs mailing list