random.py revision bbc50eafe5cc7d2fa73b5b45eebc573c600db9ac
1e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum"""Random variable generators.
2e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum
3d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    integers
4d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    --------
5d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters           uniform within range
6d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
7d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    sequences
8d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    ---------
9d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters           pick random element
10f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger           pick random sample
11d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters           generate random permutation
12d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
13e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum    distributions on the real line:
14e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum    ------------------------------
15d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters           uniform
16bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger           triangular
17e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           normal (Gaussian)
18e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           lognormal
19e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           negative exponential
20e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           gamma
21e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           beta
2240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger           pareto
2340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger           Weibull
24e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum
25e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum    distributions on the circle (angles 0 to 2pi)
26e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum    ---------------------------------------------
27e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           circular uniform
28e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum           von Mises
29e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum
3040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond HettingerGeneral notes on the underlying Mersenne Twister core generator:
3140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
3240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger* The period is 2**19937-1.
330e1159583c06fdf85d7d2dbe8b82e42565b9d166Tim Peters* It is one of the most extensively tested generators in existence.
340e1159583c06fdf85d7d2dbe8b82e42565b9d166Tim Peters* Without a direct way to compute N steps forward, the semantics of
350e1159583c06fdf85d7d2dbe8b82e42565b9d166Tim Peters  jumpahead(n) are weakened to simply jump to another distant state and rely
360e1159583c06fdf85d7d2dbe8b82e42565b9d166Tim Peters  on the large period to avoid overlapping sequences.
370e1159583c06fdf85d7d2dbe8b82e42565b9d166Tim Peters* The random() method is implemented in C, executes in a single Python step,
380e1159583c06fdf85d7d2dbe8b82e42565b9d166Tim Peters  and is, therefore, threadsafe.
3940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
40e7b146fb3bdca62a0d5ecc06dbf3348e5a4fe757Guido van Rossum"""
41d03e1197cb5052e3f758794e2a7aecf9f5ca5f46Guido van Rossum
422f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettingerfrom warnings import warn as _warn
432f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettingerfrom types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
4491e27c253c8bb8b6ae8521f1dbb76de7c66ad8cfRaymond Hettingerfrom math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil
45d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersfrom math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
46c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettingerfrom os import urandom as _urandom
47c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettingerfrom binascii import hexlify as _hexlify
48d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
49f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger__all__ = ["Random","seed","random","uniform","randint","choice","sample",
500de65807e6bdc5254f5a7e99b2f39adeea6b883bSkip Montanaro           "randrange","shuffle","normalvariate","lognormvariate",
51bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger           "expovariate","vonmisesvariate","gammavariate","triangular",
52f8a52d38ad784b34a60720cb148180d6eb6de373Raymond Hettinger           "gauss","betavariate","paretovariate","weibullvariate",
53356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger           "getstate","setstate","jumpahead", "WichmannHill", "getrandbits",
5423f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger           "SystemRandom"]
55ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
56d7b5e88e8e40b77813ceb25dc28b87d672538403Tim PetersNV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
57d7b5e88e8e40b77813ceb25dc28b87d672538403Tim PetersTWOPI = 2.0*_pi
58d7b5e88e8e40b77813ceb25dc28b87d672538403Tim PetersLOG4 = _log(4.0)
59d7b5e88e8e40b77813ceb25dc28b87d672538403Tim PetersSG_MAGICCONST = 1.0 + _log(4.5)
602f726e9093381572b21edbfc42659ea89fbdf686Raymond HettingerBPF = 53        # Number of bits in a float
617c2a85b2d44851c2442ade579b760f86447bf848Tim PetersRECIP_BPF = 2**-BPF
6233d7f1a76c3544d2901492cfb6fc9db85f2dfbd6Guido van Rossum
63356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
64d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters# Translated by Guido van Rossum from C source provided by
6540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger# Adrian Baddeley.  Adapted by Raymond Hettinger for use with
663fa19d7ff89be87139e2864fb9186b424d180a58Raymond Hettinger# the Mersenne Twister  and os.urandom() core generators.
6733d7f1a76c3544d2901492cfb6fc9db85f2dfbd6Guido van Rossum
68145a4a0f10009f7ce2644465ccd359938b034ac4Raymond Hettingerimport _random
6940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
70145a4a0f10009f7ce2644465ccd359938b034ac4Raymond Hettingerclass Random(_random.Random):
71c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    """Random number generator base class used by bound module functions.
72c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
73c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    Used to instantiate instances of Random to get generators that don't
74c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    share state.  Especially useful for multi-threaded programs, creating
75c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    a different instance of Random for each thread, and using the jumpahead()
76c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    method to ensure that the generated sequences seen by each thread don't
77c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    overlap.
78c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
79c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    Class Random can also be subclassed if you want to use a different basic
80c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    generator of your own devising: in that case, override the following
81c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    methods:  random(), seed(), getstate(), setstate() and jumpahead().
822f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger    Optionally, implement a getrandombits() method so that randrange()
832f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger    can cover arbitrarily large ranges.
84ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
85c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger    """
8633d7f1a76c3544d2901492cfb6fc9db85f2dfbd6Guido van Rossum
876b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis    VERSION = 3     # used by getstate/setstate
8833d7f1a76c3544d2901492cfb6fc9db85f2dfbd6Guido van Rossum
89d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def __init__(self, x=None):
90d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """Initialize an instance.
9133d7f1a76c3544d2901492cfb6fc9db85f2dfbd6Guido van Rossum
92d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        Optional argument x controls seeding, as for Random.seed().
93d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """
9433d7f1a76c3544d2901492cfb6fc9db85f2dfbd6Guido van Rossum
95d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        self.seed(x)
9640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self.gauss_next = None
97ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
980de88fc4b108751b86443852b6741680d704168fTim Peters    def seed(self, a=None):
990de88fc4b108751b86443852b6741680d704168fTim Peters        """Initialize internal state from hashable object.
100d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
10123f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        None or no argument seeds from current time or from an operating
10223f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        system specific randomness source if available.
1030de88fc4b108751b86443852b6741680d704168fTim Peters
104bcd725fc456faca13f4598f87c0517f917711cdaTim Peters        If a is not None or an int or long, hash(a) is used instead.
105d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """
106d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
1073081d59f920229b26293c7a3ee3f1a9da0da53e9Raymond Hettinger        if a is None:
108c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettinger            try:
109c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettinger                a = long(_hexlify(_urandom(16)), 16)
110c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettinger            except NotImplementedError:
111356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger                import time
112356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger                a = long(time.time() * 256) # use fractional seconds
113356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
114145a4a0f10009f7ce2644465ccd359938b034ac4Raymond Hettinger        super(Random, self).seed(a)
11546c04e140cf26d1b44935c28c6f15ea467400d22Tim Peters        self.gauss_next = None
11646c04e140cf26d1b44935c28c6f15ea467400d22Tim Peters
117d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def getstate(self):
118d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """Return internal state; can be passed to setstate() later."""
119145a4a0f10009f7ce2644465ccd359938b034ac4Raymond Hettinger        return self.VERSION, super(Random, self).getstate(), self.gauss_next
120d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
121d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def setstate(self, state):
122d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """Restore internal state from object returned by getstate()."""
123d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        version = state[0]
1246b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis        if version == 3:
12540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            version, internalstate, self.gauss_next = state
126145a4a0f10009f7ce2644465ccd359938b034ac4Raymond Hettinger            super(Random, self).setstate(internalstate)
1276b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis        elif version == 2:
1286b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            version, internalstate, self.gauss_next = state
1296b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            # In version 2, the state was saved as signed ints, which causes
1306b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            #   inconsistencies between 32/64-bit systems. The state is
1316b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            #   really unsigned 32-bit ints, so we convert negative ints from
1326b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            #   version 2 to positive longs for version 3.
1336b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            try:
1346b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis                internalstate = tuple( long(x) % (2**32) for x in internalstate )
1356b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            except ValueError, e:
1366b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis                raise TypeError, e
1376b449f4f2bd86c104a8b57547428eb9bb3a182b0Martin v. Löwis            super(Random, self).setstate(internalstate)
138d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        else:
139d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError("state with version %s passed to "
140d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                             "Random.setstate() of version %s" %
141d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                             (version, self.VERSION))
142d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
143cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## ---- Methods below this point do not need to be overridden when
144cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## ---- subclassing for the purpose of using a different core generator.
145d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
146cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- pickle support  -------------------
147d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
148cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters    def __getstate__(self): # for pickle
149cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters        return self.getstate()
150d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
151cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters    def __setstate__(self, state):  # for pickle
152cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters        self.setstate(state)
153cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters
1545f078ff7f0c6bb5086fae077379fc79729c34d2dRaymond Hettinger    def __reduce__(self):
1555f078ff7f0c6bb5086fae077379fc79729c34d2dRaymond Hettinger        return self.__class__, (), self.getstate()
1565f078ff7f0c6bb5086fae077379fc79729c34d2dRaymond Hettinger
157cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- integer methods  -------------------
158d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
1592f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger    def randrange(self, start, stop=None, step=1, int=int, default=None,
1602f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                  maxwidth=1L<<BPF):
161d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """Choose a random item from range(start, stop[, step]).
162d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
163d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        This fixes the problem with randint() which includes the
164d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        endpoint; in Python this is usually not what you want.
1652f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        Do not supply the 'int', 'default', and 'maxwidth' arguments.
166d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """
167d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
168d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # This code is a bit messy to make it fast for the
1699146f27b7799dab231083f194a14c6157b57549fTim Peters        # common case while still doing adequate error checking.
170d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        istart = int(start)
171d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if istart != start:
172d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError, "non-integer arg 1 for randrange()"
173d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if stop is default:
174d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            if istart > 0:
1752f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                if istart >= maxwidth:
1762f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                    return self._randbelow(istart)
177d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                return int(self.random() * istart)
178d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError, "empty range for randrange()"
1799146f27b7799dab231083f194a14c6157b57549fTim Peters
1809146f27b7799dab231083f194a14c6157b57549fTim Peters        # stop argument supplied.
181d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        istop = int(stop)
182d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if istop != stop:
183d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError, "non-integer stop for randrange()"
1842f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        width = istop - istart
1852f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        if step == 1 and width > 0:
18676ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # Note that
1872f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            #     int(istart + self.random()*width)
18876ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # instead would be incorrect.  For example, consider istart
18976ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # = -2 and istop = 0.  Then the guts would be in
19076ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # -2.0 to 0.0 exclusive on both ends (ignoring that random()
19176ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # might return 0.0), and because int() truncates toward 0, the
19276ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # final result would be -1 or 0 (instead of -2 or -1).
1932f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            #     istart + int(self.random()*width)
19476ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # would also be incorrect, for a subtler reason:  the RHS
19576ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # can return a long, and then randrange() would also return
19676ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # a long, but we're supposed to return an int (for backward
19776ca1d428f96284ed58f4523b698ed95c6fdbdb2Tim Peters            # compatibility).
1982f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger
1992f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            if width >= maxwidth:
20058eb11cf62dd04ccc2c364b62fd51b4265e2e203Tim Peters                return int(istart + self._randbelow(width))
2012f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            return int(istart + int(self.random()*width))
202d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if step == 1:
2032f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            raise ValueError, "empty range for randrange() (%d,%d, %d)" % (istart, istop, width)
2049146f27b7799dab231083f194a14c6157b57549fTim Peters
2059146f27b7799dab231083f194a14c6157b57549fTim Peters        # Non-unit step argument supplied.
206d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        istep = int(step)
207d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if istep != step:
208d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError, "non-integer step for randrange()"
209d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if istep > 0:
210ffdb8bb99c4017152a9dca70669f9d6b9831d454Raymond Hettinger            n = (width + istep - 1) // istep
211d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        elif istep < 0:
212ffdb8bb99c4017152a9dca70669f9d6b9831d454Raymond Hettinger            n = (width + istep + 1) // istep
213d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        else:
214d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError, "zero step for randrange()"
215d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
216d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if n <= 0:
217d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            raise ValueError, "empty range for randrange()"
2182f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger
2192f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        if n >= maxwidth:
22094547f7646895e032f8fc145529d9efc3a70760dRaymond Hettinger            return istart + istep*self._randbelow(n)
221d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return istart + istep*int(self.random() * n)
222d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
223d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def randint(self, a, b):
224cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters        """Return random integer in range [a, b], including both end points.
225d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """
226d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
227d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return self.randrange(a, b+1)
228d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
2292f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger    def _randbelow(self, n, _log=_log, int=int, _maxwidth=1L<<BPF,
2302f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                   _Method=_MethodType, _BuiltinMethod=_BuiltinMethodType):
2312f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        """Return a random int in the range [0,n)
2322f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger
2332f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        Handles the case where n has more bits than returned
2342f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        by a single call to the underlying generator.
2352f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        """
2362f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger
2372f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        try:
2382f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            getrandbits = self.getrandbits
2392f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        except AttributeError:
2402f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            pass
2412f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        else:
2422f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            # Only call self.getrandbits if the original random() builtin method
2432f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            # has not been overridden or if a new getrandbits() was supplied.
2442f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            # This assures that the two methods correspond.
2452f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            if type(self.random) is _BuiltinMethod or type(getrandbits) is _Method:
2462f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                k = int(1.00001 + _log(n-1, 2.0))   # 2**k > n-1 > 2**(k-2)
2472f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                r = getrandbits(k)
2482f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                while r >= n:
2492f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                    r = getrandbits(k)
2502f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                return r
2512f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        if n >= _maxwidth:
2522f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger            _warn("Underlying random() generator does not supply \n"
2532f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger                "enough bits to choose from a population range this large")
2542f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger        return int(self.random() * n)
2552f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettinger
256cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- sequence methods  -------------------
257cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters
258d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def choice(self, seq):
259d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """Choose a random element from a non-empty sequence."""
2605dae505bbd59641a948c81bea981e7c44d4c2343Raymond Hettinger        return seq[int(self.random() * len(seq))]  # raises IndexError if seq is empty
261d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
262d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def shuffle(self, x, random=None, int=int):
263d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """x, random=random.random -> shuffle list x in place; return None.
264d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
265d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        Optional arg random is a 0-argument function returning a random
266d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        float in [0.0, 1.0); by default, the standard random.random.
267d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """
268d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
269d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if random is None:
270d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            random = self.random
27185c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettinger        for i in reversed(xrange(1, len(x))):
272cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters            # pick an element in x[:i+1] with which to exchange x[i]
273d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            j = int(random() * (i+1))
274d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            x[i], x[j] = x[j], x[i]
275d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
276fdbe5223b7402ee34c4f0c06caa6faabd9e73e35Raymond Hettinger    def sample(self, population, k):
277f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger        """Chooses k unique random elements from a population sequence.
278f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger
279c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        Returns a new list containing elements from the population while
280c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        leaving the original population unchanged.  The resulting list is
281c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        in selection order so that all sub-slices will also be valid random
282c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        samples.  This allows raffle winners (the sample) to be partitioned
283c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        into grand prize and second place winners (the subslices).
284f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger
285c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        Members of the population need not be hashable or unique.  If the
286c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        population contains repeats, then each occurrence is a possible
287c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        selection in the sample.
288f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger
289c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        To choose a sample in a range of integers, use xrange as an argument.
290c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        This is especially fast and space efficient for sampling from a
291c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        large population:   sample(xrange(10000000), 60)
292f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger        """
293f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger
294c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX Although the documentation says `population` is "a sequence",
295c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX attempts are made to cater to any iterable with a __len__
296c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX method.  This has had mixed success.  Examples from both
297c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX sides:  sets work fine, and should become officially supported;
298c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX dicts are much harder, and have failed in various subtle
299c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX ways across attempts.  Support for mapping types should probably
300c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX be dropped (and users should pass mapping.keys() or .values()
301c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        # XXX explicitly).
302c17976e9833f3093adb1019356737e728a24f7c9Tim Peters
303c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        # Sampling without replacement entails tracking either potential
30491e27c253c8bb8b6ae8521f1dbb76de7c66ad8cfRaymond Hettinger        # selections (the pool) in a list or previous selections in a set.
305c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger
3062b55d35850e3e8e0b28aba7878d3f9122a7907acJeremy Hylton        # When the number of selections is small compared to the
3072b55d35850e3e8e0b28aba7878d3f9122a7907acJeremy Hylton        # population, then tracking selections is efficient, requiring
30891e27c253c8bb8b6ae8521f1dbb76de7c66ad8cfRaymond Hettinger        # only a small set and an occasional reselection.  For
3092b55d35850e3e8e0b28aba7878d3f9122a7907acJeremy Hylton        # a larger number of selections, the pool tracking method is
3102b55d35850e3e8e0b28aba7878d3f9122a7907acJeremy Hylton        # preferred since the list takes less space than the
31191e27c253c8bb8b6ae8521f1dbb76de7c66ad8cfRaymond Hettinger        # set and it doesn't suffer from frequent reselections.
312c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger
313f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger        n = len(population)
314f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger        if not 0 <= k <= n:
315f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger            raise ValueError, "sample larger than population"
3168b9aa8dbba644da23ce8417f2d30b218392b3282Raymond Hettinger        random = self.random
317fdbe5223b7402ee34c4f0c06caa6faabd9e73e35Raymond Hettinger        _int = int
318c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        result = [None] * k
31991e27c253c8bb8b6ae8521f1dbb76de7c66ad8cfRaymond Hettinger        setsize = 21        # size of a small set minus size of an empty list
32091e27c253c8bb8b6ae8521f1dbb76de7c66ad8cfRaymond Hettinger        if k > 5:
3219e34c047325651853a95f95e538582a4f6d5b7f6Tim Peters            setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
322c17976e9833f3093adb1019356737e728a24f7c9Tim Peters        if n <= setsize or hasattr(population, "keys"):
323c17976e9833f3093adb1019356737e728a24f7c9Tim Peters            # An n-length list is smaller than a k-length set, or this is a
324c17976e9833f3093adb1019356737e728a24f7c9Tim Peters            # mapping type so the other algorithm wouldn't work.
325311f4196284b894f86f56c287c71a0e59c4a72a2Raymond Hettinger            pool = list(population)
326311f4196284b894f86f56c287c71a0e59c4a72a2Raymond Hettinger            for i in xrange(k):         # invariant:  non-selected at [0,n-i)
327fdbe5223b7402ee34c4f0c06caa6faabd9e73e35Raymond Hettinger                j = _int(random() * (n-i))
328311f4196284b894f86f56c287c71a0e59c4a72a2Raymond Hettinger                result[i] = pool[j]
3298b9aa8dbba644da23ce8417f2d30b218392b3282Raymond Hettinger                pool[j] = pool[n-i-1]   # move non-selected item into vacancy
330c0b4034b8165ce958a23f2c865b51ae0f52040f5Raymond Hettinger        else:
33166d09f1b3029d9cf975ccf26c437c9fb2605db91Raymond Hettinger            try:
3323c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                selected = set()
3333c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                selected_add = selected.add
3343c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                for i in xrange(k):
335fdbe5223b7402ee34c4f0c06caa6faabd9e73e35Raymond Hettinger                    j = _int(random() * n)
3363c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                    while j in selected:
3373c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                        j = _int(random() * n)
3383c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                    selected_add(j)
3393c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                    result[i] = population[j]
340c17976e9833f3093adb1019356737e728a24f7c9Tim Peters            except (TypeError, KeyError):   # handle (at least) sets
3413c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                if isinstance(population, list):
3423c3346daa9bf900080428ed12b6d83aa04f7332bRaymond Hettinger                    raise
343c17976e9833f3093adb1019356737e728a24f7c9Tim Peters                return self.sample(tuple(population), k)
344311f4196284b894f86f56c287c71a0e59c4a72a2Raymond Hettinger        return result
345f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger
346cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- real-valued distributions  -------------------
347cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters
348cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- uniform distribution -------------------
349d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
350d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def uniform(self, a, b):
351d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        """Get a random number in the range [a, b)."""
352d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return a + (b-a) * self.random()
353ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
354bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger## -------------------- triangular --------------------
355bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger
356bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger    def triangular(self, low, high, mode):
357bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        """Triangular distribution.
358bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger
359bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        Continuous distribution bounded by given lower and upper limits,
360bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        and having a given mode value in-between.
361bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger
362bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        http://en.wikipedia.org/wiki/Triangular_distribution
363bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger
364bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        """
365bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        u = self.random()
366bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        c = (mode - low) / (high - low)
367bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        if u > c:
368bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger            u = 1 - u
369bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger            c = 1 - c
370bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger            low, high = high, low
371bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger        return low + (high - low) * (u * c) ** 0.5
372bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger
373cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- normal distribution --------------------
374ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
375d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def normalvariate(self, mu, sigma):
376c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Normal distribution.
377c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
378c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        mu is the mean, and sigma is the standard deviation.
379ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
380c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
381d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # mu = mean, sigma = standard deviation
382d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
383d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Uses Kinderman and Monahan method. Reference: Kinderman,
384d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # A.J. and Monahan, J.F., "Computer generation of random
385d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # variables using the ratio of uniform deviates", ACM Trans
386d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Math Software, 3, (1977), pp257-260.
387d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
388d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        random = self.random
38942406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger        while 1:
390d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            u1 = random()
39173ced7ee995180c0bd8d96ff7d7fb614a744ad7dRaymond Hettinger            u2 = 1.0 - random()
392d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            z = NV_MAGICCONST*(u1-0.5)/u2
393d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            zz = z*z/4.0
394d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            if zz <= -_log(u2):
395d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                break
396d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return mu + z*sigma
397ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
398cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- lognormal distribution --------------------
399ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
400d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def lognormvariate(self, mu, sigma):
401c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Log normal distribution.
402c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
403c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        If you take the natural logarithm of this distribution, you'll get a
404c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        normal distribution with mean mu and standard deviation sigma.
405c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        mu can have any value, and sigma must be greater than zero.
406ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
407c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
408d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return _exp(self.normalvariate(mu, sigma))
409ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
410cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- exponential distribution --------------------
411ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
412d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def expovariate(self, lambd):
413c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Exponential distribution.
414c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
415c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        lambd is 1.0 divided by the desired mean.  (The parameter would be
416c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        called "lambda", but that is a reserved word in Python.)  Returned
417c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        values range from 0 to positive infinity.
418ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
419c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
420d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # lambd: rate lambd = 1/mean
421d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # ('lambda' is a Python reserved word)
422ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
423d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        random = self.random
4240c9886d589ddebf32de0ca3f027a173222ed383aTim Peters        u = random()
425d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        while u <= 1e-7:
426d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            u = random()
427d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return -_log(u)/lambd
428ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
429cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- von Mises distribution --------------------
430ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
431d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def vonmisesvariate(self, mu, kappa):
432c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Circular data distribution.
433ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
434c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        mu is the mean angle, expressed in radians between 0 and 2*pi, and
435c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        kappa is the concentration parameter, which must be greater than or
436c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        equal to zero.  If kappa is equal to zero, this distribution reduces
437c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        to a uniform random angle over the range 0 to 2*pi.
438ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
439c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
440d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # mu:    mean angle (in radians between 0 and 2*pi)
441d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # kappa: concentration parameter kappa (>= 0)
442d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # if kappa = 0 generate uniform random angle
4435810297052003f28788f6790ac799fe8e5373494Guido van Rossum
444d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Based upon an algorithm published in: Fisher, N.I.,
445d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # "Statistical Analysis of Circular Data", Cambridge
446d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # University Press, 1993.
4475810297052003f28788f6790ac799fe8e5373494Guido van Rossum
448d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Thanks to Magnus Kessler for a correction to the
449d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # implementation of step 4.
4505810297052003f28788f6790ac799fe8e5373494Guido van Rossum
451d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        random = self.random
452d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if kappa <= 1e-6:
453d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            return TWOPI * random()
454ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
455d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        a = 1.0 + _sqrt(1.0 + 4.0 * kappa * kappa)
456d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        b = (a - _sqrt(2.0 * a))/(2.0 * kappa)
457d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        r = (1.0 + b * b)/(2.0 * b)
458ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
45942406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger        while 1:
460d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            u1 = random()
461ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
462d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            z = _cos(_pi * u1)
463d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            f = (1.0 + r * z)/(r + z)
464d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            c = kappa * (r - f)
465ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
466d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            u2 = random()
467ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
46842406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger            if u2 < c * (2.0 - c) or u2 <= c * _exp(1.0 - c):
469d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                break
470ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
471d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        u3 = random()
472d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if u3 > 0.5:
473d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            theta = (mu % TWOPI) + _acos(f)
474d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        else:
475d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            theta = (mu % TWOPI) - _acos(f)
476ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
477d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return theta
478ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
479cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- gamma distribution --------------------
480ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
481d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def gammavariate(self, alpha, beta):
482c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Gamma distribution.  Not the gamma function!
483c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
484c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        Conditions on the parameters are alpha > 0 and beta > 0.
485c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
486c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
4878ac1495a6a1d18111a626cec0c7f2eb67df3edb3Tim Peters
488b760efb08d509bb2acfdef8f4e59dfafa20ca57fRaymond Hettinger        # alpha > 0, beta > 0, mean is alpha*beta, variance is alpha*beta**2
4898ac1495a6a1d18111a626cec0c7f2eb67df3edb3Tim Peters
490570764ddce285afc32e6bd4bce031e421376b382Guido van Rossum        # Warning: a few older sources define the gamma distribution in terms
491570764ddce285afc32e6bd4bce031e421376b382Guido van Rossum        # of alpha > -1.0
492570764ddce285afc32e6bd4bce031e421376b382Guido van Rossum        if alpha <= 0.0 or beta <= 0.0:
493570764ddce285afc32e6bd4bce031e421376b382Guido van Rossum            raise ValueError, 'gammavariate: alpha and beta must be > 0.0'
4948ac1495a6a1d18111a626cec0c7f2eb67df3edb3Tim Peters
495d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        random = self.random
496d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if alpha > 1.0:
497d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
498d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            # Uses R.C.H. Cheng, "The generation of Gamma
499d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            # variables with non-integral shape parameters",
500d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            # Applied Statistics, (1977), 26, No. 1, p71-74
501d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
502ca6cdc2c0259b1b74a3f4c2d29a35e76617a3019Raymond Hettinger            ainv = _sqrt(2.0 * alpha - 1.0)
503ca6cdc2c0259b1b74a3f4c2d29a35e76617a3019Raymond Hettinger            bbb = alpha - LOG4
504ca6cdc2c0259b1b74a3f4c2d29a35e76617a3019Raymond Hettinger            ccc = alpha + ainv
5058ac1495a6a1d18111a626cec0c7f2eb67df3edb3Tim Peters
50642406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger            while 1:
507d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                u1 = random()
50873ced7ee995180c0bd8d96ff7d7fb614a744ad7dRaymond Hettinger                if not 1e-7 < u1 < .9999999:
50973ced7ee995180c0bd8d96ff7d7fb614a744ad7dRaymond Hettinger                    continue
51073ced7ee995180c0bd8d96ff7d7fb614a744ad7dRaymond Hettinger                u2 = 1.0 - random()
511d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                v = _log(u1/(1.0-u1))/ainv
512d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                x = alpha*_exp(v)
513d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                z = u1*u1*u2
514d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                r = bbb+ccc*v-x
515d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                if r + SG_MAGICCONST - 4.5*z >= 0.0 or r >= _log(z):
516b760efb08d509bb2acfdef8f4e59dfafa20ca57fRaymond Hettinger                    return x * beta
517d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
518d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        elif alpha == 1.0:
519d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            # expovariate(1)
5200c9886d589ddebf32de0ca3f027a173222ed383aTim Peters            u = random()
521d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            while u <= 1e-7:
522d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                u = random()
523b760efb08d509bb2acfdef8f4e59dfafa20ca57fRaymond Hettinger            return -_log(u) * beta
524d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
525d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        else:   # alpha is between 0 and 1 (exclusive)
526d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
527d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
528d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
52942406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger            while 1:
530d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                u = random()
531d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                b = (_e + alpha)/_e
532d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                p = b*u
533d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                if p <= 1.0:
53442406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger                    x = p ** (1.0/alpha)
535d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                else:
536d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                    x = -_log((b-p)/alpha)
537d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                u1 = random()
53842406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger                if p > 1.0:
53942406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger                    if u1 <= x ** (alpha - 1.0):
54042406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger                        break
54142406e6f27e9a42e91db8706d897e0b478b13a4dRaymond Hettinger                elif u1 <= _exp(-x):
542d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters                    break
543b760efb08d509bb2acfdef8f4e59dfafa20ca57fRaymond Hettinger            return x * beta
544b760efb08d509bb2acfdef8f4e59dfafa20ca57fRaymond Hettinger
545cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- Gauss (faster alternative) --------------------
54695bfcda3e0be2ace895e021296328a383eafb273Guido van Rossum
547d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def gauss(self, mu, sigma):
548c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Gaussian distribution.
549c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
550c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        mu is the mean, and sigma is the standard deviation.  This is
551c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        slightly faster than the normalvariate() function.
552c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
553c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        Not thread-safe without a lock around calls.
554ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
555c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
556d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
557d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # When x and y are two variables from [0, 1), uniformly
558d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # distributed, then
559d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        #
560d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        #    cos(2*pi*x)*sqrt(-2*log(1-y))
561d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        #    sin(2*pi*x)*sqrt(-2*log(1-y))
562d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        #
563d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # are two *independent* variables with normal distribution
564d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # (mu = 0, sigma = 1).
565d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # (Lambert Meertens)
566d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # (corrected version; bug discovered by Mike Miller, fixed by LM)
567d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
568d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Multithreading note: When two threads call this function
569d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # simultaneously, it is possible that they will receive the
570d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # same return value.  The window is very small though.  To
571d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # avoid this, you have to use a lock around all calls.  (I
572d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # didn't want to slow this down in the serial case by using a
573d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # lock here.)
574d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
575d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        random = self.random
576d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        z = self.gauss_next
577d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        self.gauss_next = None
578d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        if z is None:
579d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            x2pi = random() * TWOPI
580d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            g2rad = _sqrt(-2.0 * _log(1.0 - random()))
581d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            z = _cos(x2pi) * g2rad
582d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters            self.gauss_next = _sin(x2pi) * g2rad
583d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
584d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return mu + z*sigma
58595bfcda3e0be2ace895e021296328a383eafb273Guido van Rossum
586cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- beta --------------------
58785e2e4742d0a1accecd02058a7907df36308297eTim Peters## See
58885e2e4742d0a1accecd02058a7907df36308297eTim Peters## http://sourceforge.net/bugs/?func=detailbug&bug_id=130030&group_id=5470
58985e2e4742d0a1accecd02058a7907df36308297eTim Peters## for Ivan Frohne's insightful analysis of why the original implementation:
59085e2e4742d0a1accecd02058a7907df36308297eTim Peters##
59185e2e4742d0a1accecd02058a7907df36308297eTim Peters##    def betavariate(self, alpha, beta):
59285e2e4742d0a1accecd02058a7907df36308297eTim Peters##        # Discrete Event Simulation in C, pp 87-88.
59385e2e4742d0a1accecd02058a7907df36308297eTim Peters##
59485e2e4742d0a1accecd02058a7907df36308297eTim Peters##        y = self.expovariate(alpha)
59585e2e4742d0a1accecd02058a7907df36308297eTim Peters##        z = self.expovariate(1.0/beta)
59685e2e4742d0a1accecd02058a7907df36308297eTim Peters##        return z/(y+z)
59785e2e4742d0a1accecd02058a7907df36308297eTim Peters##
59885e2e4742d0a1accecd02058a7907df36308297eTim Peters## was dead wrong, and how it probably got that way.
59995bfcda3e0be2ace895e021296328a383eafb273Guido van Rossum
600d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def betavariate(self, alpha, beta):
601c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Beta distribution.
602c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
6031b0ce8527112b997194a4e2fb9a1a850c6d73ee8Raymond Hettinger        Conditions on the parameters are alpha > 0 and beta > 0.
604c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        Returned values range between 0 and 1.
605ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
606c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
607ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
60885e2e4742d0a1accecd02058a7907df36308297eTim Peters        # This version due to Janne Sinkkonen, and matches all the std
60985e2e4742d0a1accecd02058a7907df36308297eTim Peters        # texts (e.g., Knuth Vol 2 Ed 3 pg 134 "the beta distribution").
61085e2e4742d0a1accecd02058a7907df36308297eTim Peters        y = self.gammavariate(alpha, 1.)
61185e2e4742d0a1accecd02058a7907df36308297eTim Peters        if y == 0:
61285e2e4742d0a1accecd02058a7907df36308297eTim Peters            return 0.0
61385e2e4742d0a1accecd02058a7907df36308297eTim Peters        else:
61485e2e4742d0a1accecd02058a7907df36308297eTim Peters            return y / (y + self.gammavariate(beta, 1.))
61595bfcda3e0be2ace895e021296328a383eafb273Guido van Rossum
616cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- Pareto --------------------
617cf4559a62ec9316a3bb55a67c6fca81ec1ad0d18Guido van Rossum
618d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def paretovariate(self, alpha):
619c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Pareto distribution.  alpha is the shape parameter."""
620d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Jain, pg. 495
621cf4559a62ec9316a3bb55a67c6fca81ec1ad0d18Guido van Rossum
62273ced7ee995180c0bd8d96ff7d7fb614a744ad7dRaymond Hettinger        u = 1.0 - self.random()
623d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return 1.0 / pow(u, 1.0/alpha)
624cf4559a62ec9316a3bb55a67c6fca81ec1ad0d18Guido van Rossum
625cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- Weibull --------------------
626cf4559a62ec9316a3bb55a67c6fca81ec1ad0d18Guido van Rossum
627d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    def weibullvariate(self, alpha, beta):
628c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """Weibull distribution.
629c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger
630c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        alpha is the scale parameter and beta is the shape parameter.
631ef4d4bdc3c99d3120a401b7af6e06610716d2e47Raymond Hettinger
632c32f0336e062dd36f82fb236c66ac25e2bac217bRaymond Hettinger        """
633d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        # Jain, pg. 499; bug fix courtesy Bill Arms
634cf4559a62ec9316a3bb55a67c6fca81ec1ad0d18Guido van Rossum
63573ced7ee995180c0bd8d96ff7d7fb614a744ad7dRaymond Hettinger        u = 1.0 - self.random()
636d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters        return alpha * pow(-_log(u), 1.0/beta)
6376c395ba31609eeffce2428280cc5d95e4fb8058aGuido van Rossum
63840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger## -------------------- Wichmann-Hill -------------------
63940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
64040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettingerclass WichmannHill(Random):
64140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
64240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    VERSION = 1     # used by getstate/setstate
64340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
64440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def seed(self, a=None):
64540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Initialize internal state from hashable object.
64640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
64723f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        None or no argument seeds from current time or from an operating
64823f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        system specific randomness source if available.
64940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
65040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        If a is not None or an int or long, hash(a) is used instead.
65140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
65240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        If a is an int or long, a is used directly.  Distinct values between
65340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        0 and 27814431486575L inclusive are guaranteed to yield distinct
65440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        internal states (this guarantee is specific to the default
65540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        Wichmann-Hill generator).
65640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """
65740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
65840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if a is None:
659c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettinger            try:
660c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettinger                a = long(_hexlify(_urandom(16)), 16)
661c1c43cad63a88eae694b174c9a0fe6242dd5972bRaymond Hettinger            except NotImplementedError:
662356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger                import time
663356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger                a = long(time.time() * 256) # use fractional seconds
66440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
66540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if not isinstance(a, (int, long)):
66640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            a = hash(a)
66740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
66840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a, x = divmod(a, 30268)
66940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a, y = divmod(a, 30306)
67040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a, z = divmod(a, 30322)
67140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self._seed = int(x)+1, int(y)+1, int(z)+1
67240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
67340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self.gauss_next = None
67440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
67540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def random(self):
67640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Get the next random number in the range [0.0, 1.0)."""
67740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
67840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # Wichman-Hill random number generator.
67940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #
68040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # Wichmann, B. A. & Hill, I. D. (1982)
68140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # Algorithm AS 183:
68240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # An efficient and portable pseudo-random number generator
68340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # Applied Statistics 31 (1982) 188-190
68440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #
68540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # see also:
68640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #        Correction to Algorithm AS 183
68740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #        Applied Statistics 33 (1984) 123
68840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #
68940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #        McLeod, A. I. (1985)
69040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #        A remark on Algorithm AS 183
69140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        #        Applied Statistics 34 (1985),198-200
69240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
69340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # This part is thread-unsafe:
69440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # BEGIN CRITICAL SECTION
69540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        x, y, z = self._seed
69640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        x = (171 * x) % 30269
69740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        y = (172 * y) % 30307
69840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        z = (170 * z) % 30323
69940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self._seed = x, y, z
70040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # END CRITICAL SECTION
70140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
70240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # Note:  on a platform using IEEE-754 double arithmetic, this can
70340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # never return 0.0 (asserted by Tim; proof too long for a comment).
70440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
70540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
70640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def getstate(self):
70740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Return internal state; can be passed to setstate() later."""
70840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        return self.VERSION, self._seed, self.gauss_next
70940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
71040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def setstate(self, state):
71140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Restore internal state from object returned by getstate()."""
71240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        version = state[0]
71340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if version == 1:
71440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            version, self._seed, self.gauss_next = state
71540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        else:
71640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            raise ValueError("state with version %s passed to "
71740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger                             "Random.setstate() of version %s" %
71840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger                             (version, self.VERSION))
71940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
72040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def jumpahead(self, n):
72140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Act as if n calls to random() were made, but quickly.
72240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
72340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        n is an int, greater than or equal to 0.
72440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
72540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        Example use:  If you have 2 threads and know that each will
72640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        consume no more than a million random numbers, create two Random
72740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        objects r1 and r2, then do
72840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            r2.setstate(r1.getstate())
72940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            r2.jumpahead(1000000)
73040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        Then r1 and r2 will use guaranteed-disjoint segments of the full
73140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        period.
73240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """
73340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
73440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if not n >= 0:
73540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            raise ValueError("n must be >= 0")
73640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        x, y, z = self._seed
73740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        x = int(x * pow(171, n, 30269)) % 30269
73840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        y = int(y * pow(172, n, 30307)) % 30307
73940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        z = int(z * pow(170, n, 30323)) % 30323
74040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self._seed = x, y, z
74140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
74240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def __whseed(self, x=0, y=0, z=0):
74340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Set the Wichmann-Hill seed from (x, y, z).
74440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
74540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        These must be integers in the range [0, 256).
74640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """
74740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
74840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if not type(x) == type(y) == type(z) == int:
74940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            raise TypeError('seeds must be integers')
75040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if not (0 <= x < 256 and 0 <= y < 256 and 0 <= z < 256):
75140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            raise ValueError('seeds must be in range(0, 256)')
75240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if 0 == x == y == z:
75340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            # Initialize from current time
75440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            import time
75540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            t = long(time.time() * 256)
75640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            t = int((t&0xffffff) ^ (t>>24))
75740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            t, x = divmod(t, 256)
75840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            t, y = divmod(t, 256)
75940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            t, z = divmod(t, 256)
76040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        # Zero is a poor seed, so substitute 1
76140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self._seed = (x or 1, y or 1, z or 1)
76240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
76340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self.gauss_next = None
76440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
76540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger    def whseed(self, a=None):
76640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """Seed from hashable object's hash code.
76740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
76840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        None or no argument seeds from current time.  It is not guaranteed
76940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        that objects with distinct hash codes lead to distinct internal
77040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        states.
77140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
77240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        This is obsolete, provided for compatibility with the seed routine
77340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        used prior to Python 2.1.  Use the .seed() method instead.
77440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        """
77540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
77640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        if a is None:
77740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            self.__whseed()
77840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger            return
77940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a = hash(a)
78040f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a, x = divmod(a, 256)
78140f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a, y = divmod(a, 256)
78240f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        a, z = divmod(a, 256)
78340f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        x = (x + a) % 256 or 1
78440f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        y = (y + a) % 256 or 1
78540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        z = (z + a) % 256 or 1
78640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger        self.__whseed(x, y, z)
78740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
78823f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger## --------------- Operating System Random Source  ------------------
789356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
79023f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettingerclass SystemRandom(Random):
79123f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger    """Alternate random number generator using sources provided
79223f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger    by the operating system (such as /dev/urandom on Unix or
79323f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger    CryptGenRandom on Windows).
794356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
795356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger     Not available on all systems (see os.urandom() for details).
796356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    """
797356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
798356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    def random(self):
799356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        """Get the next random number in the range [0.0, 1.0)."""
8007c2a85b2d44851c2442ade579b760f86447bf848Tim Peters        return (long(_hexlify(_urandom(7)), 16) >> 3) * RECIP_BPF
801356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
802356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    def getrandbits(self, k):
803356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        """getrandbits(k) -> x.  Generates a long int with k random bits."""
804356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        if k <= 0:
805356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger            raise ValueError('number of bits must be greater than zero')
806356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        if k != int(k):
807356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger            raise TypeError('number of bits should be an integer')
808356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        bytes = (k + 7) // 8                    # bits / 8 and rounded up
809356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        x = long(_hexlify(_urandom(bytes)), 16)
810356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        return x >> (bytes * 8 - k)             # trim excess bits
811356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
812356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    def _stub(self, *args, **kwds):
81323f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        "Stub method.  Not used for a system random number generator."
814356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger        return None
815356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    seed = jumpahead = _stub
816356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
817356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    def _notimplemented(self, *args, **kwds):
81823f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        "Method should not be called for a system random number generator."
81923f1241dc6495eb255e1a389aef204a3e35a2632Raymond Hettinger        raise NotImplementedError('System entropy source does not have state.')
820356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger    getstate = setstate = _notimplemented
821356a4599acd4c835ab88c221bd5da073c9895e83Raymond Hettinger
822cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters## -------------------- test program --------------------
823ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
82462297132215490e9cb406e1a21f03aff40d421cbRaymond Hettingerdef _test_generator(n, func, args):
8250c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    import time
82662297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    print n, 'times', func.__name__
827b98154e4243a8d73f758dfee9a81bbe36ddc05cbRaymond Hettinger    total = 0.0
8280c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    sqsum = 0.0
8290c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    smallest = 1e10
8300c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    largest = -1e10
8310c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    t0 = time.time()
8320c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    for i in range(n):
83362297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger        x = func(*args)
834b98154e4243a8d73f758dfee9a81bbe36ddc05cbRaymond Hettinger        total += x
8350c9886d589ddebf32de0ca3f027a173222ed383aTim Peters        sqsum = sqsum + x*x
8360c9886d589ddebf32de0ca3f027a173222ed383aTim Peters        smallest = min(x, smallest)
8370c9886d589ddebf32de0ca3f027a173222ed383aTim Peters        largest = max(x, largest)
8380c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    t1 = time.time()
8390c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    print round(t1-t0, 3), 'sec,',
840b98154e4243a8d73f758dfee9a81bbe36ddc05cbRaymond Hettinger    avg = total/n
841d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    stddev = _sqrt(sqsum/n - avg*avg)
8420c9886d589ddebf32de0ca3f027a173222ed383aTim Peters    print 'avg %g, stddev %g, min %g, max %g' % \
8430c9886d589ddebf32de0ca3f027a173222ed383aTim Peters              (avg, stddev, smallest, largest)
844ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossum
845f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettinger
846f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettingerdef _test(N=2000):
84762297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, random, ())
84862297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, normalvariate, (0.0, 1.0))
84962297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, lognormvariate, (0.0, 1.0))
85062297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, vonmisesvariate, (0.0, 1.0))
85162297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (0.01, 1.0))
85262297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (0.1, 1.0))
85362297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (0.1, 2.0))
85462297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (0.5, 1.0))
85562297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (0.9, 1.0))
85662297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (1.0, 1.0))
85762297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (2.0, 1.0))
85862297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (20.0, 1.0))
85962297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gammavariate, (200.0, 1.0))
86062297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, gauss, (0.0, 1.0))
86162297132215490e9cb406e1a21f03aff40d421cbRaymond Hettinger    _test_generator(N, betavariate, (3.0, 3.0))
862bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettinger    _test_generator(N, triangular, (0.0, 1.0, 1.0/3.0))
863cd804108548e1939bd8646634ed52ef388ee9f44Tim Peters
864715c4c412b21f68ad59773698d06eea8eb0c5a44Tim Peters# Create one instance, seeded from current time, and export its methods
86540f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger# as module-level functions.  The functions share state across all uses
86640f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger#(both in the user's code and in the Python libraries), but that's fine
86740f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger# for most programs and is easier for the casual user than making them
86840f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger# instantiate their own Random() instance.
86940f621709286a7a0f7e6f260c0fd020d0fac0de0Raymond Hettinger
870d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters_inst = Random()
871d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersseed = _inst.seed
872d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersrandom = _inst.random
873d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersuniform = _inst.uniform
874bbc50eafe5cc7d2fa73b5b45eebc573c600db9acRaymond Hettingertriangular = _inst.triangular
875d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersrandint = _inst.randint
876d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peterschoice = _inst.choice
877d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersrandrange = _inst.randrange
878f24eb35d185c0623315cfbd9977d37c509860dcfRaymond Hettingersample = _inst.sample
879d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersshuffle = _inst.shuffle
880d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersnormalvariate = _inst.normalvariate
881d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peterslognormvariate = _inst.lognormvariate
882d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersexpovariate = _inst.expovariate
883d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersvonmisesvariate = _inst.vonmisesvariate
884d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersgammavariate = _inst.gammavariate
885d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersgauss = _inst.gauss
886d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersbetavariate = _inst.betavariate
887d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersparetovariate = _inst.paretovariate
888d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersweibullvariate = _inst.weibullvariate
889d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Petersgetstate = _inst.getstate
890d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peterssetstate = _inst.setstate
891d52269bfd029c4a517ea74c17edd5c3a250c366cTim Petersjumpahead = _inst.jumpahead
8922f726e9093381572b21edbfc42659ea89fbdf686Raymond Hettingergetrandbits = _inst.getrandbits
893d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters
894ff03b1ae5bba4d6712563efb7c77ace57dbe6788Guido van Rossumif __name__ == '__main__':
895d7b5e88e8e40b77813ceb25dc28b87d672538403Tim Peters    _test()
896