[New-bugs-announce] [issue23974] random.randrange() biased output

[Christopher Gurnee]

New submission from Christopher Gurnee:

Due to an optimization in random.randrange() only in Python 2, as the stop-start range approaches 2^53 the output becomes noticeably biased. This bug also affects random.SystemRandom.

For example, counting the number of even ints in a set of 10^6 random ints each in the range [0, 2^52 * 2/3) produces normal results; about half are even:

>>> sum(randrange(2**52 * 2//3) % 2 for i in xrange(1000000)) / 1000000.0
0.499932

Change the range to [0, 2^53 * 2/3), and you get a degenerate case where evens are two times more likely to occur than odds:

>>> sum(randrange(2**53 * 2//3) % 2 for i in xrange(1000000)) / 1000000.0
0.333339

The issue occurs in three places inside randrange(), here's one:

if istart >= _maxwidth:
    return self._randbelow(istart)
return _int(self.random() * istart)

_maxwidth is the max size of a double where every digit to the left of the decimal point can still be represented w/o loss of precision (2^53, where a double has 53 mantissa bits). With istart >= _maxwidth, _randbelow() behaves correctly. With istart < _maxwidth, the rounding error in random() * istart begins to cause problems as istart approaches 2^53.

Changing _maxwidth to be significantly less should (practically speaking anyways) fix this, although I'm open to suggestion on just how conservatively it should be set.

----------
components: Library (Lib)
messages: 241261
nosy: gurnec
priority: normal
severity: normal
status: open
title: random.randrange() biased output
versions: Python 2.7

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue23974>
_______________________________________