[Bug libstdc++/119739] [C++26] Implement P0952R2, A new specification for std::generate_canonical

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=119739

--- Comment #6 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Tomasz Kaminski <tkaminsk@gcc.gnu.org>:

https://gcc.gnu.org/g:d90aac09963b235b34d08cc7485eea0d90b32ae8

commit r17-2971-gd90aac09963b235b34d08cc7485eea0d90b32ae8
Author: Tomasz KamiÅski <tkaminsk@redhat.com>
Date:   Tue Jul 21 13:53:07 2026 +0200

    libstdc++: Support any generator (up to 64bit) in generate_canonical
[PR119739]

    This patch splits implementation of generate_canonical_any, into three
    different path depending on bits generated (R), required bits of entropy
    (b), and value k such that R^k > 2^d > R^(k-1):
    * log2(R) >= d: single call of generator is sufficient (k = 1),
      and computation can be performed in the generator value type (_UIntR);
    * bit_width(R^k) <= 128: computation can be performed using type
      __detail::_Select_uint_least_t; previous implementation is reused;
    * bit_width(R^k) > 128: the computations required may overflow 128 bit;
      such generators were previously unsupported, as illustrated by
      r17-507-g5d17eec7d83445.

    This patch implements the support for the last branch, by observing
    that while it is possible for following computation to overflow 128bit
    integer:
      sum_[0, k) urng() * R^i
    The values of sum, such that (sum / x * 2^d) > 1, are rejected, thus
    any value (sum / x) > 2^d can be rejected. As 2^d is guaranteed to fit
    in 128 integer, we can use above to reject the value, before overflow
    will occur.

    Firstly, we know that for l = k-1, the value R^l < 2^d, and
    sum_[0, l) urng() * R^i <= R^l (because urng() is always < R),
    always fit in 128bit integer. We compute that value (__lsum) using
    normal loop.

    This leaves us with final iteration of multiplying __kth * R^l, where
    __kth is result of invocation of urng. In that case we compute the
    bitwidth (__abits) of value that can be multiplied by _R^l without
    overflow 128bit integer. The __kth * R^l is performed by multiplying
    the loop of __abits of __kth in loop where:
    * __sumx (initially __lsum / __x) is the current value of sum / x,
    * __remx (initially 2^d - __sumx) is the value that we can still,
      add before overflowing (shifted with each iteration)
    * __modx (initially __lsum % __x) are collected reminders.
    In each iteration the lowest __kth bits are multiplied with _Rl (__val),
    scaled (__valx) and checked against __remx. When fits the __sumx, __modx
    and __remx are updated, and both values of __remx and __kth are shifted
    right by __abits.

    If the multiplication finished without overflow (__kth is zero), we handle
    the collected remainders (__modx), and compute the __ret value. The values
    greater or equal 1 (e.g. due floating point approximation), are still
    rejected.

    Similar approach is applied when computing x = R^k / 2^d.
    Again while R^k will overflow 128 bits, we know that x < R (so fits
    in 64bits), as R^l < 2^d < R^k, then x < R. We again compute
    R * R^l / 2^d, by splitting the value of R into __abits chunks (_pR).
    For result of chunks multipliations (_pRk), the bits (__xp) remaining
    after division by __shift (starts from __d and reduces by __abits),
    are collected into cumulative value of __x. While the lower bits
    are preserved for later iteration (__pRk).

            PR libstdc++/119739

    libstdc++-v3/ChangeLog:

            * include/bits/random.tcc (__generate_canonical_any):
            Rewrite to support generator with different ranges.
            *
testsuite/26_numerics/random/uniform_real_distribution/operators/gencanon.cc:
            Add test for previously unsupported generator.
            *
testsuite/26_numerics/random/uniform_real_distribution/operators/gencanon_eng.cc:
            Add test for previously unsupported-generator ranges.
            *
testsuite/26_numerics/random/uniform_real_distribution/operators/gencanon_eng_neg.cc:
            Moved (now-supported) generator test to gencanon_eng.cc, and
removed
            the file.

    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
    Signed-off-by: Tomasz KamiÅski <tkaminsk@redhat.com>