Visitar URL original
bpo-40282: Allow random.getrandbits(0) by pitrou · Pull Request #19539 · python/cpython · GitHub
Skip to content

bpo-40282: Allow random.getrandbits(0) #19539

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.

Sign up for GitHub

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

Merged
pitrou merged 7 commits into from
Apr 17, 2020
Merged

bpo-40282: Allow random.getrandbits(0) #19539

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
f572b53
bpo-40282: Allow random.getrandbits(0)
pitrou Apr 15, 2020
3153f1a
Update Doc/library/random.rst
pitrou Apr 15, 2020
9cac35f
Ensure _randbelow implementations raise on 0 input.
pitrou Apr 15, 2020
b01be91
s/positive/non-negative/
pitrou Apr 15, 2020
e7c2e99
Revert changes to choice()
pitrou Apr 15, 2020
5e02ef8
Update Lib/test/test_random.py
pitrou Apr 15, 2020
c4673f0
Apply review comments
pitrou Apr 17, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
bpo-40282: Allow random.getrandbits(0)
  • Loading branch information
@pitrou
pitrou committed Apr 17, 2020
commit f572b535baec4f84e1b1407ceb326133642b4bff
3 changes: 3 additions & 0 deletions Doc/library/random.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -111,6 +111,9 @@ Bookkeeping functions
as an optional part of the API. When available, :meth:`getrandbits` enables
:meth:`randrange` to handle arbitrarily large ranges.
Comment thread
vstinner marked this conversation as resolved.
Outdated

.. versionchanged:: 3.9
This method now accepts 0 for *k*.
Comment thread
pitrou marked this conversation as resolved.
Outdated


Functions for integers
----------------------
Expand Down
13 changes: 6 additions & 7 deletions Lib/random.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -295,11 +295,10 @@ def _randbelow_without_getrandbits(self, n, int=int, maxsize=1<<BPF):

def choice(self, seq):
"""Choose a random element from a non-empty sequence."""
try:
i = self._randbelow(len(seq))
except ValueError:
raise IndexError('Cannot choose from an empty sequence') from None
return seq[i]
n = len(seq)
if n == 0:
raise IndexError('Cannot choose from an empty sequence')
return seq[self._randbelow(n)]
Comment thread
pitrou marked this conversation as resolved.
Outdated

def shuffle(self, x, random=None):
"""Shuffle list x in place, and return None.
Expand Down Expand Up @@ -733,8 +732,8 @@ def random(self):

def getrandbits(self, k):
"""getrandbits(k) -> x. Generates an int with k random bits."""
if k <= 0:
raise ValueError('number of bits must be greater than zero')
if k < 0:
raise ValueError('number of bits must be positive')
Comment thread
pitrou marked this conversation as resolved.
Outdated
numbytes = (k + 7) // 8 # bits / 8 and rounded up
x = int.from_bytes(_urandom(numbytes), 'big')
return x >> (numbytes * 8 - k) # trim excess bits
Expand Down
68 changes: 28 additions & 40 deletions Lib/test/test_random.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -263,6 +263,30 @@ def test_gauss(self):
self.assertEqual(x1, x2)
self.assertEqual(y1, y2)

def test_getrandbits(self):
# Verify ranges
for k in range(0, 1000):
self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)
Comment thread
pitrou marked this conversation as resolved.
Outdated

# Verify all bits active
getbits = self.gen.getrandbits
for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
all_bits = 2**span-1
cum = 0
cpl_cum = 0
for i in range(100):
v = getbits(span)
cum |= v
cpl_cum |= all_bits ^ v
self.assertEqual(cum, all_bits)
self.assertEqual(cpl_cum, all_bits)

@pitrou pitrou Apr 15, 2020

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Note I've enhanced this test a bit to check that all bits take both values 0 and 1 accross 100 draws.


# Verify argument checking
self.assertRaises(TypeError, self.gen.getrandbits)
self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
self.assertRaises(ValueError, self.gen.getrandbits, -1)
self.assertRaises(TypeError, self.gen.getrandbits, 10.1)

def test_pickling(self):
for proto in range(pickle.HIGHEST_PROTOCOL + 1):
state = pickle.dumps(self.gen, proto)
Expand Down Expand Up @@ -374,26 +398,6 @@ def test_randrange_errors(self):
raises(0, 42, 0)
raises(0, 42, 3.14159)

def test_genrandbits(self):
# Verify ranges
for k in range(1, 1000):
self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)

# Verify all bits active
getbits = self.gen.getrandbits
for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
cum = 0
for i in range(100):
cum |= getbits(span)
self.assertEqual(cum, 2**span-1)

# Verify argument checking
self.assertRaises(TypeError, self.gen.getrandbits)
self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
self.assertRaises(ValueError, self.gen.getrandbits, 0)
self.assertRaises(ValueError, self.gen.getrandbits, -1)
self.assertRaises(TypeError, self.gen.getrandbits, 10.1)

def test_randbelow_logic(self, _log=log, int=int):
# check bitcount transition points: 2**i and 2**(i+1)-1
# show that: k = int(1.001 + _log(n, 2))
Expand Down Expand Up @@ -613,34 +617,18 @@ def test_rangelimits(self):
self.assertEqual(set(range(start,stop)),
set([self.gen.randrange(start,stop) for i in range(100)]))

def test_genrandbits(self):
def test_getrandbits(self):
super().test_getrandbits()

# Verify cross-platform repeatability
self.gen.seed(1234567)
self.assertEqual(self.gen.getrandbits(100),
97904845777343510404718956115)
# Verify ranges
for k in range(1, 1000):
self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)

# Verify all bits active
getbits = self.gen.getrandbits
for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
cum = 0
for i in range(100):
cum |= getbits(span)
self.assertEqual(cum, 2**span-1)

# Verify argument checking
self.assertRaises(TypeError, self.gen.getrandbits)
self.assertRaises(TypeError, self.gen.getrandbits, 'a')
self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
self.assertRaises(ValueError, self.gen.getrandbits, 0)
self.assertRaises(ValueError, self.gen.getrandbits, -1)

def test_randrange_uses_getrandbits(self):
# Verify use of getrandbits by randrange
# Use same seed as in the cross-platform repeatability test
# in test_genrandbits above.
# in test_getrandbits above.
self.gen.seed(1234567)
# If randrange uses getrandbits, it should pick getrandbits(100)
# when called with a 100-bits stop argument.
Expand Down
1 change: 1 addition & 0 deletions Misc/NEWS.d/next/Library/2020-04-15-10-23-52.bpo-40282.rIYJmu.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
Allow ``random.getrandbits(0)`` to succeed and to return 0.
8 changes: 5 additions & 3 deletions Modules/_randommodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -474,12 +474,14 @@ _random_Random_getrandbits_impl(RandomObject *self, int k)
uint32_t *wordarray;
PyObject *result;

if (k <= 0) {
PyErr_SetString(PyExc_ValueError,
"number of bits must be greater than zero");
if (k < 0) {
PyErr_SetString(PyExc_ValueError, "number of bits must be positive");
Comment thread
pitrou marked this conversation as resolved.
Outdated
return NULL;
}

if (k == 0)
return PyLong_FromLong(0);

if (k <= 32) /* Fast path */
return PyLong_FromUnsignedLong(genrand_int32(self) >> (32 - k));

Expand Down