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 <[email protected]>: https://gcc.gnu.org/g:d90aac09963b235b34d08cc7485eea0d90b32ae8 commit r17-2971-gd90aac09963b235b34d08cc7485eea0d90b32ae8 Author: Tomasz KamiÅski <[email protected]> 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 <[email protected]> Signed-off-by: Tomasz KamiÅski <[email protected]>
