random._randbelow soft fix with performance gain #132320
Description
Bug report
Bug description:
Simplest example.
def _randbelow_with_getrandbits(self, n):
"Return a random int in the range [0,n). Defined for n > 0."
k = n.bit_length()
r = self.getrandbits(k) # 0 <= r < 2**k
print(r)
while r >= n:
r = self.getrandbits(k)
print(r)
print('accepted')
return rCalling random._inst._randbelow(2) returns the following:
2
1
accepted
2
3
3
0
accepted
2
2
3
2
2
0
accepted
Changing the line to:
k = (n - 1).bit_length()
For most of cases it will not make a difference, but I suspect it is not so rare that people call randint/randrange with numbers 2**n and for all of these, this will keep failing 50% of the time.
CPython versions tested on:
3.14
Operating systems tested on:
macOS