[issue37000] _randbelow_with_getrandbits function inefficient with powers of two

[Tim Peters]

Tim Peters <tim at python.org> 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, given that `(0).bit_length() == 0`, it's a bit surprising all on its own that `getrandbits(0)` raises an exception.

In any case, I'd leave _randbelow_with_getrandbits alone.  Conauming "extra" bits is generally a red herring, since the underlying `getrandbits()` consumes 32 bits at a time from the Twister.  That is, we're _typically_ "wasting" more than a dozen bits regardless already (e.g., getrandbits(2), getrandbits(17), and getrandbits(29) all consume 32 bits).

It's unfortunate that _randbelow_with_getrandbits(power_of_2) may invoke getrandbits() more than once.  But there's also a bright side:  because there's always the possibility that _randbelow_with_getrandbits() may invoke getrandbits() more than once, we can't guess how many times getrandbits() _was_ called.  So, in turn, we can't know how much of the Twister's state space was consumed.  Which, in turn, makes it much harder to deduce the Twister's' internal state from the visible outputs (but this can be done with certainty from a long enough string of, say, random.choice([0, 1]) outputs if we knew getrandbits was called exactly once for each, despite that we're only seeing 1 bit of each 32-bit Twister output).

That last point shouldn't drive anything, but it is kinda pleasant that people inappropriately using the Twister in contexts where keeping secrets is important are partially protected by under-the-covers accept/reject methods.

----------
nosy: +tim.peters

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37000>
_______________________________________