blob: d4006e5727ec88966aa3b5f2bba726182bd1c33b [file] [log] [blame]
Guido van Rossume7b146f2000-02-04 15:28:42 +00001"""Random variable generators.
Guido van Rossumff03b1a1994-03-09 12:55:02 +00002
Tim Petersd7b5e882001-01-25 03:36:26 +00003 integers
4 --------
5 uniform within range
6
7 sequences
8 ---------
9 pick random element
Raymond Hettingerf24eb352002-11-12 17:41:57 +000010 pick random sample
Tim Petersd7b5e882001-01-25 03:36:26 +000011 generate random permutation
12
Guido van Rossume7b146f2000-02-04 15:28:42 +000013 distributions on the real line:
14 ------------------------------
Tim Petersd7b5e882001-01-25 03:36:26 +000015 uniform
Christian Heimesfe337bf2008-03-23 21:54:12 +000016 triangular
Guido van Rossume7b146f2000-02-04 15:28:42 +000017 normal (Gaussian)
18 lognormal
19 negative exponential
20 gamma
21 beta
Raymond Hettinger40f62172002-12-29 23:03:38 +000022 pareto
23 Weibull
Guido van Rossumff03b1a1994-03-09 12:55:02 +000024
Guido van Rossume7b146f2000-02-04 15:28:42 +000025 distributions on the circle (angles 0 to 2pi)
26 ---------------------------------------------
27 circular uniform
28 von Mises
29
Raymond Hettinger40f62172002-12-29 23:03:38 +000030General notes on the underlying Mersenne Twister core generator:
Guido van Rossume7b146f2000-02-04 15:28:42 +000031
Raymond Hettinger40f62172002-12-29 23:03:38 +000032* The period is 2**19937-1.
Thomas Wouters0e3f5912006-08-11 14:57:12 +000033* It is one of the most extensively tested generators in existence.
Thomas Wouters0e3f5912006-08-11 14:57:12 +000034* The random() method is implemented in C, executes in a single Python step,
35 and is, therefore, threadsafe.
Tim Peterse360d952001-01-26 10:00:39 +000036
Guido van Rossume7b146f2000-02-04 15:28:42 +000037"""
Guido van Rossumd03e1191998-05-29 17:51:31 +000038
Raymond Hettinger2f726e92003-10-05 09:09:15 +000039from warnings import warn as _warn
40from types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
Raymond Hettinger91e27c22005-08-19 01:36:35 +000041from math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil
Tim Petersd7b5e882001-01-25 03:36:26 +000042from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
Raymond Hettingerc1c43ca2004-09-05 00:00:42 +000043from os import urandom as _urandom
Raymond Hettinger102d8742011-05-05 11:49:12 -070044from collections import Set as _Set, Sequence as _Sequence
Raymond Hettinger3fcf0022010-12-08 01:13:53 +000045from hashlib import sha512 as _sha512
Guido van Rossumff03b1a1994-03-09 12:55:02 +000046
Raymond Hettingerf24eb352002-11-12 17:41:57 +000047__all__ = ["Random","seed","random","uniform","randint","choice","sample",
Skip Montanaro0de65802001-02-15 22:15:14 +000048 "randrange","shuffle","normalvariate","lognormvariate",
Christian Heimesfe337bf2008-03-23 21:54:12 +000049 "expovariate","vonmisesvariate","gammavariate","triangular",
Raymond Hettingerf8a52d32003-08-05 12:23:19 +000050 "gauss","betavariate","paretovariate","weibullvariate",
Raymond Hettinger28de64f2008-01-13 23:40:30 +000051 "getstate","setstate", "getrandbits",
Raymond Hettinger23f12412004-09-13 22:23:21 +000052 "SystemRandom"]
Tim Petersd7b5e882001-01-25 03:36:26 +000053
54NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
Tim Petersd7b5e882001-01-25 03:36:26 +000055TWOPI = 2.0*_pi
Tim Petersd7b5e882001-01-25 03:36:26 +000056LOG4 = _log(4.0)
Tim Petersd7b5e882001-01-25 03:36:26 +000057SG_MAGICCONST = 1.0 + _log(4.5)
Raymond Hettinger2f726e92003-10-05 09:09:15 +000058BPF = 53 # Number of bits in a float
Tim Peters7c2a85b2004-08-31 02:19:55 +000059RECIP_BPF = 2**-BPF
Tim Petersd7b5e882001-01-25 03:36:26 +000060
Raymond Hettinger356a4592004-08-30 06:14:31 +000061
Tim Petersd7b5e882001-01-25 03:36:26 +000062# Translated by Guido van Rossum from C source provided by
Raymond Hettinger40f62172002-12-29 23:03:38 +000063# Adrian Baddeley. Adapted by Raymond Hettinger for use with
Raymond Hettinger3fa19d72004-08-31 01:05:15 +000064# the Mersenne Twister and os.urandom() core generators.
Tim Petersd7b5e882001-01-25 03:36:26 +000065
Raymond Hettinger145a4a02003-01-07 10:25:55 +000066import _random
Raymond Hettinger40f62172002-12-29 23:03:38 +000067
Raymond Hettinger145a4a02003-01-07 10:25:55 +000068class Random(_random.Random):
Raymond Hettingerc32f0332002-05-23 19:44:49 +000069 """Random number generator base class used by bound module functions.
70
71 Used to instantiate instances of Random to get generators that don't
Raymond Hettinger28de64f2008-01-13 23:40:30 +000072 share state.
Raymond Hettingerc32f0332002-05-23 19:44:49 +000073
74 Class Random can also be subclassed if you want to use a different basic
75 generator of your own devising: in that case, override the following
Raymond Hettinger28de64f2008-01-13 23:40:30 +000076 methods: random(), seed(), getstate(), and setstate().
Benjamin Petersond18de0e2008-07-31 20:21:46 +000077 Optionally, implement a getrandbits() method so that randrange()
Raymond Hettinger2f726e92003-10-05 09:09:15 +000078 can cover arbitrarily large ranges.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +000079
Raymond Hettingerc32f0332002-05-23 19:44:49 +000080 """
Tim Petersd7b5e882001-01-25 03:36:26 +000081
Christian Heimescbf3b5c2007-12-03 21:02:03 +000082 VERSION = 3 # used by getstate/setstate
Tim Petersd7b5e882001-01-25 03:36:26 +000083
84 def __init__(self, x=None):
85 """Initialize an instance.
86
87 Optional argument x controls seeding, as for Random.seed().
88 """
89
90 self.seed(x)
Raymond Hettinger40f62172002-12-29 23:03:38 +000091 self.gauss_next = None
Tim Petersd7b5e882001-01-25 03:36:26 +000092
Raymond Hettingerf763a722010-09-07 00:38:15 +000093 def seed(self, a=None, version=2):
Tim Peters0de88fc2001-02-01 04:59:18 +000094 """Initialize internal state from hashable object.
Tim Petersd7b5e882001-01-25 03:36:26 +000095
Raymond Hettinger23f12412004-09-13 22:23:21 +000096 None or no argument seeds from current time or from an operating
97 system specific randomness source if available.
Tim Peters0de88fc2001-02-01 04:59:18 +000098
Raymond Hettinger183cd1f2010-09-08 18:48:21 +000099 For version 2 (the default), all of the bits are used if *a *is a str,
100 bytes, or bytearray. For version 1, the hash() of *a* is used instead.
Raymond Hettingerf763a722010-09-07 00:38:15 +0000101
Raymond Hettinger183cd1f2010-09-08 18:48:21 +0000102 If *a* is an int, all bits are used.
Raymond Hettingerf763a722010-09-07 00:38:15 +0000103
Tim Petersd7b5e882001-01-25 03:36:26 +0000104 """
105
Raymond Hettinger3081d592003-08-09 18:30:57 +0000106 if a is None:
Raymond Hettingerc1c43ca2004-09-05 00:00:42 +0000107 try:
Raymond Hettinger183cd1f2010-09-08 18:48:21 +0000108 a = int.from_bytes(_urandom(32), 'big')
Raymond Hettingerc1c43ca2004-09-05 00:00:42 +0000109 except NotImplementedError:
Raymond Hettinger356a4592004-08-30 06:14:31 +0000110 import time
Guido van Rossume2a383d2007-01-15 16:59:06 +0000111 a = int(time.time() * 256) # use fractional seconds
Raymond Hettinger356a4592004-08-30 06:14:31 +0000112
Raymond Hettinger3fcf0022010-12-08 01:13:53 +0000113 if version == 2:
114 if isinstance(a, (str, bytes, bytearray)):
115 if isinstance(a, str):
Raymond Hettingerf90ba8a2011-05-05 11:35:50 -0700116 a = a.encode()
Raymond Hettinger3fcf0022010-12-08 01:13:53 +0000117 a += _sha512(a).digest()
118 a = int.from_bytes(a, 'big')
Raymond Hettingerf763a722010-09-07 00:38:15 +0000119
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000120 super().seed(a)
Tim Peters46c04e12002-05-05 20:40:00 +0000121 self.gauss_next = None
122
Tim Peterscd804102001-01-25 20:25:57 +0000123 def getstate(self):
124 """Return internal state; can be passed to setstate() later."""
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000125 return self.VERSION, super().getstate(), self.gauss_next
Tim Peterscd804102001-01-25 20:25:57 +0000126
127 def setstate(self, state):
128 """Restore internal state from object returned by getstate()."""
129 version = state[0]
Christian Heimescbf3b5c2007-12-03 21:02:03 +0000130 if version == 3:
Raymond Hettinger40f62172002-12-29 23:03:38 +0000131 version, internalstate, self.gauss_next = state
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000132 super().setstate(internalstate)
Christian Heimescbf3b5c2007-12-03 21:02:03 +0000133 elif version == 2:
134 version, internalstate, self.gauss_next = state
135 # In version 2, the state was saved as signed ints, which causes
136 # inconsistencies between 32/64-bit systems. The state is
137 # really unsigned 32-bit ints, so we convert negative ints from
138 # version 2 to positive longs for version 3.
139 try:
Raymond Hettingerc585eec2010-09-07 15:00:15 +0000140 internalstate = tuple(x % (2**32) for x in internalstate)
Christian Heimescbf3b5c2007-12-03 21:02:03 +0000141 except ValueError as e:
142 raise TypeError from e
Raymond Hettinger183cd1f2010-09-08 18:48:21 +0000143 super().setstate(internalstate)
Tim Peterscd804102001-01-25 20:25:57 +0000144 else:
145 raise ValueError("state with version %s passed to "
146 "Random.setstate() of version %s" %
147 (version, self.VERSION))
148
Tim Peterscd804102001-01-25 20:25:57 +0000149## ---- Methods below this point do not need to be overridden when
150## ---- subclassing for the purpose of using a different core generator.
151
152## -------------------- pickle support -------------------
153
154 def __getstate__(self): # for pickle
155 return self.getstate()
156
157 def __setstate__(self, state): # for pickle
158 self.setstate(state)
159
Raymond Hettinger5f078ff2003-06-24 20:29:04 +0000160 def __reduce__(self):
161 return self.__class__, (), self.getstate()
162
Tim Peterscd804102001-01-25 20:25:57 +0000163## -------------------- integer methods -------------------
164
Raymond Hettinger05156612010-09-07 04:44:52 +0000165 def randrange(self, start, stop=None, step=1, int=int):
Tim Petersd7b5e882001-01-25 03:36:26 +0000166 """Choose a random item from range(start, stop[, step]).
167
168 This fixes the problem with randint() which includes the
169 endpoint; in Python this is usually not what you want.
Raymond Hettinger3051cc32010-09-07 00:48:40 +0000170
Raymond Hettingerc3246972010-09-07 09:32:57 +0000171 Do not supply the 'int' argument.
Tim Petersd7b5e882001-01-25 03:36:26 +0000172 """
173
174 # This code is a bit messy to make it fast for the
Tim Peters9146f272002-08-16 03:41:39 +0000175 # common case while still doing adequate error checking.
Tim Petersd7b5e882001-01-25 03:36:26 +0000176 istart = int(start)
177 if istart != start:
Collin Winterce36ad82007-08-30 01:19:48 +0000178 raise ValueError("non-integer arg 1 for randrange()")
Raymond Hettinger3051cc32010-09-07 00:48:40 +0000179 if stop is None:
Tim Petersd7b5e882001-01-25 03:36:26 +0000180 if istart > 0:
Raymond Hettinger05156612010-09-07 04:44:52 +0000181 return self._randbelow(istart)
Collin Winterce36ad82007-08-30 01:19:48 +0000182 raise ValueError("empty range for randrange()")
Tim Peters9146f272002-08-16 03:41:39 +0000183
184 # stop argument supplied.
Tim Petersd7b5e882001-01-25 03:36:26 +0000185 istop = int(stop)
186 if istop != stop:
Collin Winterce36ad82007-08-30 01:19:48 +0000187 raise ValueError("non-integer stop for randrange()")
Raymond Hettinger2f726e92003-10-05 09:09:15 +0000188 width = istop - istart
189 if step == 1 and width > 0:
Raymond Hettingerc3246972010-09-07 09:32:57 +0000190 return istart + self._randbelow(width)
Tim Petersd7b5e882001-01-25 03:36:26 +0000191 if step == 1:
Collin Winterce36ad82007-08-30 01:19:48 +0000192 raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))
Tim Peters9146f272002-08-16 03:41:39 +0000193
194 # Non-unit step argument supplied.
Tim Petersd7b5e882001-01-25 03:36:26 +0000195 istep = int(step)
196 if istep != step:
Collin Winterce36ad82007-08-30 01:19:48 +0000197 raise ValueError("non-integer step for randrange()")
Tim Petersd7b5e882001-01-25 03:36:26 +0000198 if istep > 0:
Raymond Hettingerffdb8bb2004-09-27 15:29:05 +0000199 n = (width + istep - 1) // istep
Tim Petersd7b5e882001-01-25 03:36:26 +0000200 elif istep < 0:
Raymond Hettingerffdb8bb2004-09-27 15:29:05 +0000201 n = (width + istep + 1) // istep
Tim Petersd7b5e882001-01-25 03:36:26 +0000202 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000203 raise ValueError("zero step for randrange()")
Tim Petersd7b5e882001-01-25 03:36:26 +0000204
205 if n <= 0:
Collin Winterce36ad82007-08-30 01:19:48 +0000206 raise ValueError("empty range for randrange()")
Raymond Hettinger2f726e92003-10-05 09:09:15 +0000207
Raymond Hettinger05156612010-09-07 04:44:52 +0000208 return istart + istep*self._randbelow(n)
Tim Petersd7b5e882001-01-25 03:36:26 +0000209
210 def randint(self, a, b):
Tim Peterscd804102001-01-25 20:25:57 +0000211 """Return random integer in range [a, b], including both end points.
Tim Petersd7b5e882001-01-25 03:36:26 +0000212 """
213
214 return self.randrange(a, b+1)
215
Raymond Hettingere4a3e992010-09-08 00:30:28 +0000216 def _randbelow(self, n, int=int, maxsize=1<<BPF, type=type,
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000217 Method=_MethodType, BuiltinMethod=_BuiltinMethodType):
Raymond Hettingere4a3e992010-09-08 00:30:28 +0000218 "Return a random int in the range [0,n). Raises ValueError if n==0."
Raymond Hettinger2f726e92003-10-05 09:09:15 +0000219
Raymond Hettingerc3246972010-09-07 09:32:57 +0000220 getrandbits = self.getrandbits
221 # Only call self.getrandbits if the original random() builtin method
222 # has not been overridden or if a new getrandbits() was supplied.
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000223 if type(self.random) is BuiltinMethod or type(getrandbits) is Method:
Raymond Hettingere4a3e992010-09-08 00:30:28 +0000224 k = n.bit_length() # don't use (n-1) here because n can be 1
Raymond Hettingerf015b3f2010-09-07 20:04:42 +0000225 r = getrandbits(k) # 0 <= r < 2**k
Raymond Hettingerc3246972010-09-07 09:32:57 +0000226 while r >= n:
227 r = getrandbits(k)
228 return r
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000229 # There's an overriden random() method but no new getrandbits() method,
230 # so we can only use random() from here.
Raymond Hettingere4a3e992010-09-08 00:30:28 +0000231 random = self.random
232 if n >= maxsize:
Raymond Hettinger2f726e92003-10-05 09:09:15 +0000233 _warn("Underlying random() generator does not supply \n"
Raymond Hettingerf015b3f2010-09-07 20:04:42 +0000234 "enough bits to choose from a population range this large.\n"
235 "To remove the range limitation, add a getrandbits() method.")
Raymond Hettingere4a3e992010-09-08 00:30:28 +0000236 return int(random() * n)
237 rem = maxsize % n
238 limit = (maxsize - rem) / maxsize # int(limit * maxsize) % n == 0
239 r = random()
240 while r >= limit:
241 r = random()
242 return int(r*maxsize) % n
Raymond Hettinger2f726e92003-10-05 09:09:15 +0000243
Tim Peterscd804102001-01-25 20:25:57 +0000244## -------------------- sequence methods -------------------
245
Tim Petersd7b5e882001-01-25 03:36:26 +0000246 def choice(self, seq):
247 """Choose a random element from a non-empty sequence."""
Raymond Hettingerdc4872e2010-09-07 10:06:56 +0000248 try:
249 i = self._randbelow(len(seq))
250 except ValueError:
251 raise IndexError('Cannot choose from an empty sequence')
252 return seq[i]
Tim Petersd7b5e882001-01-25 03:36:26 +0000253
254 def shuffle(self, x, random=None, int=int):
255 """x, random=random.random -> shuffle list x in place; return None.
256
257 Optional arg random is a 0-argument function returning a random
258 float in [0.0, 1.0); by default, the standard random.random.
Tim Petersd7b5e882001-01-25 03:36:26 +0000259 """
260
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000261 randbelow = self._randbelow
262 for i in reversed(range(1, len(x))):
263 # pick an element in x[:i+1] with which to exchange x[i]
264 j = randbelow(i+1) if random is None else int(random() * (i+1))
265 x[i], x[j] = x[j], x[i]
Tim Petersd7b5e882001-01-25 03:36:26 +0000266
Raymond Hettingerfdbe5222003-06-13 07:01:51 +0000267 def sample(self, population, k):
Raymond Hettinger1acde192008-01-14 01:00:53 +0000268 """Chooses k unique random elements from a population sequence or set.
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000269
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000270 Returns a new list containing elements from the population while
271 leaving the original population unchanged. The resulting list is
272 in selection order so that all sub-slices will also be valid random
273 samples. This allows raffle winners (the sample) to be partitioned
274 into grand prize and second place winners (the subslices).
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000275
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000276 Members of the population need not be hashable or unique. If the
277 population contains repeats, then each occurrence is a possible
278 selection in the sample.
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000279
Guido van Rossum805365e2007-05-07 22:24:25 +0000280 To choose a sample in a range of integers, use range as an argument.
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000281 This is especially fast and space efficient for sampling from a
Guido van Rossum805365e2007-05-07 22:24:25 +0000282 large population: sample(range(10000000), 60)
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000283 """
284
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000285 # Sampling without replacement entails tracking either potential
Raymond Hettinger91e27c22005-08-19 01:36:35 +0000286 # selections (the pool) in a list or previous selections in a set.
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000287
Jeremy Hylton2b55d352004-02-23 17:27:57 +0000288 # When the number of selections is small compared to the
289 # population, then tracking selections is efficient, requiring
Raymond Hettinger91e27c22005-08-19 01:36:35 +0000290 # only a small set and an occasional reselection. For
Jeremy Hylton2b55d352004-02-23 17:27:57 +0000291 # a larger number of selections, the pool tracking method is
292 # preferred since the list takes less space than the
Raymond Hettinger91e27c22005-08-19 01:36:35 +0000293 # set and it doesn't suffer from frequent reselections.
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000294
Raymond Hettinger102d8742011-05-05 11:49:12 -0700295 if isinstance(population, _Set):
Raymond Hettinger1acde192008-01-14 01:00:53 +0000296 population = tuple(population)
Raymond Hettinger102d8742011-05-05 11:49:12 -0700297 if not isinstance(population, _Sequence):
298 raise TypeError("Population must be a sequence or set. For dicts, use list(d).")
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000299 randbelow = self._randbelow
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000300 n = len(population)
301 if not 0 <= k <= n:
Raymond Hettinger1acde192008-01-14 01:00:53 +0000302 raise ValueError("Sample larger than population")
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000303 result = [None] * k
Raymond Hettinger91e27c22005-08-19 01:36:35 +0000304 setsize = 21 # size of a small set minus size of an empty list
305 if k > 5:
Tim Peters9e34c042005-08-26 15:20:46 +0000306 setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
Raymond Hettinger1acde192008-01-14 01:00:53 +0000307 if n <= setsize:
308 # An n-length list is smaller than a k-length set
Raymond Hettinger311f4192002-11-18 09:01:24 +0000309 pool = list(population)
Guido van Rossum805365e2007-05-07 22:24:25 +0000310 for i in range(k): # invariant: non-selected at [0,n-i)
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000311 j = randbelow(n-i)
Raymond Hettinger311f4192002-11-18 09:01:24 +0000312 result[i] = pool[j]
Raymond Hettinger8b9aa8d2003-01-04 05:20:33 +0000313 pool[j] = pool[n-i-1] # move non-selected item into vacancy
Raymond Hettingerc0b40342002-11-13 15:26:37 +0000314 else:
Raymond Hettinger1acde192008-01-14 01:00:53 +0000315 selected = set()
316 selected_add = selected.add
317 for i in range(k):
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000318 j = randbelow(n)
Raymond Hettinger1acde192008-01-14 01:00:53 +0000319 while j in selected:
Raymond Hettinger05a505f2010-09-07 19:19:33 +0000320 j = randbelow(n)
Raymond Hettinger1acde192008-01-14 01:00:53 +0000321 selected_add(j)
322 result[i] = population[j]
Raymond Hettinger311f4192002-11-18 09:01:24 +0000323 return result
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000324
Tim Peterscd804102001-01-25 20:25:57 +0000325## -------------------- real-valued distributions -------------------
326
327## -------------------- uniform distribution -------------------
Tim Petersd7b5e882001-01-25 03:36:26 +0000328
329 def uniform(self, a, b):
Raymond Hettingerbe40db02009-06-11 23:12:14 +0000330 "Get a random number in the range [a, b) or [a, b] depending on rounding."
Tim Petersd7b5e882001-01-25 03:36:26 +0000331 return a + (b-a) * self.random()
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000332
Christian Heimesfe337bf2008-03-23 21:54:12 +0000333## -------------------- triangular --------------------
334
335 def triangular(self, low=0.0, high=1.0, mode=None):
336 """Triangular distribution.
337
338 Continuous distribution bounded by given lower and upper limits,
339 and having a given mode value in-between.
340
341 http://en.wikipedia.org/wiki/Triangular_distribution
342
343 """
344 u = self.random()
345 c = 0.5 if mode is None else (mode - low) / (high - low)
346 if u > c:
347 u = 1.0 - u
348 c = 1.0 - c
349 low, high = high, low
350 return low + (high - low) * (u * c) ** 0.5
351
Tim Peterscd804102001-01-25 20:25:57 +0000352## -------------------- normal distribution --------------------
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000353
Tim Petersd7b5e882001-01-25 03:36:26 +0000354 def normalvariate(self, mu, sigma):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000355 """Normal distribution.
356
357 mu is the mean, and sigma is the standard deviation.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000358
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000359 """
Tim Petersd7b5e882001-01-25 03:36:26 +0000360 # mu = mean, sigma = standard deviation
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000361
Tim Petersd7b5e882001-01-25 03:36:26 +0000362 # Uses Kinderman and Monahan method. Reference: Kinderman,
363 # A.J. and Monahan, J.F., "Computer generation of random
364 # variables using the ratio of uniform deviates", ACM Trans
365 # Math Software, 3, (1977), pp257-260.
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000366
Tim Petersd7b5e882001-01-25 03:36:26 +0000367 random = self.random
Raymond Hettinger42406e62005-04-30 09:02:51 +0000368 while 1:
Tim Peters0c9886d2001-01-15 01:18:21 +0000369 u1 = random()
Raymond Hettinger73ced7e2003-01-04 09:26:32 +0000370 u2 = 1.0 - random()
Tim Petersd7b5e882001-01-25 03:36:26 +0000371 z = NV_MAGICCONST*(u1-0.5)/u2
372 zz = z*z/4.0
373 if zz <= -_log(u2):
374 break
375 return mu + z*sigma
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000376
Tim Peterscd804102001-01-25 20:25:57 +0000377## -------------------- lognormal distribution --------------------
Tim Petersd7b5e882001-01-25 03:36:26 +0000378
379 def lognormvariate(self, mu, sigma):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000380 """Log normal distribution.
381
382 If you take the natural logarithm of this distribution, you'll get a
383 normal distribution with mean mu and standard deviation sigma.
384 mu can have any value, and sigma must be greater than zero.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000385
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000386 """
Tim Petersd7b5e882001-01-25 03:36:26 +0000387 return _exp(self.normalvariate(mu, sigma))
388
Tim Peterscd804102001-01-25 20:25:57 +0000389## -------------------- exponential distribution --------------------
Tim Petersd7b5e882001-01-25 03:36:26 +0000390
391 def expovariate(self, lambd):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000392 """Exponential distribution.
393
Mark Dickinson2f947362009-01-07 17:54:07 +0000394 lambd is 1.0 divided by the desired mean. It should be
395 nonzero. (The parameter would be called "lambda", but that is
396 a reserved word in Python.) Returned values range from 0 to
397 positive infinity if lambd is positive, and from negative
398 infinity to 0 if lambd is negative.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000399
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000400 """
Tim Petersd7b5e882001-01-25 03:36:26 +0000401 # lambd: rate lambd = 1/mean
402 # ('lambda' is a Python reserved word)
403
Raymond Hettinger5279fb92011-06-25 11:30:53 +0200404 # we use 1-random() instead of random() to preclude the
405 # possibility of taking the log of zero.
406 return -_log(1.0 - self.random())/lambd
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000407
Tim Peterscd804102001-01-25 20:25:57 +0000408## -------------------- von Mises distribution --------------------
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000409
Tim Petersd7b5e882001-01-25 03:36:26 +0000410 def vonmisesvariate(self, mu, kappa):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000411 """Circular data distribution.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000412
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000413 mu is the mean angle, expressed in radians between 0 and 2*pi, and
414 kappa is the concentration parameter, which must be greater than or
415 equal to zero. If kappa is equal to zero, this distribution reduces
416 to a uniform random angle over the range 0 to 2*pi.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000417
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000418 """
Tim Petersd7b5e882001-01-25 03:36:26 +0000419 # mu: mean angle (in radians between 0 and 2*pi)
420 # kappa: concentration parameter kappa (>= 0)
421 # if kappa = 0 generate uniform random angle
422
423 # Based upon an algorithm published in: Fisher, N.I.,
424 # "Statistical Analysis of Circular Data", Cambridge
425 # University Press, 1993.
426
427 # Thanks to Magnus Kessler for a correction to the
428 # implementation of step 4.
429
430 random = self.random
431 if kappa <= 1e-6:
432 return TWOPI * random()
433
434 a = 1.0 + _sqrt(1.0 + 4.0 * kappa * kappa)
435 b = (a - _sqrt(2.0 * a))/(2.0 * kappa)
436 r = (1.0 + b * b)/(2.0 * b)
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000437
Raymond Hettinger42406e62005-04-30 09:02:51 +0000438 while 1:
Tim Peters0c9886d2001-01-15 01:18:21 +0000439 u1 = random()
Tim Petersd7b5e882001-01-25 03:36:26 +0000440
441 z = _cos(_pi * u1)
442 f = (1.0 + r * z)/(r + z)
443 c = kappa * (r - f)
444
445 u2 = random()
446
Raymond Hettinger42406e62005-04-30 09:02:51 +0000447 if u2 < c * (2.0 - c) or u2 <= c * _exp(1.0 - c):
Tim Peters0c9886d2001-01-15 01:18:21 +0000448 break
Tim Petersd7b5e882001-01-25 03:36:26 +0000449
450 u3 = random()
451 if u3 > 0.5:
452 theta = (mu % TWOPI) + _acos(f)
453 else:
454 theta = (mu % TWOPI) - _acos(f)
455
456 return theta
457
Tim Peterscd804102001-01-25 20:25:57 +0000458## -------------------- gamma distribution --------------------
Tim Petersd7b5e882001-01-25 03:36:26 +0000459
460 def gammavariate(self, alpha, beta):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000461 """Gamma distribution. Not the gamma function!
462
463 Conditions on the parameters are alpha > 0 and beta > 0.
464
Raymond Hettingera8e4d6e2011-03-22 15:55:51 -0700465 The probability distribution function is:
466
467 x ** (alpha - 1) * math.exp(-x / beta)
468 pdf(x) = --------------------------------------
469 math.gamma(alpha) * beta ** alpha
470
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000471 """
Tim Peters8ac14952002-05-23 15:15:30 +0000472
Raymond Hettingerb760efb2002-05-14 06:40:34 +0000473 # alpha > 0, beta > 0, mean is alpha*beta, variance is alpha*beta**2
Tim Peters8ac14952002-05-23 15:15:30 +0000474
Guido van Rossum570764d2002-05-14 14:08:12 +0000475 # Warning: a few older sources define the gamma distribution in terms
476 # of alpha > -1.0
477 if alpha <= 0.0 or beta <= 0.0:
Collin Winterce36ad82007-08-30 01:19:48 +0000478 raise ValueError('gammavariate: alpha and beta must be > 0.0')
Tim Peters8ac14952002-05-23 15:15:30 +0000479
Tim Petersd7b5e882001-01-25 03:36:26 +0000480 random = self.random
Tim Petersd7b5e882001-01-25 03:36:26 +0000481 if alpha > 1.0:
482
483 # Uses R.C.H. Cheng, "The generation of Gamma
484 # variables with non-integral shape parameters",
485 # Applied Statistics, (1977), 26, No. 1, p71-74
486
Raymond Hettingerca6cdc22002-05-13 23:40:14 +0000487 ainv = _sqrt(2.0 * alpha - 1.0)
488 bbb = alpha - LOG4
489 ccc = alpha + ainv
Tim Peters8ac14952002-05-23 15:15:30 +0000490
Raymond Hettinger42406e62005-04-30 09:02:51 +0000491 while 1:
Tim Petersd7b5e882001-01-25 03:36:26 +0000492 u1 = random()
Raymond Hettinger73ced7e2003-01-04 09:26:32 +0000493 if not 1e-7 < u1 < .9999999:
494 continue
495 u2 = 1.0 - random()
Tim Petersd7b5e882001-01-25 03:36:26 +0000496 v = _log(u1/(1.0-u1))/ainv
497 x = alpha*_exp(v)
498 z = u1*u1*u2
499 r = bbb+ccc*v-x
500 if r + SG_MAGICCONST - 4.5*z >= 0.0 or r >= _log(z):
Raymond Hettingerb760efb2002-05-14 06:40:34 +0000501 return x * beta
Tim Petersd7b5e882001-01-25 03:36:26 +0000502
503 elif alpha == 1.0:
504 # expovariate(1)
505 u = random()
506 while u <= 1e-7:
507 u = random()
Raymond Hettingerb760efb2002-05-14 06:40:34 +0000508 return -_log(u) * beta
Tim Petersd7b5e882001-01-25 03:36:26 +0000509
510 else: # alpha is between 0 and 1 (exclusive)
511
512 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
513
Raymond Hettinger42406e62005-04-30 09:02:51 +0000514 while 1:
Tim Petersd7b5e882001-01-25 03:36:26 +0000515 u = random()
516 b = (_e + alpha)/_e
517 p = b*u
518 if p <= 1.0:
Raymond Hettinger42406e62005-04-30 09:02:51 +0000519 x = p ** (1.0/alpha)
Tim Petersd7b5e882001-01-25 03:36:26 +0000520 else:
Tim Petersd7b5e882001-01-25 03:36:26 +0000521 x = -_log((b-p)/alpha)
522 u1 = random()
Raymond Hettinger42406e62005-04-30 09:02:51 +0000523 if p > 1.0:
524 if u1 <= x ** (alpha - 1.0):
525 break
526 elif u1 <= _exp(-x):
Tim Petersd7b5e882001-01-25 03:36:26 +0000527 break
Raymond Hettingerb760efb2002-05-14 06:40:34 +0000528 return x * beta
529
Tim Peterscd804102001-01-25 20:25:57 +0000530## -------------------- Gauss (faster alternative) --------------------
Guido van Rossum95bfcda1994-03-09 14:21:05 +0000531
Tim Petersd7b5e882001-01-25 03:36:26 +0000532 def gauss(self, mu, sigma):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000533 """Gaussian distribution.
534
535 mu is the mean, and sigma is the standard deviation. This is
536 slightly faster than the normalvariate() function.
537
538 Not thread-safe without a lock around calls.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000539
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000540 """
Guido van Rossumcc32ac91994-03-15 16:10:24 +0000541
Tim Petersd7b5e882001-01-25 03:36:26 +0000542 # When x and y are two variables from [0, 1), uniformly
543 # distributed, then
544 #
545 # cos(2*pi*x)*sqrt(-2*log(1-y))
546 # sin(2*pi*x)*sqrt(-2*log(1-y))
547 #
548 # are two *independent* variables with normal distribution
549 # (mu = 0, sigma = 1).
550 # (Lambert Meertens)
551 # (corrected version; bug discovered by Mike Miller, fixed by LM)
Guido van Rossumcc32ac91994-03-15 16:10:24 +0000552
Tim Petersd7b5e882001-01-25 03:36:26 +0000553 # Multithreading note: When two threads call this function
554 # simultaneously, it is possible that they will receive the
555 # same return value. The window is very small though. To
556 # avoid this, you have to use a lock around all calls. (I
557 # didn't want to slow this down in the serial case by using a
558 # lock here.)
Guido van Rossumd03e1191998-05-29 17:51:31 +0000559
Tim Petersd7b5e882001-01-25 03:36:26 +0000560 random = self.random
561 z = self.gauss_next
562 self.gauss_next = None
563 if z is None:
564 x2pi = random() * TWOPI
565 g2rad = _sqrt(-2.0 * _log(1.0 - random()))
566 z = _cos(x2pi) * g2rad
567 self.gauss_next = _sin(x2pi) * g2rad
Guido van Rossumcc32ac91994-03-15 16:10:24 +0000568
Tim Petersd7b5e882001-01-25 03:36:26 +0000569 return mu + z*sigma
Guido van Rossum95bfcda1994-03-09 14:21:05 +0000570
Tim Peterscd804102001-01-25 20:25:57 +0000571## -------------------- beta --------------------
Tim Peters85e2e472001-01-26 06:49:56 +0000572## See
Ezio Melotti20f53f12011-04-15 08:25:16 +0300573## http://mail.python.org/pipermail/python-bugs-list/2001-January/003752.html
Tim Peters85e2e472001-01-26 06:49:56 +0000574## for Ivan Frohne's insightful analysis of why the original implementation:
575##
576## def betavariate(self, alpha, beta):
577## # Discrete Event Simulation in C, pp 87-88.
578##
579## y = self.expovariate(alpha)
580## z = self.expovariate(1.0/beta)
581## return z/(y+z)
582##
583## was dead wrong, and how it probably got that way.
Guido van Rossum95bfcda1994-03-09 14:21:05 +0000584
Tim Petersd7b5e882001-01-25 03:36:26 +0000585 def betavariate(self, alpha, beta):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000586 """Beta distribution.
587
Thomas Woutersb2137042007-02-01 18:02:27 +0000588 Conditions on the parameters are alpha > 0 and beta > 0.
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000589 Returned values range between 0 and 1.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000590
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000591 """
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000592
Tim Peters85e2e472001-01-26 06:49:56 +0000593 # This version due to Janne Sinkkonen, and matches all the std
594 # texts (e.g., Knuth Vol 2 Ed 3 pg 134 "the beta distribution").
595 y = self.gammavariate(alpha, 1.)
596 if y == 0:
597 return 0.0
598 else:
599 return y / (y + self.gammavariate(beta, 1.))
Guido van Rossum95bfcda1994-03-09 14:21:05 +0000600
Tim Peterscd804102001-01-25 20:25:57 +0000601## -------------------- Pareto --------------------
Guido van Rossumcf4559a1997-12-02 02:47:39 +0000602
Tim Petersd7b5e882001-01-25 03:36:26 +0000603 def paretovariate(self, alpha):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000604 """Pareto distribution. alpha is the shape parameter."""
Tim Petersd7b5e882001-01-25 03:36:26 +0000605 # Jain, pg. 495
Guido van Rossumcf4559a1997-12-02 02:47:39 +0000606
Raymond Hettinger73ced7e2003-01-04 09:26:32 +0000607 u = 1.0 - self.random()
Raymond Hettinger8ff10992010-09-08 18:58:33 +0000608 return 1.0 / u ** (1.0/alpha)
Guido van Rossumcf4559a1997-12-02 02:47:39 +0000609
Tim Peterscd804102001-01-25 20:25:57 +0000610## -------------------- Weibull --------------------
Guido van Rossumcf4559a1997-12-02 02:47:39 +0000611
Tim Petersd7b5e882001-01-25 03:36:26 +0000612 def weibullvariate(self, alpha, beta):
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000613 """Weibull distribution.
614
615 alpha is the scale parameter and beta is the shape parameter.
Raymond Hettingeref4d4bd2002-05-23 23:58:17 +0000616
Raymond Hettingerc32f0332002-05-23 19:44:49 +0000617 """
Tim Petersd7b5e882001-01-25 03:36:26 +0000618 # Jain, pg. 499; bug fix courtesy Bill Arms
Guido van Rossumcf4559a1997-12-02 02:47:39 +0000619
Raymond Hettinger73ced7e2003-01-04 09:26:32 +0000620 u = 1.0 - self.random()
Raymond Hettinger183cd1f2010-09-08 18:48:21 +0000621 return alpha * (-_log(u)) ** (1.0/beta)
Guido van Rossum6c395ba1999-08-18 13:53:28 +0000622
Raymond Hettinger23f12412004-09-13 22:23:21 +0000623## --------------- Operating System Random Source ------------------
Raymond Hettinger356a4592004-08-30 06:14:31 +0000624
Raymond Hettinger23f12412004-09-13 22:23:21 +0000625class SystemRandom(Random):
626 """Alternate random number generator using sources provided
627 by the operating system (such as /dev/urandom on Unix or
628 CryptGenRandom on Windows).
Raymond Hettinger356a4592004-08-30 06:14:31 +0000629
630 Not available on all systems (see os.urandom() for details).
631 """
632
633 def random(self):
634 """Get the next random number in the range [0.0, 1.0)."""
Raymond Hettinger183cd1f2010-09-08 18:48:21 +0000635 return (int.from_bytes(_urandom(7), 'big') >> 3) * RECIP_BPF
Raymond Hettinger356a4592004-08-30 06:14:31 +0000636
637 def getrandbits(self, k):
638 """getrandbits(k) -> x. Generates a long int with k random bits."""
Raymond Hettinger356a4592004-08-30 06:14:31 +0000639 if k <= 0:
640 raise ValueError('number of bits must be greater than zero')
641 if k != int(k):
642 raise TypeError('number of bits should be an integer')
Raymond Hettinger63b17672010-09-08 19:27:59 +0000643 numbytes = (k + 7) // 8 # bits / 8 and rounded up
644 x = int.from_bytes(_urandom(numbytes), 'big')
645 return x >> (numbytes * 8 - k) # trim excess bits
Raymond Hettinger356a4592004-08-30 06:14:31 +0000646
Raymond Hettinger28de64f2008-01-13 23:40:30 +0000647 def seed(self, *args, **kwds):
Raymond Hettinger23f12412004-09-13 22:23:21 +0000648 "Stub method. Not used for a system random number generator."
Raymond Hettinger356a4592004-08-30 06:14:31 +0000649 return None
Raymond Hettinger356a4592004-08-30 06:14:31 +0000650
651 def _notimplemented(self, *args, **kwds):
Raymond Hettinger23f12412004-09-13 22:23:21 +0000652 "Method should not be called for a system random number generator."
653 raise NotImplementedError('System entropy source does not have state.')
Raymond Hettinger356a4592004-08-30 06:14:31 +0000654 getstate = setstate = _notimplemented
655
Tim Peterscd804102001-01-25 20:25:57 +0000656## -------------------- test program --------------------
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000657
Raymond Hettinger62297132003-08-30 01:24:19 +0000658def _test_generator(n, func, args):
Tim Peters0c9886d2001-01-15 01:18:21 +0000659 import time
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000660 print(n, 'times', func.__name__)
Raymond Hettingerb98154e2003-05-24 17:26:02 +0000661 total = 0.0
Tim Peters0c9886d2001-01-15 01:18:21 +0000662 sqsum = 0.0
663 smallest = 1e10
664 largest = -1e10
665 t0 = time.time()
666 for i in range(n):
Raymond Hettinger62297132003-08-30 01:24:19 +0000667 x = func(*args)
Raymond Hettingerb98154e2003-05-24 17:26:02 +0000668 total += x
Tim Peters0c9886d2001-01-15 01:18:21 +0000669 sqsum = sqsum + x*x
670 smallest = min(x, smallest)
671 largest = max(x, largest)
672 t1 = time.time()
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000673 print(round(t1-t0, 3), 'sec,', end=' ')
Raymond Hettingerb98154e2003-05-24 17:26:02 +0000674 avg = total/n
Tim Petersd7b5e882001-01-25 03:36:26 +0000675 stddev = _sqrt(sqsum/n - avg*avg)
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000676 print('avg %g, stddev %g, min %g, max %g' % \
677 (avg, stddev, smallest, largest))
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000678
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000679
680def _test(N=2000):
Raymond Hettinger62297132003-08-30 01:24:19 +0000681 _test_generator(N, random, ())
682 _test_generator(N, normalvariate, (0.0, 1.0))
683 _test_generator(N, lognormvariate, (0.0, 1.0))
684 _test_generator(N, vonmisesvariate, (0.0, 1.0))
685 _test_generator(N, gammavariate, (0.01, 1.0))
686 _test_generator(N, gammavariate, (0.1, 1.0))
687 _test_generator(N, gammavariate, (0.1, 2.0))
688 _test_generator(N, gammavariate, (0.5, 1.0))
689 _test_generator(N, gammavariate, (0.9, 1.0))
690 _test_generator(N, gammavariate, (1.0, 1.0))
691 _test_generator(N, gammavariate, (2.0, 1.0))
692 _test_generator(N, gammavariate, (20.0, 1.0))
693 _test_generator(N, gammavariate, (200.0, 1.0))
694 _test_generator(N, gauss, (0.0, 1.0))
695 _test_generator(N, betavariate, (3.0, 3.0))
Christian Heimesfe337bf2008-03-23 21:54:12 +0000696 _test_generator(N, triangular, (0.0, 1.0, 1.0/3.0))
Tim Peterscd804102001-01-25 20:25:57 +0000697
Tim Peters715c4c42001-01-26 22:56:56 +0000698# Create one instance, seeded from current time, and export its methods
Raymond Hettinger40f62172002-12-29 23:03:38 +0000699# as module-level functions. The functions share state across all uses
700#(both in the user's code and in the Python libraries), but that's fine
701# for most programs and is easier for the casual user than making them
702# instantiate their own Random() instance.
703
Tim Petersd7b5e882001-01-25 03:36:26 +0000704_inst = Random()
705seed = _inst.seed
706random = _inst.random
707uniform = _inst.uniform
Christian Heimesfe337bf2008-03-23 21:54:12 +0000708triangular = _inst.triangular
Tim Petersd7b5e882001-01-25 03:36:26 +0000709randint = _inst.randint
710choice = _inst.choice
711randrange = _inst.randrange
Raymond Hettingerf24eb352002-11-12 17:41:57 +0000712sample = _inst.sample
Tim Petersd7b5e882001-01-25 03:36:26 +0000713shuffle = _inst.shuffle
714normalvariate = _inst.normalvariate
715lognormvariate = _inst.lognormvariate
Tim Petersd7b5e882001-01-25 03:36:26 +0000716expovariate = _inst.expovariate
717vonmisesvariate = _inst.vonmisesvariate
718gammavariate = _inst.gammavariate
Tim Petersd7b5e882001-01-25 03:36:26 +0000719gauss = _inst.gauss
720betavariate = _inst.betavariate
721paretovariate = _inst.paretovariate
722weibullvariate = _inst.weibullvariate
723getstate = _inst.getstate
724setstate = _inst.setstate
Raymond Hettinger2f726e92003-10-05 09:09:15 +0000725getrandbits = _inst.getrandbits
Tim Petersd7b5e882001-01-25 03:36:26 +0000726
Guido van Rossumff03b1a1994-03-09 12:55:02 +0000727if __name__ == '__main__':
Tim Petersd7b5e882001-01-25 03:36:26 +0000728 _test()