libstdc++: Lemire's algorithm adapted for non--bit ranges.
Random number generation in libstdc++ uses Lemire's algorithm more broadly for power-of-two ranges, improving portability.
GCC’s libstdc++ now more broadly applies Lemire’s algorithm for generating random numbers within power-of-two ranges. Previously, this efficient algorithm was primarily used for 32-bit (__UINT32_TYPE__) and 64-bit (__UINT64_TYPE__) unsigned integers. This update allows it to work with targets that lack these specific types, by masking the result of integer conversions to the required bit width. The core logic for Lemire’s algorithm and the necessary type definitions are now consolidated in uniform_int_dist.h for better organization and portability.
In Details
This commit extends the use of Lemire's algorithm for uniform random number generation in libstdc++. Previously, the implementation in bits/random.h relied on __UINT32_TYPE__ and __UINT64_TYPE__. This update makes the algorithm work for any target where the range size is a power of two (2^_Bits) by masking the conversion of __product to _Up to the lowest _Bits. The type _Up and _Wp are now derived from _Select_uint_least_t based on _Bits and 2 * _Bits. The primary template and specializations of _Select_uint_least_t are moved to include/bits/uniform_int_dist.h to…
- Lemire's algorithm
- An efficient algorithm for generating uniform random numbers within a range, particularly effective for ranges that are powers of two.
- uniform random number distribution
- A type of random number generator that produces values with an equal probability of occurring within a specified range.
- __UINT32_TYPE__
- A preprocessor macro that expands to the unsigned integer type with a width of at least 32 bits.
- __UINT64_TYPE__
- A preprocessor macro that expands to the unsigned integer type with a width of at least 64 bits.