From c601117f38aa5e1bcaeb81571eb183f97dca09f3 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sun, 5 Oct 2003 23:35:38 +0000 Subject: SF bug #812202: randint is always even * Extend rangrange() to return meaningful results when the range is larger than 2**53. Only applies to the MersenneTwister. WichmannHill was left alone in the absence of a proof showing how multiple calls could be combined to produce long bit streams. * WichmannHill was missing from __all__. --- Lib/random.py | 49 +++++++++++++++++++++++++++++++++++++++++-------- Lib/test/test_random.py | 32 ++++++++++++++++++++++++++++++++ Misc/NEWS | 6 ++++++ 3 files changed, 79 insertions(+), 8 deletions(-) diff --git a/Lib/random.py b/Lib/random.py index a26e1ad..4ba9d33 100644 --- a/Lib/random.py +++ b/Lib/random.py @@ -38,7 +38,7 @@ General notes on the underlying Mersenne Twister core generator: a single Python step, and is, therefore, threadsafe. """ - +from types import BuiltinMethodType as _BuiltinMethodType from math import log as _log, exp as _exp, pi as _pi, e as _e from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin from math import floor as _floor @@ -47,12 +47,13 @@ __all__ = ["Random","seed","random","uniform","randint","choice","sample", "randrange","shuffle","normalvariate","lognormvariate", "cunifvariate","expovariate","vonmisesvariate","gammavariate", "stdgamma","gauss","betavariate","paretovariate","weibullvariate", - "getstate","setstate","jumpahead"] + "getstate","setstate","jumpahead", "WichmannHill"] NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0) TWOPI = 2.0*_pi LOG4 = _log(4.0) SG_MAGICCONST = 1.0 + _log(4.5) +BPF = 53 # Number of bits in a float # Translated by Guido van Rossum from C source provided by # Adrian Baddeley. Adapted by Raymond Hettinger for use with @@ -131,12 +132,13 @@ class Random(_random.Random): ## -------------------- integer methods ------------------- - def randrange(self, start, stop=None, step=1, int=int, default=None): + def randrange(self, start, stop=None, step=1, int=int, default=None, + maxwidth=1L< 0: + if istart >= maxwidth and type(self.random) is _BuiltinMethod: + return self._randbelow(istart) return int(self.random() * istart) raise ValueError, "empty range for randrange()" @@ -153,7 +157,8 @@ class Random(_random.Random): istop = int(stop) if istop != stop: raise ValueError, "non-integer stop for randrange()" - if step == 1 and istart < istop: + width = istop - istart + if step == 1 and width > 0: # Note that # int(istart + self.random()*(istop - istart)) # instead would be incorrect. For example, consider istart @@ -166,7 +171,9 @@ class Random(_random.Random): # can return a long, and then randrange() would also return # a long, but we're supposed to return an int (for backward # compatibility). - return int(istart + int(self.random()*(istop - istart))) + if width >= maxwidth and type(self.random) is _BuiltinMethod: + return int(istart + self._randbelow(width)) + return int(istart + int(self.random()*width)) if step == 1: raise ValueError, "empty range for randrange()" @@ -175,14 +182,17 @@ class Random(_random.Random): if istep != step: raise ValueError, "non-integer step for randrange()" if istep > 0: - n = (istop - istart + istep - 1) / istep + n = (width + istep - 1) / istep elif istep < 0: - n = (istop - istart + istep + 1) / istep + n = (width + istep + 1) / istep else: raise ValueError, "zero step for randrange()" if n <= 0: raise ValueError, "empty range for randrange()" + + if n >= maxwidth and type(self.random) is _BuiltinMethod: + return istart + self._randbelow(n) return istart + istep*int(self.random() * n) def randint(self, a, b): @@ -191,6 +201,29 @@ class Random(_random.Random): return self.randrange(a, b+1) + def _randbelow(self, n, bpf=BPF, maxwidth=1L< n-1 >= 2**(k-2) + + random = self.random + r = n + while r >= n: + # In Py2.4, this section becomes: r = self.getrandbits(k) + r = long(random() * maxwidth) + bits = bpf + while bits < k: + r = (r << bpf) | (long(random() * maxwidth)) + bits += bpf + r >>= (bits - k) + return r + ## -------------------- sequence methods ------------------- def choice(self, seq): diff --git a/Lib/test/test_random.py b/Lib/test/test_random.py index a58a105..ebb67aa 100644 --- a/Lib/test/test_random.py +++ b/Lib/test/test_random.py @@ -220,6 +220,38 @@ class MersenneTwister_TestBasicOps(TestBasicOps): seed = (1L << (10000 * 8)) - 1 # about 10K bytes self.gen.seed(seed) + def test_53_bits_per_float(self): + # This should pass whenever a C double has 53 bit precision. + span = 2 ** 53 + cum = 0 + for i in xrange(100): + cum |= int(self.gen.random() * span) + self.assertEqual(cum, span-1) + + def test_bigrand(self): + # The randrange routine should build-up the required number of bits + # in stages so that all bit positions are active. + span = 2 ** 500 + cum = 0 + for i in xrange(100): + r = self.gen.randrange(span) + self.assert_(0 <= r < span) + cum |= r + self.assertEqual(cum, span-1) + + def test_bigrand_ranges(self): + for i in [40,80, 160, 200, 211, 250, 375, 512, 550]: + start = self.gen.randrange(2 ** i) + stop = self.gen.randrange(2 ** (i-2)) + if stop <= start: + return + self.assert_(start <= self.gen.randrange(start, stop) < stop) + + def test_rangelimits(self): + for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]: + self.assertEqual(Set(range(start,stop)), + Set([self.gen.randrange(start,stop) for i in xrange(100)])) + _gammacoeff = (0.9999999999995183, 676.5203681218835, -1259.139216722289, 771.3234287757674, -176.6150291498386, 12.50734324009056, -0.1385710331296526, 0.9934937113930748e-05, 0.1659470187408462e-06) diff --git a/Misc/NEWS b/Misc/NEWS index 99d18a8..a92abc9 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -21,6 +21,12 @@ Extension modules - Bug #814613: INET_ADDRSTRLEN fix needed for all compilers on SGI +Library +------- + +- Bug #812202: random.randrange() returned only even numbers + for range lengths above 2**53. + What's New in Python 2.3.2 (final)? =================================== -- cgit v0.12