[New-bugs-announce] [issue37000] _randbelow_with_getrandbits function inefficient with powers of two

[Mathis Hammel]

New submission from Mathis Hammel <mathis.hammel at 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 <report at bugs.python.org>
<https://bugs.python.org/issue37000>
_______________________________________