Support large generators in generate_canonical
libstdc++'s generate_canonical now supports generators producing more than 128 bits of entropy.
The libstdc++ generate_canonical function now supports generators that produce more than 128 bits of entropy. Previously, generators requiring computations that could overflow 128 bits were unsupported. This change implements a method to handle such cases by checking for potential overflows and rejecting values early, ensuring correctness even for generators with very large outputs.
In Details
Extends generate_canonical_any to handle generators where bit_width(R^k) exceeds 128. It introduces a new computation path that leverages the fact that large values of sum are rejected if (sum / x * 2^d) > 1. The implementation computes the sum of lower terms iteratively and then multiplies by the highest term, carefully checking for overflows against a 128-bit limit.
- libstdc++
- The C++ standard library implementation used by GCC. It provides the core language features and standard library components for C++ programs.
- generate_canonical
- A function likely related to random number generation or canonical representation, typically found in a probability or statistics context. The 'any' variant suggests it handles various generator types.
- entropy
- In the context of random number generation, entropy refers to the unpredictability or randomness of the output. Higher entropy means a less predictable sequence.
- generator
- A component or function that produces a sequence of values, often used for random number generation.