bpo-43040: Fix randrange() is very slow if the range is a power of 2. by dbaarda · Pull Request #24354 · python/cpython

@dbaarda

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.

vstinner

@dbaarda

@dbaarda

…thout_getrandbits().

These will return 0 for n <=1.

mdickinson

mdickinson

mdickinson

mdickinson

@dbaarda

…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.

@dbaarda

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().

@blurb-it