New submission from Mathis Hammel <mathis.ham...@gmail.com>:
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. ---------- components: Library (Lib) messages: 343094 nosy: Mathis Hammel, mark.dickinson, rhettinger priority: normal severity: normal status: open title: _randbelow_with_getrandbits function inefficient with powers of two type: performance versions: Python 2.7, Python 3.5, Python 3.6, Python 3.7, Python 3.8, Python 3.9 _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue37000> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
