1import unittest
2import unittest.mock
3import random
4import time
5import pickle
6import warnings
7from functools import partial
8from math import log, exp, pi, fsum, sin
9from test import support
10from fractions import Fraction
11
12class TestBasicOps:
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 range(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        # Seed value with a negative hash.
39        class MySeed(object):
40            def __hash__(self):
41                return -1729
42        for arg in [None, 0, 0, 1, 1, -1, -1, 10**20, -(10**20),
43                    3.14, 1+2j, 'a', tuple('abc'), MySeed()]:
44            self.gen.seed(arg)
45        for arg in [list(range(3)), dict(one=1)]:
46            self.assertRaises(TypeError, self.gen.seed, arg)
47        self.assertRaises(TypeError, self.gen.seed, 1, 2, 3, 4)
48        self.assertRaises(TypeError, type(self.gen), [])
49
50    @unittest.mock.patch('random._urandom') # os.urandom
51    def test_seed_when_randomness_source_not_found(self, urandom_mock):
52        # Random.seed() uses time.time() when an operating system specific
53        # randomness source is not found. To test this on machines were it
54        # exists, run the above test, test_seedargs(), again after mocking
55        # os.urandom() so that it raises the exception expected when the
56        # randomness source is not available.
57        urandom_mock.side_effect = NotImplementedError
58        self.test_seedargs()
59
60    def test_shuffle(self):
61        shuffle = self.gen.shuffle
62        lst = []
63        shuffle(lst)
64        self.assertEqual(lst, [])
65        lst = [37]
66        shuffle(lst)
67        self.assertEqual(lst, [37])
68        seqs = [list(range(n)) for n in range(10)]
69        shuffled_seqs = [list(range(n)) for n in range(10)]
70        for shuffled_seq in shuffled_seqs:
71            shuffle(shuffled_seq)
72        for (seq, shuffled_seq) in zip(seqs, shuffled_seqs):
73            self.assertEqual(len(seq), len(shuffled_seq))
74            self.assertEqual(set(seq), set(shuffled_seq))
75        # The above tests all would pass if the shuffle was a
76        # no-op. The following non-deterministic test covers that.  It
77        # asserts that the shuffled sequence of 1000 distinct elements
78        # must be different from the original one. Although there is
79        # mathematically a non-zero probability that this could
80        # actually happen in a genuinely random shuffle, it is
81        # completely negligible, given that the number of possible
82        # permutations of 1000 objects is 1000! (factorial of 1000),
83        # which is considerably larger than the number of atoms in the
84        # universe...
85        lst = list(range(1000))
86        shuffled_lst = list(range(1000))
87        shuffle(shuffled_lst)
88        self.assertTrue(lst != shuffled_lst)
89        shuffle(lst)
90        self.assertTrue(lst != shuffled_lst)
91
92    def test_choice(self):
93        choice = self.gen.choice
94        with self.assertRaises(IndexError):
95            choice([])
96        self.assertEqual(choice([50]), 50)
97        self.assertIn(choice([25, 75]), [25, 75])
98
99    def test_sample(self):
100        # For the entire allowable range of 0 <= k <= N, validate that
101        # the sample is of the correct length and contains only unique items
102        N = 100
103        population = range(N)
104        for k in range(N+1):
105            s = self.gen.sample(population, k)
106            self.assertEqual(len(s), k)
107            uniq = set(s)
108            self.assertEqual(len(uniq), k)
109            self.assertTrue(uniq <= set(population))
110        self.assertEqual(self.gen.sample([], 0), [])  # test edge case N==k==0
111        # Exception raised if size of sample exceeds that of population
112        self.assertRaises(ValueError, self.gen.sample, population, N+1)
113        self.assertRaises(ValueError, self.gen.sample, [], -1)
114
115    def test_sample_distribution(self):
116        # For the entire allowable range of 0 <= k <= N, validate that
117        # sample generates all possible permutations
118        n = 5
119        pop = range(n)
120        trials = 10000  # large num prevents false negatives without slowing normal case
121        def factorial(n):
122            if n == 0:
123                return 1
124            return n * factorial(n - 1)
125        for k in range(n):
126            expected = factorial(n) // factorial(n-k)
127            perms = {}
128            for i in range(trials):
129                perms[tuple(self.gen.sample(pop, k))] = None
130                if len(perms) == expected:
131                    break
132            else:
133                self.fail()
134
135    def test_sample_inputs(self):
136        # SF bug #801342 -- population can be any iterable defining __len__()
137        self.gen.sample(set(range(20)), 2)
138        self.gen.sample(range(20), 2)
139        self.gen.sample(range(20), 2)
140        self.gen.sample(str('abcdefghijklmnopqrst'), 2)
141        self.gen.sample(tuple('abcdefghijklmnopqrst'), 2)
142
143    def test_sample_on_dicts(self):
144        self.assertRaises(TypeError, self.gen.sample, dict.fromkeys('abcdef'), 2)
145
146    def test_choices(self):
147        choices = self.gen.choices
148        data = ['red', 'green', 'blue', 'yellow']
149        str_data = 'abcd'
150        range_data = range(4)
151        set_data = set(range(4))
152
153        # basic functionality
154        for sample in [
155            choices(data, k=5),
156            choices(data, range(4), k=5),
157            choices(k=5, population=data, weights=range(4)),
158            choices(k=5, population=data, cum_weights=range(4)),
159        ]:
160            self.assertEqual(len(sample), 5)
161            self.assertEqual(type(sample), list)
162            self.assertTrue(set(sample) <= set(data))
163
164        # test argument handling
165        with self.assertRaises(TypeError):                               # missing arguments
166            choices(2)
167
168        self.assertEqual(choices(data, k=0), [])                         # k == 0
169        self.assertEqual(choices(data, k=-1), [])                        # negative k behaves like ``[0] * -1``
170        with self.assertRaises(TypeError):
171            choices(data, k=2.5)                                         # k is a float
172
173        self.assertTrue(set(choices(str_data, k=5)) <= set(str_data))    # population is a string sequence
174        self.assertTrue(set(choices(range_data, k=5)) <= set(range_data))  # population is a range
175        with self.assertRaises(TypeError):
176            choices(set_data, k=2)                                       # population is not a sequence
177
178        self.assertTrue(set(choices(data, None, k=5)) <= set(data))      # weights is None
179        self.assertTrue(set(choices(data, weights=None, k=5)) <= set(data))
180        with self.assertRaises(ValueError):
181            choices(data, [1,2], k=5)                                    # len(weights) != len(population)
182        with self.assertRaises(TypeError):
183            choices(data, 10, k=5)                                       # non-iterable weights
184        with self.assertRaises(TypeError):
185            choices(data, [None]*4, k=5)                                 # non-numeric weights
186        for weights in [
187                [15, 10, 25, 30],                                                 # integer weights
188                [15.1, 10.2, 25.2, 30.3],                                         # float weights
189                [Fraction(1, 3), Fraction(2, 6), Fraction(3, 6), Fraction(4, 6)], # fractional weights
190                [True, False, True, False]                                        # booleans (include / exclude)
191        ]:
192            self.assertTrue(set(choices(data, weights, k=5)) <= set(data))
193
194        with self.assertRaises(ValueError):
195            choices(data, cum_weights=[1,2], k=5)                        # len(weights) != len(population)
196        with self.assertRaises(TypeError):
197            choices(data, cum_weights=10, k=5)                           # non-iterable cum_weights
198        with self.assertRaises(TypeError):
199            choices(data, cum_weights=[None]*4, k=5)                     # non-numeric cum_weights
200        with self.assertRaises(TypeError):
201            choices(data, range(4), cum_weights=range(4), k=5)           # both weights and cum_weights
202        for weights in [
203                [15, 10, 25, 30],                                                 # integer cum_weights
204                [15.1, 10.2, 25.2, 30.3],                                         # float cum_weights
205                [Fraction(1, 3), Fraction(2, 6), Fraction(3, 6), Fraction(4, 6)], # fractional cum_weights
206        ]:
207            self.assertTrue(set(choices(data, cum_weights=weights, k=5)) <= set(data))
208
209        # Test weight focused on a single element of the population
210        self.assertEqual(choices('abcd', [1, 0, 0, 0]), ['a'])
211        self.assertEqual(choices('abcd', [0, 1, 0, 0]), ['b'])
212        self.assertEqual(choices('abcd', [0, 0, 1, 0]), ['c'])
213        self.assertEqual(choices('abcd', [0, 0, 0, 1]), ['d'])
214
215        # Test consistency with random.choice() for empty population
216        with self.assertRaises(IndexError):
217            choices([], k=1)
218        with self.assertRaises(IndexError):
219            choices([], weights=[], k=1)
220        with self.assertRaises(IndexError):
221            choices([], cum_weights=[], k=5)
222
223    def test_gauss(self):
224        # Ensure that the seed() method initializes all the hidden state.  In
225        # particular, through 2.2.1 it failed to reset a piece of state used
226        # by (and only by) the .gauss() method.
227
228        for seed in 1, 12, 123, 1234, 12345, 123456, 654321:
229            self.gen.seed(seed)
230            x1 = self.gen.random()
231            y1 = self.gen.gauss(0, 1)
232
233            self.gen.seed(seed)
234            x2 = self.gen.random()
235            y2 = self.gen.gauss(0, 1)
236
237            self.assertEqual(x1, x2)
238            self.assertEqual(y1, y2)
239
240    def test_pickling(self):
241        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
242            state = pickle.dumps(self.gen, proto)
243            origseq = [self.gen.random() for i in range(10)]
244            newgen = pickle.loads(state)
245            restoredseq = [newgen.random() for i in range(10)]
246            self.assertEqual(origseq, restoredseq)
247
248    def test_bug_1727780(self):
249        # verify that version-2-pickles can be loaded
250        # fine, whether they are created on 32-bit or 64-bit
251        # platforms, and that version-3-pickles load fine.
252        files = [("randv2_32.pck", 780),
253                 ("randv2_64.pck", 866),
254                 ("randv3.pck", 343)]
255        for file, value in files:
256            f = open(support.findfile(file),"rb")
257            r = pickle.load(f)
258            f.close()
259            self.assertEqual(int(r.random()*1000), value)
260
261    def test_bug_9025(self):
262        # Had problem with an uneven distribution in int(n*random())
263        # Verify the fix by checking that distributions fall within expectations.
264        n = 100000
265        randrange = self.gen.randrange
266        k = sum(randrange(6755399441055744) % 3 == 2 for i in range(n))
267        self.assertTrue(0.30 < k/n < .37, (k/n))
268
269try:
270    random.SystemRandom().random()
271except NotImplementedError:
272    SystemRandom_available = False
273else:
274    SystemRandom_available = True
275
276@unittest.skipUnless(SystemRandom_available, "random.SystemRandom not available")
277class SystemRandom_TestBasicOps(TestBasicOps, unittest.TestCase):
278    gen = random.SystemRandom()
279
280    def test_autoseed(self):
281        # Doesn't need to do anything except not fail
282        self.gen.seed()
283
284    def test_saverestore(self):
285        self.assertRaises(NotImplementedError, self.gen.getstate)
286        self.assertRaises(NotImplementedError, self.gen.setstate, None)
287
288    def test_seedargs(self):
289        # Doesn't need to do anything except not fail
290        self.gen.seed(100)
291
292    def test_gauss(self):
293        self.gen.gauss_next = None
294        self.gen.seed(100)
295        self.assertEqual(self.gen.gauss_next, None)
296
297    def test_pickling(self):
298        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
299            self.assertRaises(NotImplementedError, pickle.dumps, self.gen, proto)
300
301    def test_53_bits_per_float(self):
302        # This should pass whenever a C double has 53 bit precision.
303        span = 2 ** 53
304        cum = 0
305        for i in range(100):
306            cum |= int(self.gen.random() * span)
307        self.assertEqual(cum, span-1)
308
309    def test_bigrand(self):
310        # The randrange routine should build-up the required number of bits
311        # in stages so that all bit positions are active.
312        span = 2 ** 500
313        cum = 0
314        for i in range(100):
315            r = self.gen.randrange(span)
316            self.assertTrue(0 <= r < span)
317            cum |= r
318        self.assertEqual(cum, span-1)
319
320    def test_bigrand_ranges(self):
321        for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
322            start = self.gen.randrange(2 ** (i-2))
323            stop = self.gen.randrange(2 ** i)
324            if stop <= start:
325                continue
326            self.assertTrue(start <= self.gen.randrange(start, stop) < stop)
327
328    def test_rangelimits(self):
329        for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
330            self.assertEqual(set(range(start,stop)),
331                set([self.gen.randrange(start,stop) for i in range(100)]))
332
333    def test_randrange_nonunit_step(self):
334        rint = self.gen.randrange(0, 10, 2)
335        self.assertIn(rint, (0, 2, 4, 6, 8))
336        rint = self.gen.randrange(0, 2, 2)
337        self.assertEqual(rint, 0)
338
339    def test_randrange_errors(self):
340        raises = partial(self.assertRaises, ValueError, self.gen.randrange)
341        # Empty range
342        raises(3, 3)
343        raises(-721)
344        raises(0, 100, -12)
345        # Non-integer start/stop
346        raises(3.14159)
347        raises(0, 2.71828)
348        # Zero and non-integer step
349        raises(0, 42, 0)
350        raises(0, 42, 3.14159)
351
352    def test_genrandbits(self):
353        # Verify ranges
354        for k in range(1, 1000):
355            self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)
356
357        # Verify all bits active
358        getbits = self.gen.getrandbits
359        for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
360            cum = 0
361            for i in range(100):
362                cum |= getbits(span)
363            self.assertEqual(cum, 2**span-1)
364
365        # Verify argument checking
366        self.assertRaises(TypeError, self.gen.getrandbits)
367        self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
368        self.assertRaises(ValueError, self.gen.getrandbits, 0)
369        self.assertRaises(ValueError, self.gen.getrandbits, -1)
370        self.assertRaises(TypeError, self.gen.getrandbits, 10.1)
371
372    def test_randbelow_logic(self, _log=log, int=int):
373        # check bitcount transition points:  2**i and 2**(i+1)-1
374        # show that: k = int(1.001 + _log(n, 2))
375        # is equal to or one greater than the number of bits in n
376        for i in range(1, 1000):
377            n = 1 << i # check an exact power of two
378            numbits = i+1
379            k = int(1.00001 + _log(n, 2))
380            self.assertEqual(k, numbits)
381            self.assertEqual(n, 2**(k-1))
382
383            n += n - 1      # check 1 below the next power of two
384            k = int(1.00001 + _log(n, 2))
385            self.assertIn(k, [numbits, numbits+1])
386            self.assertTrue(2**k > n > 2**(k-2))
387
388            n -= n >> 15     # check a little farther below the next power of two
389            k = int(1.00001 + _log(n, 2))
390            self.assertEqual(k, numbits)        # note the stronger assertion
391            self.assertTrue(2**k > n > 2**(k-1))   # note the stronger assertion
392
393
394class MersenneTwister_TestBasicOps(TestBasicOps, unittest.TestCase):
395    gen = random.Random()
396
397    def test_guaranteed_stable(self):
398        # These sequences are guaranteed to stay the same across versions of python
399        self.gen.seed(3456147, version=1)
400        self.assertEqual([self.gen.random().hex() for i in range(4)],
401            ['0x1.ac362300d90d2p-1', '0x1.9d16f74365005p-1',
402             '0x1.1ebb4352e4c4dp-1', '0x1.1a7422abf9c11p-1'])
403        self.gen.seed("the quick brown fox", version=2)
404        self.assertEqual([self.gen.random().hex() for i in range(4)],
405            ['0x1.1239ddfb11b7cp-3', '0x1.b3cbb5c51b120p-4',
406             '0x1.8c4f55116b60fp-1', '0x1.63eb525174a27p-1'])
407
408    def test_bug_27706(self):
409        # Verify that version 1 seeds are unaffected by hash randomization
410
411        self.gen.seed('nofar', version=1)   # hash('nofar') == 5990528763808513177
412        self.assertEqual([self.gen.random().hex() for i in range(4)],
413            ['0x1.8645314505ad7p-1', '0x1.afb1f82e40a40p-5',
414             '0x1.2a59d2285e971p-1', '0x1.56977142a7880p-6'])
415
416        self.gen.seed('rachel', version=1)  # hash('rachel') == -9091735575445484789
417        self.assertEqual([self.gen.random().hex() for i in range(4)],
418            ['0x1.0b294cc856fcdp-1', '0x1.2ad22d79e77b8p-3',
419             '0x1.3052b9c072678p-2', '0x1.578f332106574p-3'])
420
421        self.gen.seed('', version=1)        # hash('') == 0
422        self.assertEqual([self.gen.random().hex() for i in range(4)],
423            ['0x1.b0580f98a7dbep-1', '0x1.84129978f9c1ap-1',
424             '0x1.aeaa51052e978p-2', '0x1.092178fb945a6p-2'])
425
426    def test_setstate_first_arg(self):
427        self.assertRaises(ValueError, self.gen.setstate, (1, None, None))
428
429    def test_setstate_middle_arg(self):
430        # Wrong type, s/b tuple
431        self.assertRaises(TypeError, self.gen.setstate, (2, None, None))
432        # Wrong length, s/b 625
433        self.assertRaises(ValueError, self.gen.setstate, (2, (1,2,3), None))
434        # Wrong type, s/b tuple of 625 ints
435        self.assertRaises(TypeError, self.gen.setstate, (2, ('a',)*625, None))
436        # Last element s/b an int also
437        self.assertRaises(TypeError, self.gen.setstate, (2, (0,)*624+('a',), None))
438        # Last element s/b between 0 and 624
439        with self.assertRaises((ValueError, OverflowError)):
440            self.gen.setstate((2, (1,)*624+(625,), None))
441        with self.assertRaises((ValueError, OverflowError)):
442            self.gen.setstate((2, (1,)*624+(-1,), None))
443
444        # Little trick to make "tuple(x % (2**32) for x in internalstate)"
445        # raise ValueError. I cannot think of a simple way to achieve this, so
446        # I am opting for using a generator as the middle argument of setstate
447        # which attempts to cast a NaN to integer.
448        state_values = self.gen.getstate()[1]
449        state_values = list(state_values)
450        state_values[-1] = float('nan')
451        state = (int(x) for x in state_values)
452        self.assertRaises(TypeError, self.gen.setstate, (2, state, None))
453
454    def test_referenceImplementation(self):
455        # Compare the python implementation with results from the original
456        # code.  Create 2000 53-bit precision random floats.  Compare only
457        # the last ten entries to show that the independent implementations
458        # are tracking.  Here is the main() function needed to create the
459        # list of expected random numbers:
460        #    void main(void){
461        #         int i;
462        #         unsigned long init[4]={61731, 24903, 614, 42143}, length=4;
463        #         init_by_array(init, length);
464        #         for (i=0; i<2000; i++) {
465        #           printf("%.15f ", genrand_res53());
466        #           if (i%5==4) printf("\n");
467        #         }
468        #     }
469        expected = [0.45839803073713259,
470                    0.86057815201978782,
471                    0.92848331726782152,
472                    0.35932681119782461,
473                    0.081823493762449573,
474                    0.14332226470169329,
475                    0.084297823823520024,
476                    0.53814864671831453,
477                    0.089215024911993401,
478                    0.78486196105372907]
479
480        self.gen.seed(61731 + (24903<<32) + (614<<64) + (42143<<96))
481        actual = self.randomlist(2000)[-10:]
482        for a, e in zip(actual, expected):
483            self.assertAlmostEqual(a,e,places=14)
484
485    def test_strong_reference_implementation(self):
486        # Like test_referenceImplementation, but checks for exact bit-level
487        # equality.  This should pass on any box where C double contains
488        # at least 53 bits of precision (the underlying algorithm suffers
489        # no rounding errors -- all results are exact).
490        from math import ldexp
491
492        expected = [0x0eab3258d2231f,
493                    0x1b89db315277a5,
494                    0x1db622a5518016,
495                    0x0b7f9af0d575bf,
496                    0x029e4c4db82240,
497                    0x04961892f5d673,
498                    0x02b291598e4589,
499                    0x11388382c15694,
500                    0x02dad977c9e1fe,
501                    0x191d96d4d334c6]
502        self.gen.seed(61731 + (24903<<32) + (614<<64) + (42143<<96))
503        actual = self.randomlist(2000)[-10:]
504        for a, e in zip(actual, expected):
505            self.assertEqual(int(ldexp(a, 53)), e)
506
507    def test_long_seed(self):
508        # This is most interesting to run in debug mode, just to make sure
509        # nothing blows up.  Under the covers, a dynamically resized array
510        # is allocated, consuming space proportional to the number of bits
511        # in the seed.  Unfortunately, that's a quadratic-time algorithm,
512        # so don't make this horribly big.
513        seed = (1 << (10000 * 8)) - 1  # about 10K bytes
514        self.gen.seed(seed)
515
516    def test_53_bits_per_float(self):
517        # This should pass whenever a C double has 53 bit precision.
518        span = 2 ** 53
519        cum = 0
520        for i in range(100):
521            cum |= int(self.gen.random() * span)
522        self.assertEqual(cum, span-1)
523
524    def test_bigrand(self):
525        # The randrange routine should build-up the required number of bits
526        # in stages so that all bit positions are active.
527        span = 2 ** 500
528        cum = 0
529        for i in range(100):
530            r = self.gen.randrange(span)
531            self.assertTrue(0 <= r < span)
532            cum |= r
533        self.assertEqual(cum, span-1)
534
535    def test_bigrand_ranges(self):
536        for i in [40,80, 160, 200, 211, 250, 375, 512, 550]:
537            start = self.gen.randrange(2 ** (i-2))
538            stop = self.gen.randrange(2 ** i)
539            if stop <= start:
540                continue
541            self.assertTrue(start <= self.gen.randrange(start, stop) < stop)
542
543    def test_rangelimits(self):
544        for start, stop in [(-2,0), (-(2**60)-2,-(2**60)), (2**60,2**60+2)]:
545            self.assertEqual(set(range(start,stop)),
546                set([self.gen.randrange(start,stop) for i in range(100)]))
547
548    def test_genrandbits(self):
549        # Verify cross-platform repeatability
550        self.gen.seed(1234567)
551        self.assertEqual(self.gen.getrandbits(100),
552                         97904845777343510404718956115)
553        # Verify ranges
554        for k in range(1, 1000):
555            self.assertTrue(0 <= self.gen.getrandbits(k) < 2**k)
556
557        # Verify all bits active
558        getbits = self.gen.getrandbits
559        for span in [1, 2, 3, 4, 31, 32, 32, 52, 53, 54, 119, 127, 128, 129]:
560            cum = 0
561            for i in range(100):
562                cum |= getbits(span)
563            self.assertEqual(cum, 2**span-1)
564
565        # Verify argument checking
566        self.assertRaises(TypeError, self.gen.getrandbits)
567        self.assertRaises(TypeError, self.gen.getrandbits, 'a')
568        self.assertRaises(TypeError, self.gen.getrandbits, 1, 2)
569        self.assertRaises(ValueError, self.gen.getrandbits, 0)
570        self.assertRaises(ValueError, self.gen.getrandbits, -1)
571
572    def test_randbelow_logic(self, _log=log, int=int):
573        # check bitcount transition points:  2**i and 2**(i+1)-1
574        # show that: k = int(1.001 + _log(n, 2))
575        # is equal to or one greater than the number of bits in n
576        for i in range(1, 1000):
577            n = 1 << i # check an exact power of two
578            numbits = i+1
579            k = int(1.00001 + _log(n, 2))
580            self.assertEqual(k, numbits)
581            self.assertEqual(n, 2**(k-1))
582
583            n += n - 1      # check 1 below the next power of two
584            k = int(1.00001 + _log(n, 2))
585            self.assertIn(k, [numbits, numbits+1])
586            self.assertTrue(2**k > n > 2**(k-2))
587
588            n -= n >> 15     # check a little farther below the next power of two
589            k = int(1.00001 + _log(n, 2))
590            self.assertEqual(k, numbits)        # note the stronger assertion
591            self.assertTrue(2**k > n > 2**(k-1))   # note the stronger assertion
592
593    @unittest.mock.patch('random.Random.random')
594    def test_randbelow_overridden_random(self, random_mock):
595        # Random._randbelow() can only use random() when the built-in one
596        # has been overridden but no new getrandbits() method was supplied.
597        random_mock.side_effect = random.SystemRandom().random
598        maxsize = 1<<random.BPF
599        with warnings.catch_warnings():
600            warnings.simplefilter("ignore", UserWarning)
601            # Population range too large (n >= maxsize)
602            self.gen._randbelow(maxsize+1, maxsize = maxsize)
603        self.gen._randbelow(5640, maxsize = maxsize)
604
605        # This might be going too far to test a single line, but because of our
606        # noble aim of achieving 100% test coverage we need to write a case in
607        # which the following line in Random._randbelow() gets executed:
608        #
609        # rem = maxsize % n
610        # limit = (maxsize - rem) / maxsize
611        # r = random()
612        # while r >= limit:
613        #     r = random() # <== *This line* <==<
614        #
615        # Therefore, to guarantee that the while loop is executed at least
616        # once, we need to mock random() so that it returns a number greater
617        # than 'limit' the first time it gets called.
618
619        n = 42
620        epsilon = 0.01
621        limit = (maxsize - (maxsize % n)) / maxsize
622        random_mock.side_effect = [limit + epsilon, limit - epsilon]
623        self.gen._randbelow(n, maxsize = maxsize)
624
625    def test_randrange_bug_1590891(self):
626        start = 1000000000000
627        stop = -100000000000000000000
628        step = -200
629        x = self.gen.randrange(start, stop, step)
630        self.assertTrue(stop < x <= start)
631        self.assertEqual((x+stop)%step, 0)
632
633    def test_choices_algorithms(self):
634        # The various ways of specifying weights should produce the same results
635        choices = self.gen.choices
636        n = 104729
637
638        self.gen.seed(8675309)
639        a = self.gen.choices(range(n), k=10000)
640
641        self.gen.seed(8675309)
642        b = self.gen.choices(range(n), [1]*n, k=10000)
643        self.assertEqual(a, b)
644
645        self.gen.seed(8675309)
646        c = self.gen.choices(range(n), cum_weights=range(1, n+1), k=10000)
647        self.assertEqual(a, c)
648
649        # Amerian Roulette
650        population = ['Red', 'Black', 'Green']
651        weights = [18, 18, 2]
652        cum_weights = [18, 36, 38]
653        expanded_population = ['Red'] * 18 + ['Black'] * 18 + ['Green'] * 2
654
655        self.gen.seed(9035768)
656        a = self.gen.choices(expanded_population, k=10000)
657
658        self.gen.seed(9035768)
659        b = self.gen.choices(population, weights, k=10000)
660        self.assertEqual(a, b)
661
662        self.gen.seed(9035768)
663        c = self.gen.choices(population, cum_weights=cum_weights, k=10000)
664        self.assertEqual(a, c)
665
666def gamma(z, sqrt2pi=(2.0*pi)**0.5):
667    # Reflection to right half of complex plane
668    if z < 0.5:
669        return pi / sin(pi*z) / gamma(1.0-z)
670    # Lanczos approximation with g=7
671    az = z + (7.0 - 0.5)
672    return az ** (z-0.5) / exp(az) * sqrt2pi * fsum([
673        0.9999999999995183,
674        676.5203681218835 / z,
675        -1259.139216722289 / (z+1.0),
676        771.3234287757674 / (z+2.0),
677        -176.6150291498386 / (z+3.0),
678        12.50734324009056 / (z+4.0),
679        -0.1385710331296526 / (z+5.0),
680        0.9934937113930748e-05 / (z+6.0),
681        0.1659470187408462e-06 / (z+7.0),
682    ])
683
684class TestDistributions(unittest.TestCase):
685    def test_zeroinputs(self):
686        # Verify that distributions can handle a series of zero inputs'
687        g = random.Random()
688        x = [g.random() for i in range(50)] + [0.0]*5
689        g.random = x[:].pop; g.uniform(1,10)
690        g.random = x[:].pop; g.paretovariate(1.0)
691        g.random = x[:].pop; g.expovariate(1.0)
692        g.random = x[:].pop; g.weibullvariate(1.0, 1.0)
693        g.random = x[:].pop; g.vonmisesvariate(1.0, 1.0)
694        g.random = x[:].pop; g.normalvariate(0.0, 1.0)
695        g.random = x[:].pop; g.gauss(0.0, 1.0)
696        g.random = x[:].pop; g.lognormvariate(0.0, 1.0)
697        g.random = x[:].pop; g.vonmisesvariate(0.0, 1.0)
698        g.random = x[:].pop; g.gammavariate(0.01, 1.0)
699        g.random = x[:].pop; g.gammavariate(1.0, 1.0)
700        g.random = x[:].pop; g.gammavariate(200.0, 1.0)
701        g.random = x[:].pop; g.betavariate(3.0, 3.0)
702        g.random = x[:].pop; g.triangular(0.0, 1.0, 1.0/3.0)
703
704    def test_avg_std(self):
705        # Use integration to test distribution average and standard deviation.
706        # Only works for distributions which do not consume variates in pairs
707        g = random.Random()
708        N = 5000
709        x = [i/float(N) for i in range(1,N)]
710        for variate, args, mu, sigmasqrd in [
711                (g.uniform, (1.0,10.0), (10.0+1.0)/2, (10.0-1.0)**2/12),
712                (g.triangular, (0.0, 1.0, 1.0/3.0), 4.0/9.0, 7.0/9.0/18.0),
713                (g.expovariate, (1.5,), 1/1.5, 1/1.5**2),
714                (g.vonmisesvariate, (1.23, 0), pi, pi**2/3),
715                (g.paretovariate, (5.0,), 5.0/(5.0-1),
716                                  5.0/((5.0-1)**2*(5.0-2))),
717                (g.weibullvariate, (1.0, 3.0), gamma(1+1/3.0),
718                                  gamma(1+2/3.0)-gamma(1+1/3.0)**2) ]:
719            g.random = x[:].pop
720            y = []
721            for i in range(len(x)):
722                try:
723                    y.append(variate(*args))
724                except IndexError:
725                    pass
726            s1 = s2 = 0
727            for e in y:
728                s1 += e
729                s2 += (e - mu) ** 2
730            N = len(y)
731            self.assertAlmostEqual(s1/N, mu, places=2,
732                                   msg='%s%r' % (variate.__name__, args))
733            self.assertAlmostEqual(s2/(N-1), sigmasqrd, places=2,
734                                   msg='%s%r' % (variate.__name__, args))
735
736    def test_constant(self):
737        g = random.Random()
738        N = 100
739        for variate, args, expected in [
740                (g.uniform, (10.0, 10.0), 10.0),
741                (g.triangular, (10.0, 10.0), 10.0),
742                (g.triangular, (10.0, 10.0, 10.0), 10.0),
743                (g.expovariate, (float('inf'),), 0.0),
744                (g.vonmisesvariate, (3.0, float('inf')), 3.0),
745                (g.gauss, (10.0, 0.0), 10.0),
746                (g.lognormvariate, (0.0, 0.0), 1.0),
747                (g.lognormvariate, (-float('inf'), 0.0), 0.0),
748                (g.normalvariate, (10.0, 0.0), 10.0),
749                (g.paretovariate, (float('inf'),), 1.0),
750                (g.weibullvariate, (10.0, float('inf')), 10.0),
751                (g.weibullvariate, (0.0, 10.0), 0.0),
752            ]:
753            for i in range(N):
754                self.assertEqual(variate(*args), expected)
755
756    def test_von_mises_range(self):
757        # Issue 17149: von mises variates were not consistently in the
758        # range [0, 2*PI].
759        g = random.Random()
760        N = 100
761        for mu in 0.0, 0.1, 3.1, 6.2:
762            for kappa in 0.0, 2.3, 500.0:
763                for _ in range(N):
764                    sample = g.vonmisesvariate(mu, kappa)
765                    self.assertTrue(
766                        0 <= sample <= random.TWOPI,
767                        msg=("vonmisesvariate({}, {}) produced a result {} out"
768                             " of range [0, 2*pi]").format(mu, kappa, sample))
769
770    def test_von_mises_large_kappa(self):
771        # Issue #17141: vonmisesvariate() was hang for large kappas
772        random.vonmisesvariate(0, 1e15)
773        random.vonmisesvariate(0, 1e100)
774
775    def test_gammavariate_errors(self):
776        # Both alpha and beta must be > 0.0
777        self.assertRaises(ValueError, random.gammavariate, -1, 3)
778        self.assertRaises(ValueError, random.gammavariate, 0, 2)
779        self.assertRaises(ValueError, random.gammavariate, 2, 0)
780        self.assertRaises(ValueError, random.gammavariate, 1, -3)
781
782    @unittest.mock.patch('random.Random.random')
783    def test_gammavariate_full_code_coverage(self, random_mock):
784        # There are three different possibilities in the current implementation
785        # of random.gammavariate(), depending on the value of 'alpha'. What we
786        # are going to do here is to fix the values returned by random() to
787        # generate test cases that provide 100% line coverage of the method.
788
789        # #1: alpha > 1.0: we want the first random number to be outside the
790        # [1e-7, .9999999] range, so that the continue statement executes
791        # once. The values of u1 and u2 will be 0.5 and 0.3, respectively.
792        random_mock.side_effect = [1e-8, 0.5, 0.3]
793        returned_value = random.gammavariate(1.1, 2.3)
794        self.assertAlmostEqual(returned_value, 2.53)
795
796        # #2: alpha == 1: first random number less than 1e-7 to that the body
797        # of the while loop executes once. Then random.random() returns 0.45,
798        # which causes while to stop looping and the algorithm to terminate.
799        random_mock.side_effect = [1e-8, 0.45]
800        returned_value = random.gammavariate(1.0, 3.14)
801        self.assertAlmostEqual(returned_value, 2.507314166123803)
802
803        # #3: 0 < alpha < 1. This is the most complex region of code to cover,
804        # as there are multiple if-else statements. Let's take a look at the
805        # source code, and determine the values that we need accordingly:
806        #
807        # while 1:
808        #     u = random()
809        #     b = (_e + alpha)/_e
810        #     p = b*u
811        #     if p <= 1.0: # <=== (A)
812        #         x = p ** (1.0/alpha)
813        #     else: # <=== (B)
814        #         x = -_log((b-p)/alpha)
815        #     u1 = random()
816        #     if p > 1.0: # <=== (C)
817        #         if u1 <= x ** (alpha - 1.0): # <=== (D)
818        #             break
819        #     elif u1 <= _exp(-x): # <=== (E)
820        #         break
821        # return x * beta
822        #
823        # First, we want (A) to be True. For that we need that:
824        # b*random() <= 1.0
825        # r1 = random() <= 1.0 / b
826        #
827        # We now get to the second if-else branch, and here, since p <= 1.0,
828        # (C) is False and we take the elif branch, (E). For it to be True,
829        # so that the break is executed, we need that:
830        # r2 = random() <= _exp(-x)
831        # r2 <= _exp(-(p ** (1.0/alpha)))
832        # r2 <= _exp(-((b*r1) ** (1.0/alpha)))
833
834        _e = random._e
835        _exp = random._exp
836        _log = random._log
837        alpha = 0.35
838        beta = 1.45
839        b = (_e + alpha)/_e
840        epsilon = 0.01
841
842        r1 = 0.8859296441566 # 1.0 / b
843        r2 = 0.3678794411714 # _exp(-((b*r1) ** (1.0/alpha)))
844
845        # These four "random" values result in the following trace:
846        # (A) True, (E) False --> [next iteration of while]
847        # (A) True, (E) True --> [while loop breaks]
848        random_mock.side_effect = [r1, r2 + epsilon, r1, r2]
849        returned_value = random.gammavariate(alpha, beta)
850        self.assertAlmostEqual(returned_value, 1.4499999999997544)
851
852        # Let's now make (A) be False. If this is the case, when we get to the
853        # second if-else 'p' is greater than 1, so (C) evaluates to True. We
854        # now encounter a second if statement, (D), which in order to execute
855        # must satisfy the following condition:
856        # r2 <= x ** (alpha - 1.0)
857        # r2 <= (-_log((b-p)/alpha)) ** (alpha - 1.0)
858        # r2 <= (-_log((b-(b*r1))/alpha)) ** (alpha - 1.0)
859        r1 = 0.8959296441566 # (1.0 / b) + epsilon -- so that (A) is False
860        r2 = 0.9445400408898141
861
862        # And these four values result in the following trace:
863        # (B) and (C) True, (D) False --> [next iteration of while]
864        # (B) and (C) True, (D) True [while loop breaks]
865        random_mock.side_effect = [r1, r2 + epsilon, r1, r2]
866        returned_value = random.gammavariate(alpha, beta)
867        self.assertAlmostEqual(returned_value, 1.5830349561760781)
868
869    @unittest.mock.patch('random.Random.gammavariate')
870    def test_betavariate_return_zero(self, gammavariate_mock):
871        # betavariate() returns zero when the Gamma distribution
872        # that it uses internally returns this same value.
873        gammavariate_mock.return_value = 0.0
874        self.assertEqual(0.0, random.betavariate(2.71828, 3.14159))
875
876class TestModule(unittest.TestCase):
877    def testMagicConstants(self):
878        self.assertAlmostEqual(random.NV_MAGICCONST, 1.71552776992141)
879        self.assertAlmostEqual(random.TWOPI, 6.28318530718)
880        self.assertAlmostEqual(random.LOG4, 1.38629436111989)
881        self.assertAlmostEqual(random.SG_MAGICCONST, 2.50407739677627)
882
883    def test__all__(self):
884        # tests validity but not completeness of the __all__ list
885        self.assertTrue(set(random.__all__) <= set(dir(random)))
886
887    def test_random_subclass_with_kwargs(self):
888        # SF bug #1486663 -- this used to erroneously raise a TypeError
889        class Subclass(random.Random):
890            def __init__(self, newarg=None):
891                random.Random.__init__(self)
892        Subclass(newarg=1)
893
894
895if __name__ == "__main__":
896    unittest.main()
897