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 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
<https://bugs.python.org/issue37000>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
