[Python-checkins] python/dist/src/Lib/test test_random.py, 1.14, 1.15

[rhettinger at users.sourceforge.net]

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

Modified Files:
	test_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: test_random.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/test_random.py,v
retrieving revision 1.14
retrieving revision 1.15
diff -C2 -d -r1.14 -r1.15
*** test_random.py	6 Sep 2003 04:25:54 -0000	1.14
--- test_random.py	5 Oct 2003 09:09:15 -0000	1.15
***************
*** 5,8 ****
--- 5,9 ----
  import time
  import pickle
+ import warnings
  from math import log, exp, sqrt, pi
  from sets import Set
***************
*** 154,157 ****
--- 155,165 ----
              self.assertEqual(y1, y2)
  
+     def test_bigrand(self):
+         # Verify warnings are raised when randrange is too large for random()
+         oldfilters = warnings.filters[:]
+         warnings.filterwarnings("error", "Underlying random")
+         self.assertRaises(UserWarning, self.gen.randrange, 2**60)
+         warnings.filters[:] = oldfilters
+ 
  class MersenneTwister_TestBasicOps(TestBasicOps):
      gen = random.Random()
***************
*** 219,222 ****
--- 227,300 ----
          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)]))
+ 
+     def test_genrandbits(self):
+         # Verify cross-platform repeatability
+         self.gen.seed(1234567)
+         self.assertEqual(self.gen.getrandbits(100),
+                          97904845777343510404718956115L)
+         # Verify ranges
+         for k in xrange(1, 1000):
+             self.assert_(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 xrange(100):
+                 cum |= getbits(span)
+             self.assertEqual(cum, 2**span-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))
+         # is equal to or one greater than the number of bits in n
+         for i in xrange(1, 1000):
+             n = 1L << i # check an exact power of two
+             numbits = i+1
+             k = int(1.00001 + _log(n, 2))
+             self.assertEqual(k, numbits)
+             self.assert_(n == 2**(k-1))
+ 
+             n += n - 1      # check 1 below the next power of two
+             k = int(1.00001 + _log(n, 2))
+             self.assert_(k in [numbits, numbits+1])
+             self.assert_(2**k > n > 2**(k-2))
+ 
+             n -= n >> 15     # check a little farther below the next power of two
+             k = int(1.00001 + _log(n, 2))
+             self.assertEqual(k, numbits)        # note the stronger assertion
+             self.assert_(2**k > n > 2**(k-1))   # note the stronger assertion
  
  _gammacoeff = (0.9999999999995183, 676.5203681218835, -1259.139216722289,