bpo-43040: Fix randrange() is very slow if the range is a power of 2. by dbaarda · Pull Request #24354 · python/cpython
Make _randbelow_with_getrandbits() get the number of bits needed for (n-1), not n, since we only return values <=n. When n is a power of 2, this reduces the number of bits needed by 1, and also means getrandbits() is not called repeatedly (on average 2x as many times as needed) until the returned value is <n. Make _randbelow_with_getrandbits() and _randbelow_without_getrandbits() short-circuit and return 0 if n <= 1, not just == 0. This also protects against invalid evaluation in the above fix to _randbelow_with_getrandbits() calling getrandbits(0) when n == 1.
…below_without_getrandbits()." This reverts commit 5215ba3. The docstring already explains the behaviour when n==1 with the normal behaviour of returning [0,n). The case when n=0 is special and needs specific explanation.
The case of n==1 is correctly handled by the rest of the code, and this makes it a tiny bit faster for the common case (n > 1). This also makes how this case is handled in _randbelow_without_getrandbits() consistent with _randbelow_with_getrandbits().
This test uses gen.choice() to randomly select values from a sequence, which is affected by the repeatability change from optimizing _randbelow_with_getrandbits().
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters