New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
_randbelow_with_getrandbits function inefficient with powers of two #81181
Comments
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 computational overhead in addition to wasting k+2 bits on average. This is due to taking n.bit_size() instead of (n-1).bit_size() for the size of the random candidates. Using n instead of n-1 is apparently deliberate in order to save the case where n = 1, but this could be avoided by directly returning 0 if n == 1. |
The other solution is to make |
Some quick notes:
When I get a chance, I'll take a closer look at Mark's suggestion. |
I believe the thrust of Mark's suggestion was that it would allow using That said, given that In any case, I'd leave _randbelow_with_getrandbits alone. Conauming "extra" bits is generally a red herring, since the underlying 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. |
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:
That makes sense to me as well. I'll mark this as closed. There's one other bright side. If someone really cares about the speed of the power-of-two case, they can already call Mathis, thank you for taking the time to look at this code. |
Related: Those are very different from The So if So to me, it makes no sense at all that |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: