[Python-checkins] python/dist/src/Lib random.py,1.55,1.56
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Sun Oct 5 05:09:17 EDT 2003
Update of /cvsroot/python/python/dist/src/Lib
In directory sc8-pr-cvs1:/tmp/cvs-serv30780/Lib
Modified Files:
random.py
Log Message:
SF bug #812202: randint is always even
* Added C coded getrandbits(k) method that runs in linear time.
* Call the new method from randrange() for ranges >= 2**53.
* Adds a warning for generators not defining getrandbits() whenever they
have a call to randrange() with too large of a population.
Index: random.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/random.py,v
retrieving revision 1.55
retrieving revision 1.56
diff -C2 -d -r1.55 -r1.56
*** random.py 6 Sep 2003 04:25:54 -0000 1.55
--- random.py 5 Oct 2003 09:09:14 -0000 1.56
***************
*** 40,43 ****
--- 40,45 ----
"""
+ from warnings import warn as _warn
+ from types import MethodType as _MethodType, 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
***************
*** 48,52 ****
"expovariate","vonmisesvariate","gammavariate",
"gauss","betavariate","paretovariate","weibullvariate",
! "getstate","setstate","jumpahead"]
NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
--- 50,55 ----
"expovariate","vonmisesvariate","gammavariate",
"gauss","betavariate","paretovariate","weibullvariate",
! "getstate","setstate","jumpahead", "WichmannHill", "getrandbits",
! "Random"]
NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
***************
*** 54,57 ****
--- 57,61 ----
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
***************
*** 73,76 ****
--- 77,82 ----
generator of your own devising: in that case, override the following
methods: random(), seed(), getstate(), setstate() and jumpahead().
+ Optionally, implement a getrandombits() method so that randrange()
+ can cover arbitrarily large ranges.
"""
***************
*** 132,141 ****
## -------------------- integer methods -------------------
! def randrange(self, start, stop=None, step=1, int=int, default=None):
"""Choose a random item from range(start, stop[, step]).
This fixes the problem with randint() which includes the
endpoint; in Python this is usually not what you want.
! Do not supply the 'int' and 'default' arguments.
"""
--- 138,148 ----
## -------------------- integer methods -------------------
! def randrange(self, start, stop=None, step=1, int=int, default=None,
! maxwidth=1L<<BPF):
"""Choose a random item from range(start, stop[, step]).
This fixes the problem with randint() which includes the
endpoint; in Python this is usually not what you want.
! Do not supply the 'int', 'default', and 'maxwidth' arguments.
"""
***************
*** 147,150 ****
--- 154,159 ----
if stop is default:
if istart > 0:
+ if istart >= maxwidth:
+ return self._randbelow(istart)
return int(self.random() * istart)
raise ValueError, "empty range for randrange()"
***************
*** 154,160 ****
if istop != stop:
raise ValueError, "non-integer stop for randrange()"
! if step == 1 and istart < istop:
# Note that
! # int(istart + self.random()*(istop - istart))
# instead would be incorrect. For example, consider istart
# = -2 and istop = 0. Then the guts would be in
--- 163,170 ----
if istop != stop:
raise ValueError, "non-integer stop for randrange()"
! width = istop - istart
! if step == 1 and width > 0:
# Note that
! # int(istart + self.random()*width)
# instead would be incorrect. For example, consider istart
# = -2 and istop = 0. Then the guts would be in
***************
*** 162,173 ****
# might return 0.0), and because int() truncates toward 0, the
# final result would be -1 or 0 (instead of -2 or -1).
! # istart + int(self.random()*(istop - istart))
# would also be incorrect, for a subtler reason: the RHS
# 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 step == 1:
! raise ValueError, "empty range for randrange()"
# Non-unit step argument supplied.
--- 172,186 ----
# might return 0.0), and because int() truncates toward 0, the
# final result would be -1 or 0 (instead of -2 or -1).
! # istart + int(self.random()*width)
# would also be incorrect, for a subtler reason: the RHS
# can return a long, and then randrange() would also return
# a long, but we're supposed to return an int (for backward
# compatibility).
!
! if width >= maxwidth:
! return int(istart + self._randbelow(width))
! return int(istart + int(self.random()*width))
if step == 1:
! raise ValueError, "empty range for randrange() (%d,%d, %d)" % (istart, istop, width)
# Non-unit step argument supplied.
***************
*** 176,182 ****
raise ValueError, "non-integer step for randrange()"
if istep > 0:
! n = (istop - istart + istep - 1) / istep
elif istep < 0:
! n = (istop - istart + istep + 1) / istep
else:
raise ValueError, "zero step for randrange()"
--- 189,195 ----
raise ValueError, "non-integer step for randrange()"
if istep > 0:
! n = (width + istep - 1) / istep
elif istep < 0:
! n = (width + istep + 1) / istep
else:
raise ValueError, "zero step for randrange()"
***************
*** 184,187 ****
--- 197,203 ----
if n <= 0:
raise ValueError, "empty range for randrange()"
+
+ if n >= maxwidth:
+ return istart + self._randbelow(n)
return istart + istep*int(self.random() * n)
***************
*** 192,195 ****
--- 208,238 ----
return self.randrange(a, b+1)
+ def _randbelow(self, n, _log=_log, int=int, _maxwidth=1L<<BPF,
+ _Method=_MethodType, _BuiltinMethod=_BuiltinMethodType):
+ """Return a random int in the range [0,n)
+
+ Handles the case where n has more bits than returned
+ by a single call to the underlying generator.
+ """
+
+ try:
+ getrandbits = self.getrandbits
+ except AttributeError:
+ pass
+ else:
+ # Only call self.getrandbits if the original random() builtin method
+ # has not been overridden or if a new getrandbits() was supplied.
+ # This assures that the two methods correspond.
+ if type(self.random) is _BuiltinMethod or type(getrandbits) is _Method:
+ k = int(1.00001 + _log(n-1, 2.0)) # 2**k > n-1 > 2**(k-2)
+ r = getrandbits(k)
+ while r >= n:
+ r = getrandbits(k)
+ return r
+ if n >= _maxwidth:
+ _warn("Underlying random() generator does not supply \n"
+ "enough bits to choose from a population range this large")
+ return int(self.random() * n)
+
## -------------------- sequence methods -------------------
***************
*** 758,761 ****
--- 801,805 ----
setstate = _inst.setstate
jumpahead = _inst.jumpahead
+ getrandbits = _inst.getrandbits
if __name__ == '__main__':
More information about the Python-checkins
mailing list