• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python
2
3import unittest
4import random
5import time
6import pickle
7import warnings
8from math import log, exp, pi, fsum, sin
9from functools import reduce
10from test import test_support
11
12class TestBasicOps(unittest.TestCase):
13    # Superclass with tests common to all generators.
14    # Subclasses must arrange for self.gen to retrieve the Random instance
15    # to be tested.
16
17    def randomlist(self, n):
18        """Helper function to make a list of random numbers"""
19        return [self.gen.random() for i in xrange(n)]
20
21    def test_autoseed(self):
22        self.gen.seed()
23        state1 = self.gen.getstate()
24        time.sleep(0.1)
25        self.gen.seed()      # diffent seeds at different times
26        state2 = self.gen.getstate()
27        self.assertNotEqual(state1, state2)
28
29    def test_saverestore(self):
30        N = 1000
31        self.gen.seed()
32        state = self.gen.getstate()
33        randseq = self.randomlist(N)
34        self.gen.setstate(state)    # should regenerate the same sequence
35        self.assertEqual(randseq, self.randomlist(N))
36
37    def test_seedargs(self):
38        for arg in [None, 0, 0L, 1, 1L, -1, -1L, 10**20, -(10**20),
39                    3.14, 1+2j, 'a', tuple('abc')]:
40            self.gen.seed(arg)
41        for arg in [range(3), dict(one=1)]:
42            self.assertRaises(TypeError, self.gen.seed, arg)
43        self.assertRaises(TypeError, self.gen.seed, 1, 2)
44        self.assertRaises(TypeError, type(self.gen), [])
45
46    def test_jumpahead(self):
47        self.gen.seed()
48        state1 = self.gen.getstate()
49        self.gen.jumpahead(100)
50        state2 = self.gen.getstate()    # s/b distinct from state1
51        self.assertNotEqual(state1, state2)
52        self.gen.jumpahead(100)
53        state3 = self.gen.getstate()    # s/b distinct from state2
54        self.assertNotEqual(state2, state3)
55
56        with test_support.check_py3k_warnings(quiet=True):
57            self.assertRaises(TypeError, self.gen.jumpahead)  # needs an arg
58            self.assertRaises(TypeError, self.gen.jumpahead, 2, 3)  # too many
59
60    def test_sample(self):
61        # For the entire allowable range of 0 <= k <= N, validate that
62        # the sample is of the correct length and contains only unique items
63        N = 100
64        population = xrange(N)
65        for k in xrange(N+1):
66            s = self.gen.sample(population, k)
67            self.assertEqual(len(s), k)
68            uniq = set(s)
69            self.assertEqual(len(uniq), k)
70            self.assertTrue(uniq <= set(population))
71        self.assertEqual(self.gen.sample([], 0), [])  # test edge case N==k==0
72
73    def test_sample_distribution(self):
74        # For the entire allowable range of 0 <= k <= N, validate that
75        # sample generates all possible permutations
76        n = 5
77        pop = range(n)
78        trials = 10000  # large num prevents false negatives without slowing normal case
79        def factorial(n):
80            return reduce(int.__mul__, xrange(1, n), 1)
81        for k in xrange(n):
82            expected = factorial(n) // factorial(n-k)
83            perms = {}
84            for i in xrange(trials):
85                perms[tuple(self.gen.sample(pop, k))] = None
86                if len(perms) == expected:
87                    break
88            else:
89                self.fail()
90
91    def test_sample_inputs(self):
92        # SF bug #801342 -- population can be any iterable defining __len__()
93        self.gen.sample(set(range(20)), 2)
94        self.gen.sample(range(20), 2)
95        self.gen.sample(xrange(20), 2)
96        self.gen.sample(str('abcdefghijklmnopqrst'), 2)
97        self.gen.sample(tuple('abcdefghijklmnopqrst'), 2)
98
99    def test_sample_on_dicts(self):
100        self.gen.sample(dict.fromkeys('abcdefghijklmnopqrst'), 2)
101
102        # SF bug #1460340 -- random.sample can raise KeyError
103        a = dict.fromkeys(range(10)+range(10,100,2)+range(100,110))
104        self.gen.sample(a, 3)
105
106        # A followup to bug #1460340:  sampling from a dict could return
107        # a subset of its keys or of its values, depending on the size of
108        # the subset requested.
109        N = 30
110        d = dict((i, complex(i, i)) for i in xrange(N))
111        for k in xrange(N+1):
112            samp = self.gen.sample(d, k)
113            # Verify that we got ints back (keys); the values are complex.
114            for x in samp:
115                self.assertTrue(type(x) is int)
116        samp.sort()
117        self.assertEqual(samp, range(N))
118
119    def test_gauss(self):
120        # Ensure that the seed() method initializes all the hidden state.  In
121        # particular, through 2.2.1 it failed to reset a piece of state used
122        # by (and only by) the .gauss() method.
123
124        for seed in 1, 12, 123, 1234, 12345, 123456, 654321:
125            self.gen.seed(seed)
126            x1 = self.gen.random()
127            y1 = self.gen.gauss(0, 1)
128
129            self.gen.seed(seed)
130            x2 = self.gen.random()
131            y2 = self.gen.gauss(0, 1)
132
133            self.assertEqual(x1, x2)
134            self.assertEqual(y1, y2)
135
136    def test_pickling(self):
137        state = pickle.dumps(self.gen)
138        origseq = [self.gen.random() for i in xrange(10)]
139        newgen = pickle.loads(state)
140        restoredseq = [newgen.random() for i in xrange(10)]
141        self.assertEqual(origseq, restoredseq)
142
143    def test_bug_1727780(self):
144        # verify that version-2-pickles can be loaded
145        # fine, whether they are created on 32-bit or 64-bit
146        # platforms, and that version-3-pickles load fine.
147        files = [("randv2_32.pck", 780),
148                 ("randv2_64.pck", 866),
149                 ("randv3.pck", 343)]
150        for file, value in files:
151            f = open(test_support.findfile(file),"rb")
152            r = pickle.load(f)
153            f.close()
154            self.assertEqual(r.randrange(1000), value)
155
156class WichmannHill_TestBasicOps(TestBasicOps):
157    gen = random.WichmannHill()
158
159    def test_setstate_first_arg(self):
160        self.assertRaises(ValueError, self.gen.setstate, (2, None, None))
161
162    def test_strong_jumpahead(self):
163        # tests that jumpahead(n) semantics correspond to n calls to random()
164        N = 1000
165        s = self.gen.getstate()
166        self.gen.jumpahead(N)
167        r1 = self.gen.random()
168        # now do it the slow way
169        self.gen.setstate(s)
170        for i in xrange(N):
171            self.gen.random()
172        r2 = self.gen.random()
173        self.assertEqual(r1, r2)
174
175    def test_gauss_with_whseed(self):
176        # Ensure that the seed() method initializes all the hidden state.  In
177        # particular, through 2.2.1 it failed to reset a piece of state used
178        # by (and only by) the .gauss() method.
179
180        for seed in 1, 12, 123, 1234, 12345, 123456, 654321:
181            self.gen.whseed(seed)
182            x1 = self.gen.random()
183            y1 = self.gen.gauss(0, 1)
184
185            self.gen.whseed(seed)
186            x2 = self.gen.random()
187            y2 = self.gen.gauss(0, 1)
188
189            self.assertEqual(x1, x2)
190            self.assertEqual(y1, y2)
191
192    def test_bigrand(self):
193        # Verify warnings are raised when randrange is too large for random()
194        with warnings.catch_warnings():
195            warnings.filterwarnings("error", "Underlying random")
196            self.assertRaises(UserWarning, self.gen.randrange, 2**60)
197
198class SystemRandom_TestBasicOps(TestBasicOps):
199    gen = random.SystemRandom()
200
201    def test_autoseed(self):
202        # Doesn't need to do anything except not fail
203        self.gen.seed()
204
205    def test_saverestore(self):
206        self.assertRaises(NotImplementedError, self.gen.getstate)
207        self.assertRaises(NotImplementedError, self.gen.setstate, None)
208
209    def test_seedargs(self):
210        # Doesn't need to do anything except not fail
211        self.gen.seed(100)
212
213    def test_jumpahead(self):
214        # Doesn't need to do anything except not fail
215        self.gen.jumpahead(100)
216
217    def test_gauss(self):
218        self.gen.gauss_next = None
219        self.gen.seed(100)
220        self.assertEqual(self.gen.gauss_next, None)
221
222    def test_pickling(self):
223        self.assertRaises(NotImplementedError, pickle.dumps, self.gen)
224
225    def test_53_bits_per_float(self):
226        # This should pass whenever a C double has 53 bit precision.
227        span = 2 ** 53
228        cum = 0
229        for i in xrange(100):
230            cum |= int(self.gen.random() * span)
231        self.assertEqual(cum, span-1)
232
233    def test_bigrand(self):
234        # The randrange routine should build-up the required number of bits
235        # in stages so that all bit positions are active.
236        span = 2 ** 500
237        cum = 0
238        for i in xrange(100):
239            r = self.gen.randrange(span)
240            self.assertTrue(0 <= r < span)
241            cum |= r
242        self.assertEqual(cum, span-1)
243
244    def test_bigrand_ranges(self):
245        for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
246            start = self.gen.randrange(2 ** i)
247            stop = self.gen.randrange(2 ** (i-2))
248            if stop <= start:
249                return
250            self.assertTrue(start <= self.gen.randrange(start, stop) < stop)
251
252    def test_rangelimits(self):
253        for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
254            self.assertEqual(set(range(start,stop)),
255                set([self.gen.randrange(start,stop) for i in xrange(100)]))
256
257    def test_genrandbits(self):
258        # Verify ranges
259        for k in xrange(1, 1000):
260            self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)
261
262        # Verify all bits active
263        getbits = self.gen.getrandbits
264        for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
265            cum = 0
266            for i in xrange(100):
267                cum |= getbits(span)
268            self.assertEqual(cum, 2**span-1)
269
270        # Verify argument checking
271        self.assertRaises(TypeError, self.gen.getrandbits)
272        self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
273        self.assertRaises(ValueError, self.gen.getrandbits, 0)
274        self.assertRaises(ValueError, self.gen.getrandbits, -1)
275        self.assertRaises(TypeError, self.gen.getrandbits, 10.1)
276
277    def test_randbelow_logic(self, _log=log, int=int):
278        # check bitcount transition points:  2**i and 2**(i+1)-1
279        # show that: k = int(1.001 + _log(n, 2))
280        # is equal to or one greater than the number of bits in n
281        for i in xrange(1, 1000):
282            n = 1L << i # check an exact power of two
283            numbits = i+1
284            k = int(1.00001 + _log(n, 2))
285            self.assertEqual(k, numbits)
286            self.assertTrue(n == 2**(k-1))
287
288            n += n - 1      # check 1 below the next power of two
289            k = int(1.00001 + _log(n, 2))
290            self.assertIn(k, [numbits, numbits+1])
291            self.assertTrue(2**k > n > 2**(k-2))
292
293            n -= n >> 15     # check a little farther below the next power of two
294            k = int(1.00001 + _log(n, 2))
295            self.assertEqual(k, numbits)        # note the stronger assertion
296            self.assertTrue(2**k > n > 2**(k-1))   # note the stronger assertion
297
298
299class MersenneTwister_TestBasicOps(TestBasicOps):
300    gen = random.Random()
301
302    def test_setstate_first_arg(self):
303        self.assertRaises(ValueError, self.gen.setstate, (1, None, None))
304
305    def test_setstate_middle_arg(self):
306        # Wrong type, s/b tuple
307        self.assertRaises(TypeError, self.gen.setstate, (2, None, None))
308        # Wrong length, s/b 625
309        self.assertRaises(ValueError, self.gen.setstate, (2, (1,2,3), None))
310        # Wrong type, s/b tuple of 625 ints
311        self.assertRaises(TypeError, self.gen.setstate, (2, ('a',)*625, None))
312        # Last element s/b an int also
313        self.assertRaises(TypeError, self.gen.setstate, (2, (0,)*624+('a',), None))
314
315    def test_referenceImplementation(self):
316        # Compare the python implementation with results from the original
317        # code.  Create 2000 53-bit precision random floats.  Compare only
318        # the last ten entries to show that the independent implementations
319        # are tracking.  Here is the main() function needed to create the
320        # list of expected random numbers:
321        #    void main(void){
322        #         int i;
323        #         unsigned long init[4]={61731, 24903, 614, 42143}, length=4;
324        #         init_by_array(init, length);
325        #         for (i=0; i<2000; i++) {
326        #           printf("%.15f ", genrand_res53());
327        #           if (i%5==4) printf("\n");
328        #         }
329        #     }
330        expected = [0.45839803073713259,
331                    0.86057815201978782,
332                    0.92848331726782152,
333                    0.35932681119782461,
334                    0.081823493762449573,
335                    0.14332226470169329,
336                    0.084297823823520024,
337                    0.53814864671831453,
338                    0.089215024911993401,
339                    0.78486196105372907]
340
341        self.gen.seed(61731L + (24903L<<32) + (614L<<64) + (42143L<<96))
342        actual = self.randomlist(2000)[-10:]
343        for a, e in zip(actual, expected):
344            self.assertAlmostEqual(a,e,places=14)
345
346    def test_strong_reference_implementation(self):
347        # Like test_referenceImplementation, but checks for exact bit-level
348        # equality.  This should pass on any box where C double contains
349        # at least 53 bits of precision (the underlying algorithm suffers
350        # no rounding errors -- all results are exact).
351        from math import ldexp
352
353        expected = [0x0eab3258d2231fL,
354                    0x1b89db315277a5L,
355                    0x1db622a5518016L,
356                    0x0b7f9af0d575bfL,
357                    0x029e4c4db82240L,
358                    0x04961892f5d673L,
359                    0x02b291598e4589L,
360                    0x11388382c15694L,
361                    0x02dad977c9e1feL,
362                    0x191d96d4d334c6L]
363        self.gen.seed(61731L + (24903L<<32) + (614L<<64) + (42143L<<96))
364        actual = self.randomlist(2000)[-10:]
365        for a, e in zip(actual, expected):
366            self.assertEqual(long(ldexp(a, 53)), e)
367
368    def test_long_seed(self):
369        # This is most interesting to run in debug mode, just to make sure
370        # nothing blows up.  Under the covers, a dynamically resized array
371        # is allocated, consuming space proportional to the number of bits
372        # in the seed.  Unfortunately, that's a quadratic-time algorithm,
373        # so don't make this horribly big.
374        seed = (1L << (10000 * 8)) - 1  # about 10K bytes
375        self.gen.seed(seed)
376
377    def test_53_bits_per_float(self):
378        # This should pass whenever a C double has 53 bit precision.
379        span = 2 ** 53
380        cum = 0
381        for i in xrange(100):
382            cum |= int(self.gen.random() * span)
383        self.assertEqual(cum, span-1)
384
385    def test_bigrand(self):
386        # The randrange routine should build-up the required number of bits
387        # in stages so that all bit positions are active.
388        span = 2 ** 500
389        cum = 0
390        for i in xrange(100):
391            r = self.gen.randrange(span)
392            self.assertTrue(0 <= r < span)
393            cum |= r
394        self.assertEqual(cum, span-1)
395
396    def test_bigrand_ranges(self):
397        for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
398            start = self.gen.randrange(2 ** i)
399            stop = self.gen.randrange(2 ** (i-2))
400            if stop <= start:
401                return
402            self.assertTrue(start <= self.gen.randrange(start, stop) < stop)
403
404    def test_rangelimits(self):
405        for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
406            self.assertEqual(set(range(start,stop)),
407                set([self.gen.randrange(start,stop) for i in xrange(100)]))
408
409    def test_genrandbits(self):
410        # Verify cross-platform repeatability
411        self.gen.seed(1234567)
412        self.assertEqual(self.gen.getrandbits(100),
413                         97904845777343510404718956115L)
414        # Verify ranges
415        for k in xrange(1, 1000):
416            self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)
417
418        # Verify all bits active
419        getbits = self.gen.getrandbits
420        for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
421            cum = 0
422            for i in xrange(100):
423                cum |= getbits(span)
424            self.assertEqual(cum, 2**span-1)
425
426        # Verify argument checking
427        self.assertRaises(TypeError, self.gen.getrandbits)
428        self.assertRaises(TypeError, self.gen.getrandbits, 'a')
429        self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
430        self.assertRaises(ValueError, self.gen.getrandbits, 0)
431        self.assertRaises(ValueError, self.gen.getrandbits, -1)
432
433    def test_randbelow_logic(self, _log=log, int=int):
434        # check bitcount transition points:  2**i and 2**(i+1)-1
435        # show that: k = int(1.001 + _log(n, 2))
436        # is equal to or one greater than the number of bits in n
437        for i in xrange(1, 1000):
438            n = 1L << i # check an exact power of two
439            numbits = i+1
440            k = int(1.00001 + _log(n, 2))
441            self.assertEqual(k, numbits)
442            self.assertTrue(n == 2**(k-1))
443
444            n += n - 1      # check 1 below the next power of two
445            k = int(1.00001 + _log(n, 2))
446            self.assertIn(k, [numbits, numbits+1])
447            self.assertTrue(2**k > n > 2**(k-2))
448
449            n -= n >> 15     # check a little farther below the next power of two
450            k = int(1.00001 + _log(n, 2))
451            self.assertEqual(k, numbits)        # note the stronger assertion
452            self.assertTrue(2**k > n > 2**(k-1))   # note the stronger assertion
453
454    def test_randrange_bug_1590891(self):
455        start = 1000000000000
456        stop = -100000000000000000000
457        step = -200
458        x = self.gen.randrange(start, stop, step)
459        self.assertTrue(stop < x <= start)
460        self.assertEqual((x+stop)%step, 0)
461
462def gamma(z, sqrt2pi=(2.0*pi)**0.5):
463    # Reflection to right half of complex plane
464    if z < 0.5:
465        return pi / sin(pi*z) / gamma(1.0-z)
466    # Lanczos approximation with g=7
467    az = z + (7.0 - 0.5)
468    return az ** (z-0.5) / exp(az) * sqrt2pi * fsum([
469        0.9999999999995183,
470        676.5203681218835 / z,
471        -1259.139216722289 / (z+1.0),
472        771.3234287757674 / (z+2.0),
473        -176.6150291498386 / (z+3.0),
474        12.50734324009056 / (z+4.0),
475        -0.1385710331296526 / (z+5.0),
476        0.9934937113930748e-05 / (z+6.0),
477        0.1659470187408462e-06 / (z+7.0),
478    ])
479
480class TestDistributions(unittest.TestCase):
481    def test_zeroinputs(self):
482        # Verify that distributions can handle a series of zero inputs'
483        g = random.Random()
484        x = [g.random() for i in xrange(50)] + [0.0]*5
485        g.random = x[:].pop; g.uniform(1,10)
486        g.random = x[:].pop; g.paretovariate(1.0)
487        g.random = x[:].pop; g.expovariate(1.0)
488        g.random = x[:].pop; g.weibullvariate(1.0, 1.0)
489        g.random = x[:].pop; g.normalvariate(0.0, 1.0)
490        g.random = x[:].pop; g.gauss(0.0, 1.0)
491        g.random = x[:].pop; g.lognormvariate(0.0, 1.0)
492        g.random = x[:].pop; g.vonmisesvariate(0.0, 1.0)
493        g.random = x[:].pop; g.gammavariate(0.01, 1.0)
494        g.random = x[:].pop; g.gammavariate(1.0, 1.0)
495        g.random = x[:].pop; g.gammavariate(200.0, 1.0)
496        g.random = x[:].pop; g.betavariate(3.0, 3.0)
497        g.random = x[:].pop; g.triangular(0.0, 1.0, 1.0/3.0)
498
499    def test_avg_std(self):
500        # Use integration to test distribution average and standard deviation.
501        # Only works for distributions which do not consume variates in pairs
502        g = random.Random()
503        N = 5000
504        x = [i/float(N) for i in xrange(1,N)]
505        for variate, args, mu, sigmasqrd in [
506                (g.uniform, (1.0,10.0), (10.0+1.0)/2, (10.0-1.0)**2/12),
507                (g.triangular, (0.0, 1.0, 1.0/3.0), 4.0/9.0, 7.0/9.0/18.0),
508                (g.expovariate, (1.5,), 1/1.5, 1/1.5**2),
509                (g.paretovariate, (5.0,), 5.0/(5.0-1),
510                                  5.0/((5.0-1)**2*(5.0-2))),
511                (g.weibullvariate, (1.0, 3.0), gamma(1+1/3.0),
512                                  gamma(1+2/3.0)-gamma(1+1/3.0)**2) ]:
513            g.random = x[:].pop
514            y = []
515            for i in xrange(len(x)):
516                try:
517                    y.append(variate(*args))
518                except IndexError:
519                    pass
520            s1 = s2 = 0
521            for e in y:
522                s1 += e
523                s2 += (e - mu) ** 2
524            N = len(y)
525            self.assertAlmostEqual(s1/N, mu, 2)
526            self.assertAlmostEqual(s2/(N-1), sigmasqrd, 2)
527
528class TestModule(unittest.TestCase):
529    def testMagicConstants(self):
530        self.assertAlmostEqual(random.NV_MAGICCONST, 1.71552776992141)
531        self.assertAlmostEqual(random.TWOPI, 6.28318530718)
532        self.assertAlmostEqual(random.LOG4, 1.38629436111989)
533        self.assertAlmostEqual(random.SG_MAGICCONST, 2.50407739677627)
534
535    def test__all__(self):
536        # tests validity but not completeness of the __all__ list
537        self.assertTrue(set(random.__all__) <= set(dir(random)))
538
539    def test_random_subclass_with_kwargs(self):
540        # SF bug #1486663 -- this used to erroneously raise a TypeError
541        class Subclass(random.Random):
542            def __init__(self, newarg=None):
543                random.Random.__init__(self)
544        Subclass(newarg=1)
545
546
547def test_main(verbose=None):
548    testclasses =    [WichmannHill_TestBasicOps,
549                      MersenneTwister_TestBasicOps,
550                      TestDistributions,
551                      TestModule]
552
553    try:
554        random.SystemRandom().random()
555    except NotImplementedError:
556        pass
557    else:
558        testclasses.append(SystemRandom_TestBasicOps)
559
560    test_support.run_unittest(*testclasses)
561
562    # verify reference counting
563    import sys
564    if verbose and hasattr(sys, "gettotalrefcount"):
565        counts = [None] * 5
566        for i in xrange(len(counts)):
567            test_support.run_unittest(*testclasses)
568            counts[i] = sys.gettotalrefcount()
569        print counts
570
571if __name__ == "__main__":
572    test_main(verbose=True)
573