[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Mark Dickinson added the comment: Related: `randrange(0)` raises an exception `choice([])` raises an exception Those are very different from `getrandbits(0)`: in both cases there's no reasonable value that can be returned: for the first case, there's no integer `x` with `0 <= x < 0`;

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Raymond Hettinger added the comment: > it's a bit surprising all on its own that `getrandbits(0)` > raises an exception. Given that there would be no randomness in the result, it makes sense to me that getrandbits(0) is documented to raise an exception. Related: `randrange(0)` raises an

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Tim Peters added the comment: I believe the thrust of Mark's suggestion was that it would allow using `k = (n-1).bit_length()` even when n == 1, without special-casing n == 1. But you'd still be adding a new "subtract 1" operation, and would still change results in some cases. That said, g

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Raymond Hettinger added the comment: Some quick notes: * In issue 33144, we achieved a significant speed-up for _randbelow_with_getrandbits() by removing a single test. The code for that method is thin and almost any additional logic will slow it down. * The attached PR (now closed) causes

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Mark Dickinson added the comment: > this could be avoided by directly returning 0 if n == 1 The other solution is to make `getrandbits(0)` valid, always returning `0`. -- ___ Python tracker

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Change by Mathis Hammel : -- keywords: +patch pull_requests: +13398 stage: -> patch review ___ Python tracker ___ ___ Python-bugs-l

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

Change by Raymond Hettinger : -- assignee: -> rhettinger priority: normal -> low versions: -Python 2.7, Python 3.5, Python 3.6, Python 3.7, Python 3.9 ___ Python tracker ___

[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

New submission from Mathis Hammel : In case _randbelow_with_getrandbits is called with a power of two as its argument (say 2^k), the function will consume k+1 random bits instead of k. Instead of never being rejected, the sampled number will be rejected on average once per call, causing a com