cpython-lru_cache-weakref: Lib/random.py annotate

annotate Lib/random.py @ 38664:7619216bbc19 2.4

Bug #1502728: Correctly link against librt library on HP-UX. (backport from rev. 46743)

author	Georg Brandl <georg@python.org>
date	Thu, 08 Jun 2006 12:54:16 +0000
parents	f05bd98d935d
children	195a0d3eecd4

rev	line source
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	1 """Random variable generators.
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	2
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	3 integers
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	4 --------
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	5 uniform within range
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	6
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	7 sequences
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	8 ---------
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	9 pick random element
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	10 pick random sample
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	11 generate random permutation
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	12
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	13 distributions on the real line:
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	14 ------------------------------
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	15 uniform
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	16 normal (Gaussian)
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	17 lognormal
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	18 negative exponential
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	19 gamma
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	20 beta
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	21 pareto
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	22 Weibull
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	23
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	24 distributions on the circle (angles 0 to 2pi)
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	25 ---------------------------------------------
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	26 circular uniform
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	27 von Mises
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	28
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	29 General notes on the underlying Mersenne Twister core generator:
16272 835e9dd54bfb The combo of getstate/setstate/jumpahead is very powerful, but needs Tim Peters <tim.peters@gmail.com> parents: 16271 diff changeset	30
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	31 * The period is 2**19937-1.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	32 * It is one of the most extensively tested generators in existence
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	33 * Without a direct way to compute N steps forward, the
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	34 semantics of jumpahead(n) are weakened to simply jump
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	35 to another distant state and rely on the large period
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	36 to avoid overlapping sequences.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	37 * The random() method is implemented in C, executes in
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	38 a single Python step, and is, therefore, threadsafe.
16272 835e9dd54bfb The combo of getstate/setstate/jumpahead is very powerful, but needs Tim Peters <tim.peters@gmail.com> parents: 16271 diff changeset	39
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	40 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	41
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	42 from warnings import warn as _warn
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	43 from types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	44 from math import log as _log, exp as _exp, pi as _pi, e as _e
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	45 from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
33409 8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	46 from os import urandom as _urandom
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	47 from binascii import hexlify as _hexlify
8455 af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results, Guido van Rossum <guido@python.org> parents: 8393 diff changeset	48
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	49 __all__ = ["Random","seed","random","uniform","randint","choice","sample",
16613 f68dbffff927 bunch more __all__ lists Skip Montanaro <skip@pobox.com> parents: 16386 diff changeset	50 "randrange","shuffle","normalvariate","lognormvariate",
30068 171814f5dcc6 Removed deprecated functions Raymond Hettinger <python@rcn.com> parents: 29586 diff changeset	51 "expovariate","vonmisesvariate","gammavariate",
171814f5dcc6 Removed deprecated functions Raymond Hettinger <python@rcn.com> parents: 29586 diff changeset	52 "gauss","betavariate","paretovariate","weibullvariate",
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	53 "getstate","setstate","jumpahead", "WichmannHill", "getrandbits",
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	54 "SystemRandom"]
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	55
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	56 NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	57 TWOPI = 2.0*_pi
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	58 LOG4 = _log(4.0)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	59 SG_MAGICCONST = 1.0 + _log(4.5)
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	60 BPF = 53 # Number of bits in a float
33350 c44f083465f9 HardwareRandom: Go back to multiplying by 2*-BPF instead of using Tim Peters <tim.peters@gmail.com>* parents: 33349 diff changeset	61 RECIP_BPF = 2**-BPF
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	62
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	63
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	64 # Translated by Guido van Rossum from C source provided by
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	65 # Adrian Baddeley. Adapted by Raymond Hettinger for use with
33349 ddba154c0e00 Take advantage of the math library's ldexp for assembling a float by Raymond Hettinger <python@rcn.com> parents: 33329 diff changeset	66 # the Mersenne Twister and os.urandom() core generators.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	67
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	68 import _random
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	69
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	70 class Random(_random.Random):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	71 """Random number generator base class used by bound module functions.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	72
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	73 Used to instantiate instances of Random to get generators that don't
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	74 share state. Especially useful for multi-threaded programs, creating
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	75 a different instance of Random for each thread, and using the jumpahead()
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	76 method to ensure that the generated sequences seen by each thread don't
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	77 overlap.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	78
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	79 Class Random can also be subclassed if you want to use a different basic
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	80 generator of your own devising: in that case, override the following
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	81 methods: random(), seed(), getstate(), setstate() and jumpahead().
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	82 Optionally, implement a getrandombits() method so that randrange()
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	83 can cover arbitrarily large ranges.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	84
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	85 """
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	86
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	87 VERSION = 2 # used by getstate/setstate
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	88
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	89 def __init__(self, x=None):
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	90 """Initialize an instance.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	91
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	92 Optional argument x controls seeding, as for Random.seed().
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	93 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	94
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	95 self.seed(x)
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	96 self.gauss_next = None
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	97
16379 5f0683a69efc Change random.seed() so that it can get at the full range of possible Tim Peters <tim.peters@gmail.com> parents: 16292 diff changeset	98 def seed(self, a=None):
5f0683a69efc Change random.seed() so that it can get at the full range of possible Tim Peters <tim.peters@gmail.com> parents: 16292 diff changeset	99 """Initialize internal state from hashable object.
5f0683a69efc Change random.seed() so that it can get at the full range of possible Tim Peters <tim.peters@gmail.com> parents: 16292 diff changeset	100
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	101 None or no argument seeds from current time or from an operating
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	102 system specific randomness source if available.
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	103
16386 c2555b4f38a3 Repaired a docstring. Tim Peters <tim.peters@gmail.com> parents: 16379 diff changeset	104 If a is not None or an int or long, hash(a) is used instead.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	105 """
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	106
30114 9f6e2dee1892 SF bug #778964: bad seed in python 2.3 random Raymond Hettinger <python@rcn.com> parents: 30068 diff changeset	107 if a is None:
33409 8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	108 try:
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	109 a = long(_hexlify(_urandom(16)), 16)
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	110 except NotImplementedError:
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	111 import time
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	112 a = long(time.time() * 256) # use fractional seconds
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	113
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	114 super(Random, self).seed(a)
23380 9be01b7b6c80 random.gauss() uses a piece of hidden state used by nothing else, Tim Peters <tim.peters@gmail.com> parents: 23023 diff changeset	115 self.gauss_next = None
9be01b7b6c80 random.gauss() uses a piece of hidden state used by nothing else, Tim Peters <tim.peters@gmail.com> parents: 23023 diff changeset	116
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	117 def getstate(self):
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	118 """Return internal state; can be passed to setstate() later."""
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	119 return self.VERSION, super(Random, self).getstate(), self.gauss_next
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	120
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	121 def setstate(self, state):
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	122 """Restore internal state from object returned by getstate()."""
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	123 version = state[0]
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	124 if version == 2:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	125 version, internalstate, self.gauss_next = state
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	126 super(Random, self).setstate(internalstate)
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	127 else:
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	128 raise ValueError("state with version %s passed to "
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	129 "Random.setstate() of version %s" %
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	130 (version, self.VERSION))
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	131
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	132 ## ---- Methods below this point do not need to be overridden when
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	133 ## ---- subclassing for the purpose of using a different core generator.
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	134
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	135 ## -------------------- pickle support -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	136
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	137 def __getstate__(self): # for pickle
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	138 return self.getstate()
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	139
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	140 def __setstate__(self, state): # for pickle
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	141 self.setstate(state)
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	142
29586 8b163370372d SF bug #759889: Pickling of Random is broken Raymond Hettinger <python@rcn.com> parents: 29539 diff changeset	143 def __reduce__(self):
8b163370372d SF bug #759889: Pickling of Random is broken Raymond Hettinger <python@rcn.com> parents: 29539 diff changeset	144 return self.__class__, (), self.getstate()
8b163370372d SF bug #759889: Pickling of Random is broken Raymond Hettinger <python@rcn.com> parents: 29539 diff changeset	145
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	146 ## -------------------- integer methods -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	147
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	148 def randrange(self, start, stop=None, step=1, int=int, default=None,
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	149 maxwidth=1L<<BPF):
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	150 """Choose a random item from range(start, stop[, step]).
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	151
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	152 This fixes the problem with randint() which includes the
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	153 endpoint; in Python this is usually not what you want.
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	154 Do not supply the 'int', 'default', and 'maxwidth' arguments.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	155 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	156
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	157 # This code is a bit messy to make it fast for the
24861 4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	158 # common case while still doing adequate error checking.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	159 istart = int(start)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	160 if istart != start:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	161 raise ValueError, "non-integer arg 1 for randrange()"
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	162 if stop is default:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	163 if istart > 0:
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	164 if istart >= maxwidth:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	165 return self._randbelow(istart)
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	166 return int(self.random() * istart)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	167 raise ValueError, "empty range for randrange()"
24861 4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	168
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	169 # stop argument supplied.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	170 istop = int(stop)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	171 if istop != stop:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	172 raise ValueError, "non-integer stop for randrange()"
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	173 width = istop - istart
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	174 if step == 1 and width > 0:
29539 fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	175 # Note that
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	176 # int(istart + self.random()*width)
29539 fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	177 # instead would be incorrect. For example, consider istart
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	178 # = -2 and istop = 0. Then the guts would be in
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	179 # -2.0 to 0.0 exclusive on both ends (ignoring that random()
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	180 # might return 0.0), and because int() truncates toward 0, the
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	181 # final result would be -1 or 0 (instead of -2 or -1).
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	182 # istart + int(self.random()*width)
29539 fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	183 # would also be incorrect, for a subtler reason: the RHS
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	184 # can return a long, and then randrange() would also return
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	185 # a long, but we're supposed to return an int (for backward
fafb6eb0f97e randrange(): Repaired my overly optimistic rewrite, and added comments Tim Peters <tim.peters@gmail.com> parents: 29538 diff changeset	186 # compatibility).
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	187
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	188 if width >= maxwidth:
31389 aca1ce1b4b61 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 30865 diff changeset	189 return int(istart + self._randbelow(width))
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	190 return int(istart + int(self.random()*width))
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	191 if step == 1:
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	192 raise ValueError, "empty range for randrange() (%d,%d, %d)" % (istart, istop, width)
24861 4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	193
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	194 # Non-unit step argument supplied.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	195 istep = int(step)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	196 if istep != step:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	197 raise ValueError, "non-integer step for randrange()"
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	198 if istep > 0:
33597 355b15e4a4da Use floor division operator. Raymond Hettinger <python@rcn.com> parents: 33481 diff changeset	199 n = (width + istep - 1) // istep
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	200 elif istep < 0:
33597 355b15e4a4da Use floor division operator. Raymond Hettinger <python@rcn.com> parents: 33481 diff changeset	201 n = (width + istep + 1) // istep
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	202 else:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	203 raise ValueError, "zero step for randrange()"
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	204
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	205 if n <= 0:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	206 raise ValueError, "empty range for randrange()"
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	207
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	208 if n >= maxwidth:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	209 return istart + self._randbelow(n)
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	210 return istart + istepint(self.random() n)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	211
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	212 def randint(self, a, b):
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	213 """Return random integer in range [a, b], including both end points.
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	214 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	215
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	216 return self.randrange(a, b+1)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	217
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	218 def _randbelow(self, n, _log=_log, int=int, _maxwidth=1L<<BPF,
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	219 _Method=_MethodType, _BuiltinMethod=_BuiltinMethodType):
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	220 """Return a random int in the range [0,n)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	221
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	222 Handles the case where n has more bits than returned
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	223 by a single call to the underlying generator.
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	224 """
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	225
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	226 try:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	227 getrandbits = self.getrandbits
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	228 except AttributeError:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	229 pass
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	230 else:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	231 # Only call self.getrandbits if the original random() builtin method
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	232 # has not been overridden or if a new getrandbits() was supplied.
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	233 # This assures that the two methods correspond.
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	234 if type(self.random) is _BuiltinMethod or type(getrandbits) is _Method:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	235 k = int(1.00001 + _log(n-1, 2.0)) # 2k > n-1 > 2(k-2)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	236 r = getrandbits(k)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	237 while r >= n:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	238 r = getrandbits(k)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	239 return r
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	240 if n >= _maxwidth:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	241 _warn("Underlying random() generator does not supply \n"
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	242 "enough bits to choose from a population range this large")
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	243 return int(self.random() * n)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	244
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	245 ## -------------------- sequence methods -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	246
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	247 def choice(self, seq):
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	248 """Choose a random element from a non-empty sequence."""
32287 854a2417d35e Fix typo in comment. Raymond Hettinger <python@rcn.com> parents: 32255 diff changeset	249 return seq[int(self.random() * len(seq))] # raises IndexError if seq is empty
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	250
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	251 def shuffle(self, x, random=None, int=int):
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	252 """x, random=random.random -> shuffle list x in place; return None.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	253
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	254 Optional arg random is a 0-argument function returning a random
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	255 float in [0.0, 1.0); by default, the standard random.random.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	256
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	257 Note that for even rather small len(x), the total number of
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	258 permutations of x is larger than the period of most random number
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	259 generators; this implies that "most" permutations of a long
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	260 sequence can never be generated.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	261 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	262
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	263 if random is None:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	264 random = self.random
30865 41c4e143e6e6 Implement and apply PEP 322, reverse iteration Raymond Hettinger <python@rcn.com> parents: 30680 diff changeset	265 for i in reversed(xrange(1, len(x))):
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	266 # pick an element in x[:i+1] with which to exchange x[i]
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	267 j = int(random() * (i+1))
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	268 x[i], x[j] = x[j], x[i]
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	269
29430 b80a22250e4f SF bug #753602: random.sample not properly documented Raymond Hettinger <python@rcn.com> parents: 29250 diff changeset	270 def sample(self, population, k):
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	271 """Chooses k unique random elements from a population sequence.
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	272
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	273 Returns a new list containing elements from the population while
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	274 leaving the original population unchanged. The resulting list is
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	275 in selection order so that all sub-slices will also be valid random
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	276 samples. This allows raffle winners (the sample) to be partitioned
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	277 into grand prize and second place winners (the subslices).
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	278
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	279 Members of the population need not be hashable or unique. If the
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	280 population contains repeats, then each occurrence is a possible
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	281 selection in the sample.
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	282
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	283 To choose a sample in a range of integers, use xrange as an argument.
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	284 This is especially fast and space efficient for sampling from a
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	285 large population: sample(xrange(10000000), 60)
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	286 """
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	287
37361 f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	288 # XXX Although the documentation says `population` is "a sequence",
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	289 # XXX attempts are made to cater to any iterable with a __len__
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	290 # XXX method. This has had mixed success. Examples from both
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	291 # XXX sides: sets work fine, and should become officially supported;
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	292 # XXX dicts are much harder, and have failed in various subtle
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	293 # XXX ways across attempts. Support for mapping types should probably
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	294 # XXX be dropped (and users should pass mapping.keys() or .values()
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	295 # XXX explicitly).
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	296
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	297 # Sampling without replacement entails tracking either potential
27080 2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	298 # selections (the pool) in a list or previous selections in a
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	299 # dictionary.
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	300
31578 8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	301 # When the number of selections is small compared to the
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	302 # population, then tracking selections is efficient, requiring
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	303 # only a small dictionary and an occasional reselection. For
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	304 # a larger number of selections, the pool tracking method is
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	305 # preferred since the list takes less space than the
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	306 # dictionary and it doesn't suffer from frequent reselections.
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	307
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	308 n = len(population)
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	309 if not 0 <= k <= n:
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	310 raise ValueError, "sample larger than population"
27080 2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	311 random = self.random
29430 b80a22250e4f SF bug #753602: random.sample not properly documented Raymond Hettinger <python@rcn.com> parents: 29250 diff changeset	312 _int = int
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	313 result = [None] * k
37361 f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	314 if n < 6 * k or hasattr(population, "keys"):
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	315 # An n-length list is smaller than a k-length set, or this is a
f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	316 # mapping type so the other algorithm wouldn't work.
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	317 pool = list(population)
42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	318 for i in xrange(k): # invariant: non-selected at [0,n-i)
29430 b80a22250e4f SF bug #753602: random.sample not properly documented Raymond Hettinger <python@rcn.com> parents: 29250 diff changeset	319 j = _int(random() * (n-i))
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	320 result[i] = pool[j]
27080 2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	321 pool[j] = pool[n-i-1] # move non-selected item into vacancy
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	322 else:
30346 aaf6b6a8510b SF bug #801342: Bug (documentation or real, your choice) in random.sample. Raymond Hettinger <python@rcn.com> parents: 30243 diff changeset	323 try:
37292 60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	324 selected = {}
60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	325 for i in xrange(k):
60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	326 j = _int(random() * n)
60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	327 while j in selected:
60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	328 j = _int(random() * n)
60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	329 result[i] = selected[j] = population[j]
37361 f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	330 except (TypeError, KeyError): # handle (at least) sets
37292 60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	331 if isinstance(population, list):
60be3f39a72b SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35577 diff changeset	332 raise
37361 f05bd98d935d Merge rev 43511 from the trunk. Tim Peters <tim.peters@gmail.com> parents: 37292 diff changeset	333 return self.sample(tuple(population), k)
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	334 return result
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	335
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	336 ## -------------------- real-valued distributions -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	337
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	338 ## -------------------- uniform distribution -------------------
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	339
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	340 def uniform(self, a, b):
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	341 """Get a random number in the range [a, b)."""
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	342 return a + (b-a) * self.random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	343
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	344 ## -------------------- normal distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	345
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	346 def normalvariate(self, mu, sigma):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	347 """Normal distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	348
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	349 mu is the mean, and sigma is the standard deviation.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	350
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	351 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	352 # mu = mean, sigma = standard deviation
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	353
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	354 # Uses Kinderman and Monahan method. Reference: Kinderman,
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	355 # A.J. and Monahan, J.F., "Computer generation of random
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	356 # variables using the ratio of uniform deviates", ACM Trans
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	357 # Math Software, 3, (1977), pp257-260.
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	358
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	359 random = self.random
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	360 while 1:
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	361 u1 = random()
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	362 u2 = 1.0 - random()
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	363 z = NV_MAGICCONST*(u1-0.5)/u2
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	364 zz = z*z/4.0
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	365 if zz <= -_log(u2):
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	366 break
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	367 return mu + z*sigma
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	368
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	369 ## -------------------- lognormal distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	370
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	371 def lognormvariate(self, mu, sigma):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	372 """Log normal distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	373
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	374 If you take the natural logarithm of this distribution, you'll get a
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	375 normal distribution with mean mu and standard deviation sigma.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	376 mu can have any value, and sigma must be greater than zero.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	377
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	378 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	379 return _exp(self.normalvariate(mu, sigma))
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	380
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	381 ## -------------------- exponential distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	382
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	383 def expovariate(self, lambd):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	384 """Exponential distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	385
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	386 lambd is 1.0 divided by the desired mean. (The parameter would be
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	387 called "lambda", but that is a reserved word in Python.) Returned
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	388 values range from 0 to positive infinity.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	389
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	390 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	391 # lambd: rate lambd = 1/mean
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	392 # ('lambda' is a Python reserved word)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	393
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	394 random = self.random
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	395 u = random()
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	396 while u <= 1e-7:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	397 u = random()
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	398 return -_log(u)/lambd
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	399
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	400 ## -------------------- von Mises distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	401
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	402 def vonmisesvariate(self, mu, kappa):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	403 """Circular data distribution.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	404
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	405 mu is the mean angle, expressed in radians between 0 and 2*pi, and
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	406 kappa is the concentration parameter, which must be greater than or
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	407 equal to zero. If kappa is equal to zero, this distribution reduces
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	408 to a uniform random angle over the range 0 to 2*pi.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	409
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	410 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	411 # mu: mean angle (in radians between 0 and 2*pi)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	412 # kappa: concentration parameter kappa (>= 0)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	413 # if kappa = 0 generate uniform random angle
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	414
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	415 # Based upon an algorithm published in: Fisher, N.I.,
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	416 # "Statistical Analysis of Circular Data", Cambridge
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	417 # University Press, 1993.
7881 6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and Guido van Rossum <guido@python.org> parents: 7412 diff changeset	418
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	419 # Thanks to Magnus Kessler for a correction to the
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	420 # implementation of step 4.
7881 6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and Guido van Rossum <guido@python.org> parents: 7412 diff changeset	421
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	422 random = self.random
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	423 if kappa <= 1e-6:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	424 return TWOPI * random()
7881 6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and Guido van Rossum <guido@python.org> parents: 7412 diff changeset	425
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	426 a = 1.0 + _sqrt(1.0 + 4.0 * kappa * kappa)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	427 b = (a - _sqrt(2.0 * a))/(2.0 * kappa)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	428 r = (1.0 + b * b)/(2.0 * b)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	429
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	430 while 1:
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	431 u1 = random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	432
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	433 z = _cos(_pi * u1)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	434 f = (1.0 + r * z)/(r + z)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	435 c = kappa * (r - f)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	436
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	437 u2 = random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	438
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	439 if u2 < c * (2.0 - c) or u2 <= c * _exp(1.0 - c):
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	440 break
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	441
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	442 u3 = random()
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	443 if u3 > 0.5:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	444 theta = (mu % TWOPI) + _acos(f)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	445 else:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	446 theta = (mu % TWOPI) - _acos(f)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	447
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	448 return theta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	449
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	450 ## -------------------- gamma distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	451
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	452 def gammavariate(self, alpha, beta):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	453 """Gamma distribution. Not the gamma function!
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	454
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	455 Conditions on the parameters are alpha > 0 and beta > 0.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	456
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	457 """
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	458
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	459 # alpha > 0, beta > 0, mean is alphabeta, variance is alphabeta**2
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	460
23451 273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	461 # Warning: a few older sources define the gamma distribution in terms
273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	462 # of alpha > -1.0
273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	463 if alpha <= 0.0 or beta <= 0.0:
273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	464 raise ValueError, 'gammavariate: alpha and beta must be > 0.0'
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	465
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	466 random = self.random
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	467 if alpha > 1.0:
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	468
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	469 # Uses R.C.H. Cheng, "The generation of Gamma
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	470 # variables with non-integral shape parameters",
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	471 # Applied Statistics, (1977), 26, No. 1, p71-74
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	472
23442 b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	473 ainv = _sqrt(2.0 * alpha - 1.0)
b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	474 bbb = alpha - LOG4
b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	475 ccc = alpha + ainv
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	476
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	477 while 1:
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	478 u1 = random()
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	479 if not 1e-7 < u1 < .9999999:
90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	480 continue
90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	481 u2 = 1.0 - random()
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	482 v = _log(u1/(1.0-u1))/ainv
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	483 x = alpha*_exp(v)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	484 z = u1u1u2
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	485 r = bbb+ccc*v-x
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	486 if r + SG_MAGICCONST - 4.5*z >= 0.0 or r >= _log(z):
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	487 return x * beta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	488
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	489 elif alpha == 1.0:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	490 # expovariate(1)
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	491 u = random()
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	492 while u <= 1e-7:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	493 u = random()
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	494 return -_log(u) * beta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	495
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	496 else: # alpha is between 0 and 1 (exclusive)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	497
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	498 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	499
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	500 while 1:
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	501 u = random()
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	502 b = (_e + alpha)/_e
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	503 p = b*u
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	504 if p <= 1.0:
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	505 x = p ** (1.0/alpha)
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	506 else:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	507 x = -_log((b-p)/alpha)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	508 u1 = random()
35577 5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	509 if p > 1.0:
5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	510 if u1 <= x ** (alpha - 1.0):
5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	511 break
5a6c483ed689 Sync-up with head except for 1.72 which is Py2.5 specific. Raymond Hettinger <python@rcn.com> parents: 33597 diff changeset	512 elif u1 <= _exp(-x):
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	513 break
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	514 return x * beta
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	515
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	516 ## -------------------- Gauss (faster alternative) --------------------
1576 695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate(); Guido van Rossum <guido@python.org> parents: 1575 diff changeset	517
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	518 def gauss(self, mu, sigma):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	519 """Gaussian distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	520
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	521 mu is the mean, and sigma is the standard deviation. This is
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	522 slightly faster than the normalvariate() function.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	523
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	524 Not thread-safe without a lock around calls.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	525
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	526 """
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	527
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	528 # When x and y are two variables from [0, 1), uniformly
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	529 # distributed, then
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	530 #
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	531 # cos(2pix)sqrt(-2log(1-y))
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	532 # sin(2pix)sqrt(-2log(1-y))
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	533 #
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	534 # are two independent variables with normal distribution
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	535 # (mu = 0, sigma = 1).
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	536 # (Lambert Meertens)
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	537 # (corrected version; bug discovered by Mike Miller, fixed by LM)
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	538
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	539 # Multithreading note: When two threads call this function
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	540 # simultaneously, it is possible that they will receive the
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	541 # same return value. The window is very small though. To
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	542 # avoid this, you have to use a lock around all calls. (I
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	543 # didn't want to slow this down in the serial case by using a
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	544 # lock here.)
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	545
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	546 random = self.random
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	547 z = self.gauss_next
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	548 self.gauss_next = None
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	549 if z is None:
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	550 x2pi = random() * TWOPI
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	551 g2rad = _sqrt(-2.0 * _log(1.0 - random()))
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	552 z = _cos(x2pi) * g2rad
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	553 self.gauss_next = _sin(x2pi) * g2rad
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	554
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	555 return mu + z*sigma
1576 695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate(); Guido van Rossum <guido@python.org> parents: 1575 diff changeset	556
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	557 ## -------------------- beta --------------------
16271 7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	558 ## See
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	559 ## http://sourceforge.net/bugs/?func=detailbug&bug_id=130030&group_id=5470
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	560 ## for Ivan Frohne's insightful analysis of why the original implementation:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	561 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	562 ## def betavariate(self, alpha, beta):
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	563 ## # Discrete Event Simulation in C, pp 87-88.
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	564 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	565 ## y = self.expovariate(alpha)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	566 ## z = self.expovariate(1.0/beta)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	567 ## return z/(y+z)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	568 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	569 ## was dead wrong, and how it probably got that way.
1576 695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate(); Guido van Rossum <guido@python.org> parents: 1575 diff changeset	570
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	571 def betavariate(self, alpha, beta):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	572 """Beta distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	573
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	574 Conditions on the parameters are alpha > -1 and beta} > -1.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	575 Returned values range between 0 and 1.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	576
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	577 """
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	578
16271 7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	579 # This version due to Janne Sinkkonen, and matches all the std
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	580 # texts (e.g., Knuth Vol 2 Ed 3 pg 134 "the beta distribution").
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	581 y = self.gammavariate(alpha, 1.)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	582 if y == 0:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	583 return 0.0
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	584 else:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	585 return y / (y + self.gammavariate(beta, 1.))
1576 695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate(); Guido van Rossum <guido@python.org> parents: 1575 diff changeset	586
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	587 ## -------------------- Pareto --------------------
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	588
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	589 def paretovariate(self, alpha):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	590 """Pareto distribution. alpha is the shape parameter."""
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	591 # Jain, pg. 495
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	592
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	593 u = 1.0 - self.random()
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	594 return 1.0 / pow(u, 1.0/alpha)
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	595
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	596 ## -------------------- Weibull --------------------
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	597
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	598 def weibullvariate(self, alpha, beta):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	599 """Weibull distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	600
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	601 alpha is the scale parameter and beta is the shape parameter.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	602
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	603 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	604 # Jain, pg. 499; bug fix courtesy Bill Arms
11200 bca2d14f3e36 Add Tim Peters' shuffle() algorithm. Guido van Rossum <guido@python.org> parents: 8802 diff changeset	605
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	606 u = 1.0 - self.random()
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	607 return alpha * pow(-_log(u), 1.0/beta)
11200 bca2d14f3e36 Add Tim Peters' shuffle() algorithm. Guido van Rossum <guido@python.org> parents: 8802 diff changeset	608
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	609 ## -------------------- Wichmann-Hill -------------------
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	610
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	611 class WichmannHill(Random):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	612
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	613 VERSION = 1 # used by getstate/setstate
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	614
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	615 def seed(self, a=None):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	616 """Initialize internal state from hashable object.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	617
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	618 None or no argument seeds from current time or from an operating
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	619 system specific randomness source if available.
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	620
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	621 If a is not None or an int or long, hash(a) is used instead.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	622
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	623 If a is an int or long, a is used directly. Distinct values between
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	624 0 and 27814431486575L inclusive are guaranteed to yield distinct
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	625 internal states (this guarantee is specific to the default
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	626 Wichmann-Hill generator).
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	627 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	628
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	629 if a is None:
33409 8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	630 try:
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	631 a = long(_hexlify(_urandom(16)), 16)
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	632 except NotImplementedError:
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	633 import time
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	634 a = long(time.time() * 256) # use fractional seconds
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	635
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	636 if not isinstance(a, (int, long)):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	637 a = hash(a)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	638
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	639 a, x = divmod(a, 30268)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	640 a, y = divmod(a, 30306)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	641 a, z = divmod(a, 30322)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	642 self._seed = int(x)+1, int(y)+1, int(z)+1
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	643
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	644 self.gauss_next = None
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	645
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	646 def random(self):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	647 """Get the next random number in the range [0.0, 1.0)."""
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	648
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	649 # Wichman-Hill random number generator.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	650 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	651 # Wichmann, B. A. & Hill, I. D. (1982)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	652 # Algorithm AS 183:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	653 # An efficient and portable pseudo-random number generator
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	654 # Applied Statistics 31 (1982) 188-190
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	655 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	656 # see also:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	657 # Correction to Algorithm AS 183
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	658 # Applied Statistics 33 (1984) 123
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	659 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	660 # McLeod, A. I. (1985)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	661 # A remark on Algorithm AS 183
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	662 # Applied Statistics 34 (1985),198-200
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	663
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	664 # This part is thread-unsafe:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	665 # BEGIN CRITICAL SECTION
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	666 x, y, z = self._seed
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	667 x = (171 * x) % 30269
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	668 y = (172 * y) % 30307
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	669 z = (170 * z) % 30323
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	670 self._seed = x, y, z
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	671 # END CRITICAL SECTION
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	672
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	673 # Note: on a platform using IEEE-754 double arithmetic, this can
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	674 # never return 0.0 (asserted by Tim; proof too long for a comment).
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	675 return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	676
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	677 def getstate(self):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	678 """Return internal state; can be passed to setstate() later."""
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	679 return self.VERSION, self._seed, self.gauss_next
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	680
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	681 def setstate(self, state):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	682 """Restore internal state from object returned by getstate()."""
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	683 version = state[0]
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	684 if version == 1:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	685 version, self._seed, self.gauss_next = state
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	686 else:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	687 raise ValueError("state with version %s passed to "
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	688 "Random.setstate() of version %s" %
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	689 (version, self.VERSION))
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	690
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	691 def jumpahead(self, n):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	692 """Act as if n calls to random() were made, but quickly.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	693
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	694 n is an int, greater than or equal to 0.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	695
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	696 Example use: If you have 2 threads and know that each will
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	697 consume no more than a million random numbers, create two Random
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	698 objects r1 and r2, then do
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	699 r2.setstate(r1.getstate())
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	700 r2.jumpahead(1000000)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	701 Then r1 and r2 will use guaranteed-disjoint segments of the full
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	702 period.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	703 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	704
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	705 if not n >= 0:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	706 raise ValueError("n must be >= 0")
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	707 x, y, z = self._seed
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	708 x = int(x * pow(171, n, 30269)) % 30269
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	709 y = int(y * pow(172, n, 30307)) % 30307
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	710 z = int(z * pow(170, n, 30323)) % 30323
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	711 self._seed = x, y, z
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	712
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	713 def __whseed(self, x=0, y=0, z=0):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	714 """Set the Wichmann-Hill seed from (x, y, z).
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	715
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	716 These must be integers in the range [0, 256).
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	717 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	718
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	719 if not type(x) == type(y) == type(z) == int:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	720 raise TypeError('seeds must be integers')
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	721 if not (0 <= x < 256 and 0 <= y < 256 and 0 <= z < 256):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	722 raise ValueError('seeds must be in range(0, 256)')
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	723 if 0 == x == y == z:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	724 # Initialize from current time
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	725 import time
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	726 t = long(time.time() * 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	727 t = int((t&0xffffff) ^ (t>>24))
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	728 t, x = divmod(t, 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	729 t, y = divmod(t, 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	730 t, z = divmod(t, 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	731 # Zero is a poor seed, so substitute 1
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	732 self._seed = (x or 1, y or 1, z or 1)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	733
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	734 self.gauss_next = None
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	735
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	736 def whseed(self, a=None):
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	737 """Seed from hashable object's hash code.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	738
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	739 None or no argument seeds from current time. It is not guaranteed
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	740 that objects with distinct hash codes lead to distinct internal
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	741 states.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	742
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	743 This is obsolete, provided for compatibility with the seed routine
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	744 used prior to Python 2.1. Use the .seed() method instead.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	745 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	746
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	747 if a is None:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	748 self.__whseed()
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	749 return
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	750 a = hash(a)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	751 a, x = divmod(a, 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	752 a, y = divmod(a, 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	753 a, z = divmod(a, 256)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	754 x = (x + a) % 256 or 1
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	755 y = (y + a) % 256 or 1
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	756 z = (z + a) % 256 or 1
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	757 self.__whseed(x, y, z)
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	758
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	759 ## --------------- Operating System Random Source ------------------
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	760
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	761 class SystemRandom(Random):
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	762 """Alternate random number generator using sources provided
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	763 by the operating system (such as /dev/urandom on Unix or
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	764 CryptGenRandom on Windows).
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	765
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	766 Not available on all systems (see os.urandom() for details).
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	767 """
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	768
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	769 def random(self):
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	770 """Get the next random number in the range [0.0, 1.0)."""
33350 c44f083465f9 HardwareRandom: Go back to multiplying by 2*-BPF instead of using Tim Peters <tim.peters@gmail.com>* parents: 33349 diff changeset	771 return (long(_hexlify(_urandom(7)), 16) >> 3) * RECIP_BPF
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	772
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	773 def getrandbits(self, k):
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	774 """getrandbits(k) -> x. Generates a long int with k random bits."""
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	775 if k <= 0:
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	776 raise ValueError('number of bits must be greater than zero')
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	777 if k != int(k):
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	778 raise TypeError('number of bits should be an integer')
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	779 bytes = (k + 7) // 8 # bits / 8 and rounded up
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	780 x = long(_hexlify(_urandom(bytes)), 16)
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	781 return x >> (bytes * 8 - k) # trim excess bits
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	782
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	783 def _stub(self, args, *kwds):
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	784 "Stub method. Not used for a system random number generator."
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	785 return None
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	786 seed = jumpahead = _stub
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	787
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	788 def _notimplemented(self, args, *kwds):
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	789 "Method should not be called for a system random number generator."
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	790 raise NotImplementedError('System entropy source does not have state.')
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	791 getstate = setstate = _notimplemented
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	792
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	793 ## -------------------- test program --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	794
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	795 def _test_generator(n, func, args):
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	796 import time
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	797 print n, 'times', func.__name__
29250 34609fa35b11 'sum' is no longer a good variable name. Use 'total' instead. Raymond Hettinger <python@rcn.com> parents: 27279 diff changeset	798 total = 0.0
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	799 sqsum = 0.0
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	800 smallest = 1e10
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	801 largest = -1e10
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	802 t0 = time.time()
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	803 for i in range(n):
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	804 x = func(*args)
29250 34609fa35b11 'sum' is no longer a good variable name. Use 'total' instead. Raymond Hettinger <python@rcn.com> parents: 27279 diff changeset	805 total += x
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	806 sqsum = sqsum + x*x
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	807 smallest = min(x, smallest)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	808 largest = max(x, largest)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	809 t1 = time.time()
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	810 print round(t1-t0, 3), 'sec,',
29250 34609fa35b11 'sum' is no longer a good variable name. Use 'total' instead. Raymond Hettinger <python@rcn.com> parents: 27279 diff changeset	811 avg = total/n
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	812 stddev = _sqrt(sqsum/n - avg*avg)
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	813 print 'avg %g, stddev %g, min %g, max %g' % \
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	814 (avg, stddev, smallest, largest)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	815
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	816
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	817 def _test(N=2000):
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	818 _test_generator(N, random, ())
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	819 _test_generator(N, normalvariate, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	820 _test_generator(N, lognormvariate, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	821 _test_generator(N, vonmisesvariate, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	822 _test_generator(N, gammavariate, (0.01, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	823 _test_generator(N, gammavariate, (0.1, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	824 _test_generator(N, gammavariate, (0.1, 2.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	825 _test_generator(N, gammavariate, (0.5, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	826 _test_generator(N, gammavariate, (0.9, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	827 _test_generator(N, gammavariate, (1.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	828 _test_generator(N, gammavariate, (2.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	829 _test_generator(N, gammavariate, (20.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	830 _test_generator(N, gammavariate, (200.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	831 _test_generator(N, gauss, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	832 _test_generator(N, betavariate, (3.0, 3.0))
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	833
16292 0501c2a10315 New comment block to Clarify a subtlety. Tim Peters <tim.peters@gmail.com> parents: 16272 diff changeset	834 # Create one instance, seeded from current time, and export its methods
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	835 # as module-level functions. The functions share state across all uses
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	836 #(both in the user's code and in the Python libraries), but that's fine
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	837 # for most programs and is easier for the casual user than making them
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	838 # instantiate their own Random() instance.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	839
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	840 _inst = Random()
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	841 seed = _inst.seed
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	842 random = _inst.random
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	843 uniform = _inst.uniform
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	844 randint = _inst.randint
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	845 choice = _inst.choice
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	846 randrange = _inst.randrange
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	847 sample = _inst.sample
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	848 shuffle = _inst.shuffle
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	849 normalvariate = _inst.normalvariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	850 lognormvariate = _inst.lognormvariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	851 expovariate = _inst.expovariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	852 vonmisesvariate = _inst.vonmisesvariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	853 gammavariate = _inst.gammavariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	854 gauss = _inst.gauss
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	855 betavariate = _inst.betavariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	856 paretovariate = _inst.paretovariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	857 weibullvariate = _inst.weibullvariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	858 getstate = _inst.getstate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	859 setstate = _inst.setstate
16243 9fd96e2455b6 Fix bugs introduced by rewrite (in particular, time-based initialization Tim Peters <tim.peters@gmail.com> parents: 16242 diff changeset	860 jumpahead = _inst.jumpahead
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	861 getrandbits = _inst.getrandbits
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	862
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	863 if __name__ == '__main__':
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	864 _test()

Mercurial > cpython-lru_cache-weakref

annotate Lib/random.py @ 38664:7619216bbc19 2.4