[Python-checkins] python/dist/src/Lib random.py,1.51.8.3,1.51.8.4

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Lib
In directory sc8-pr-cvs1:/tmp/cvs-serv17515/Lib

Modified Files:
      Tag: release23-maint
	random.py 
Log Message:
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__.



Index: random.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/random.py,v
retrieving revision 1.51.8.3
retrieving revision 1.51.8.4
diff -C2 -d -r1.51.8.3 -r1.51.8.4
*** random.py	8 Sep 2003 19:15:43 -0000	1.51.8.3
--- random.py	5 Oct 2003 23:35:38 -0000	1.51.8.4
***************
*** 39,43 ****
  
  """
! 
  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
--- 39,43 ----
  
  """
! 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
***************
*** 48,52 ****
             "cunifvariate","expovariate","vonmisesvariate","gammavariate",
             "stdgamma","gauss","betavariate","paretovariate","weibullvariate",
!            "getstate","setstate","jumpahead"]
  
  NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
--- 48,52 ----
             "cunifvariate","expovariate","vonmisesvariate","gammavariate",
             "stdgamma","gauss","betavariate","paretovariate","weibullvariate",
!            "getstate","setstate","jumpahead", "WichmannHill"]
  
  NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
***************
*** 54,57 ****
--- 54,58 ----
  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
***************
*** 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.
          """
  
--- 133,143 ----
  ## -------------------- integer methods  -------------------
  
!     def randrange(self, start, stop=None, step=1, int=int, default=None,
!                   maxwidth=1L<<BPF, _BuiltinMethod=_BuiltinMethodType):
          """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 ****
--- 149,154 ----
          if stop is default:
              if istart > 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()"
***************
*** 154,158 ****
          if istop != stop:
              raise ValueError, "non-integer stop for randrange()"
!         if step == 1 and istart < istop:
              # Note that
              #     int(istart + self.random()*(istop - istart))
--- 158,163 ----
          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()*(istop - istart))
***************
*** 167,171 ****
              # 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()"
--- 172,178 ----
              # a long, but we're supposed to return an int (for backward
              # compatibility).
!             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()"
***************
*** 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()"
--- 183,189 ----
              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 ****
--- 191,197 ----
          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)
  
***************
*** 191,194 ****
--- 201,227 ----
  
          return self.randrange(a, b+1)
+ 
+     def _randbelow(self, n, bpf=BPF, maxwidth=1L<<BPF,
+                    long=long, _log=_log, int=int):
+         """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.
+         """
+ 
+         # k is a sometimes over but never under estimate of the bits in n
+         k = int(1.00001 + _log(n-1, 2))     # 2**k > 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  -------------------