Random.randbelow speed up by using larger variates

[isaacl]

Feature or enhancement

Proposal:

_randbelow is implemented as a loop polling r = self.getrandbits(k) # 0 <= r < 2**k until r < n. For small n, such as when used in shuffle, this can force re-rolls.

But if poll with a larger random, we minimize re-rolls. The cPython intrinsic can return of 32 random bits at a time for the same cost as a smaller number of bits. So essentially, if we assume we can get multiples of 32 random bits for free:

bits = (n.bit_length() + 31) & ~31  # round up to next multiple of 32
max_rand = 1 << bits  # max value from getrandbits
limit = max_rand - (max_rand % n)   # reject anything above limit
while (r := self.getrandbits(bits)) >= limit:
  pass
return r % n

See also OpenJDK

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

[mdickinson]

Do you have timings to back up the "speed up" claim in the issue title? I'm skeptical: unless sampling is particularly expensive (e.g., because a cryptographically secure PRNG is being used in place of Mersenne Twister), the extra per-call work involved in computing limit and in the final % n reduction could easily negate any gain from the reduced number of samples.

The proposed change would break reproducibility of anything depending on _randbelow. While such reproducibility isn't guaranteed (see https://docs.python.org/3/library/random.html#notes-on-reproducibility), reproducibility breakage isn't something to take lightly, either.