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

annotate Lib/random.py @ 58765:2ba7677bfa95 legacy-trunk

testCopysign was defined twice in test_math; combine the definitions

author	Mark Dickinson <dickinsm@gmail.com>
date	Sat, 06 Feb 2010 23:11:25 +0000
parents	7cf89ed90f9d
children	53cd8ecdce8a

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
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	16 triangular
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	17 normal (Gaussian)
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	18 lognormal
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	19 negative exponential
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	20 gamma
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	21 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	22 pareto
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	23 Weibull
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	24
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	25 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	26 ---------------------------------------------
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	27 circular uniform
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	28 von Mises
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	29
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	30 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	31
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	32 * The period is 2**19937-1.
38732 bf4e485becf3 shuffle() doscstring: Removed warning about sequence length Tim Peters <tim.peters@gmail.com> parents: 37360 diff changeset	33 * It is one of the most extensively tested generators in existence.
bf4e485becf3 shuffle() doscstring: Removed warning about sequence length Tim Peters <tim.peters@gmail.com> parents: 37360 diff changeset	34 * Without a direct way to compute N steps forward, the semantics of
bf4e485becf3 shuffle() doscstring: Removed warning about sequence length Tim Peters <tim.peters@gmail.com> parents: 37360 diff changeset	35 jumpahead(n) are weakened to simply jump to another distant state and rely
bf4e485becf3 shuffle() doscstring: Removed warning about sequence length Tim Peters <tim.peters@gmail.com> parents: 37360 diff changeset	36 on the large period to avoid overlapping sequences.
bf4e485becf3 shuffle() doscstring: Removed warning about sequence length Tim Peters <tim.peters@gmail.com> parents: 37360 diff changeset	37 * The random() method is implemented in C, executes in a single Python step,
bf4e485becf3 shuffle() doscstring: Removed warning about sequence length Tim Peters <tim.peters@gmail.com> parents: 37360 diff changeset	38 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
46030 1d5a11619eca Adopt Nick's suggestion for useful default arguments. Raymond Hettinger <python@rcn.com> parents: 46029 diff changeset	42 from __future__ import division
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	43 from warnings import warn as _warn
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	44 from types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
35359 c5bf5685267b Implement random.sample() using sets instead of dicts. Raymond Hettinger <python@rcn.com> parents: 34942 diff changeset	45 from math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil
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	46 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	47 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	48 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	49
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	50 __all__ = ["Random","seed","random","uniform","randint","choice","sample",
16613 f68dbffff927 bunch more __all__ lists Skip Montanaro <skip@pobox.com> parents: 16386 diff changeset	51 "randrange","shuffle","normalvariate","lognormvariate",
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	52 "expovariate","vonmisesvariate","gammavariate","triangular",
30068 171814f5dcc6 Removed deprecated functions Raymond Hettinger <python@rcn.com> parents: 29586 diff changeset	53 "gauss","betavariate","paretovariate","weibullvariate",
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	54 "getstate","setstate","jumpahead", "WichmannHill", "getrandbits",
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	55 "SystemRandom"]
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	56
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	57 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	58 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	59 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	60 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	61 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	62 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	63
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	64
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	65 # 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	66 # 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	67 # 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	68
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	69 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	70
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	71 class Random(_random.Random):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	72 """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	73
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	74 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	75 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	76 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	77 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	78 overlap.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	79
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	80 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	81 generator of your own devising: in that case, override the following
48100 40e949a68344 getrandombits is actually getrandbits Benjamin Peterson <benjamin@python.org> parents: 46030 diff changeset	82 methods: random(), seed(), getstate(), setstate() and jumpahead().
40e949a68344 getrandombits is actually getrandbits Benjamin Peterson <benjamin@python.org> parents: 46030 diff changeset	83 Optionally, implement a getrandbits() method so that randrange() can cover
40e949a68344 getrandombits is actually getrandbits Benjamin Peterson <benjamin@python.org> parents: 46030 diff changeset	84 arbitrarily large ranges.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	85
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	86 """
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	87
44122 97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	88 VERSION = 3 # 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	89
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 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	91 """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	92
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 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	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
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	96 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	97 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	98
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	99 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	100 """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	101
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	102 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	103 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	104
16386 c2555b4f38a3 Repaired a docstring. Tim Peters <tim.peters@gmail.com> parents: 16379 diff changeset	105 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	106 """
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	107
30114 9f6e2dee1892 SF bug #778964: bad seed in python 2.3 random Raymond Hettinger <python@rcn.com> parents: 30068 diff changeset	108 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	109 try:
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	110 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	111 except NotImplementedError:
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	112 import time
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	113 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	114
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	115 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	116 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	117
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	118 def getstate(self):
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	119 """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	120 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	121
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	122 def setstate(self, state):
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	123 """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	124 version = state[0]
44122 97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	125 if version == 3:
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	126 version, internalstate, self.gauss_next = state
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	127 super(Random, self).setstate(internalstate)
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	128 elif version == 2:
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	129 version, internalstate, self.gauss_next = state
44122 97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	130 # In version 2, the state was saved as signed ints, which causes
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	131 # inconsistencies between 32/64-bit systems. The state is
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	132 # really unsigned 32-bit ints, so we convert negative ints from
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	133 # version 2 to positive longs for version 3.
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	134 try:
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	135 internalstate = tuple( long(x) % (2**32) for x in internalstate )
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	136 except ValueError, e:
97210d863d12 Issue #1727780: Support loading pickles of random.Random objects created Martin v. Löwis <martin@v.loewis.de> parents: 40673 diff changeset	137 raise TypeError, e
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	138 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	139 else:
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	140 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	141 "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	142 (version, self.VERSION))
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	143
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	144 ## ---- 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	145 ## ---- 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	146
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	147 ## -------------------- pickle support -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	148
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	149 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	150 return self.getstate()
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	151
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	152 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	153 self.setstate(state)
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	154
29586 8b163370372d SF bug #759889: Pickling of Random is broken Raymond Hettinger <python@rcn.com> parents: 29539 diff changeset	155 def __reduce__(self):
8b163370372d SF bug #759889: Pickling of Random is broken Raymond Hettinger <python@rcn.com> parents: 29539 diff changeset	156 return self.__class__, (), self.getstate()
8b163370372d SF bug #759889: Pickling of Random is broken Raymond Hettinger <python@rcn.com> parents: 29539 diff changeset	157
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	158 ## -------------------- integer methods -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	159
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	160 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	161 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	162 """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	163
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	164 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	165 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	166 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	167 """
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	168
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	169 # 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	170 # 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	171 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	172 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	173 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	174 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	175 if istart > 0:
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	176 if istart >= maxwidth:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	177 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	178 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	179 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	180
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	181 # 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	182 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	183 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	184 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	185 width = istop - istart
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	186 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	187 # Note that
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	188 # 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	189 # 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	190 # = -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	191 # -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	192 # 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	193 # 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	194 # 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	195 # 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	196 # 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	197 # 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	198 # compatibility).
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	199
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	200 if width >= maxwidth:
31389 aca1ce1b4b61 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 30865 diff changeset	201 return int(istart + self._randbelow(width))
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	202 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	203 if step == 1:
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	204 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	205
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	206 # 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	207 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	208 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	209 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	210 if istep > 0:
33597 355b15e4a4da Use floor division operator. Raymond Hettinger <python@rcn.com> parents: 33481 diff changeset	211 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	212 elif istep < 0:
33597 355b15e4a4da Use floor division operator. Raymond Hettinger <python@rcn.com> parents: 33481 diff changeset	213 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	214 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	215 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	216
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 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	218 raise ValueError, "empty range for randrange()"
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	219
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	220 if n >= maxwidth:
40488 96d533efbe7d Bug #1590891: random.randrange don't return correct value for big number Raymond Hettinger <python@rcn.com> parents: 38732 diff changeset	221 return istart + istep*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	222 return istart + istepint(self.random() n)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	223
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	224 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	225 """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	226 """
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	227
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	228 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	229
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	230 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	231 _Method=_MethodType, _BuiltinMethod=_BuiltinMethodType):
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	232 """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	233
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	234 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	235 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	236 """
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	237
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	238 try:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	239 getrandbits = self.getrandbits
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	240 except AttributeError:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	241 pass
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	242 else:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	243 # 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	244 # 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	245 # This assures that the two methods correspond.
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	246 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	247 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	248 r = getrandbits(k)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	249 while r >= n:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	250 r = getrandbits(k)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	251 return r
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	252 if n >= _maxwidth:
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	253 _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	254 "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	255 return int(self.random() * n)
8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	256
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	257 ## -------------------- sequence methods -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	258
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	259 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	260 """Choose a random element from a non-empty sequence."""
32287 854a2417d35e Fix typo in comment. Raymond Hettinger <python@rcn.com> parents: 32255 diff changeset	261 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	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 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	264 """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	265
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	266 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	267 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	268 """
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
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	270 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	271 random = self.random
30865 41c4e143e6e6 Implement and apply PEP 322, reverse iteration Raymond Hettinger <python@rcn.com> parents: 30680 diff changeset	272 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	273 # 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	274 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	275 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	276
29430 b80a22250e4f SF bug #753602: random.sample not properly documented Raymond Hettinger <python@rcn.com> parents: 29250 diff changeset	277 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	278 """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	279
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	280 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	281 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	282 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	283 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	284 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	285
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	286 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	287 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	288 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	289
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	290 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	291 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	292 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	293 """
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	294
37360 98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	295 # XXX Although the documentation says `population` is "a sequence",
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	296 # XXX attempts are made to cater to any iterable with a __len__
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	297 # XXX method. This has had mixed success. Examples from both
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	298 # XXX sides: sets work fine, and should become officially supported;
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	299 # XXX dicts are much harder, and have failed in various subtle
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	300 # XXX ways across attempts. Support for mapping types should probably
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	301 # XXX be dropped (and users should pass mapping.keys() or .values()
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	302 # XXX explicitly).
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	303
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	304 # Sampling without replacement entails tracking either potential
35359 c5bf5685267b Implement random.sample() using sets instead of dicts. Raymond Hettinger <python@rcn.com> parents: 34942 diff changeset	305 # selections (the pool) in a list or previous selections in a set.
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	306
31578 8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	307 # When the number of selections is small compared to the
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	308 # population, then tracking selections is efficient, requiring
35359 c5bf5685267b Implement random.sample() using sets instead of dicts. Raymond Hettinger <python@rcn.com> parents: 34942 diff changeset	309 # only a small set and an occasional reselection. For
31578 8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	310 # a larger number of selections, the pool tracking method is
8183dd1a4fe6 Reflow long line. Jeremy Hylton <jeremy@alum.mit.edu> parents: 31389 diff changeset	311 # preferred since the list takes less space than the
35359 c5bf5685267b Implement random.sample() using sets instead of dicts. Raymond Hettinger <python@rcn.com> parents: 34942 diff changeset	312 # set 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	313
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	314 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	315 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	316 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	317 random = self.random
29430 b80a22250e4f SF bug #753602: random.sample not properly documented Raymond Hettinger <python@rcn.com> parents: 29250 diff changeset	318 _int = int
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	319 result = [None] * k
35359 c5bf5685267b Implement random.sample() using sets instead of dicts. Raymond Hettinger <python@rcn.com> parents: 34942 diff changeset	320 setsize = 21 # size of a small set minus size of an empty list
c5bf5685267b Implement random.sample() using sets instead of dicts. Raymond Hettinger <python@rcn.com> parents: 34942 diff changeset	321 if k > 5:
35465 3e5c07faab11 Whitespace normalization (via reindent.py). Tim Peters <tim.peters@gmail.com> parents: 35359 diff changeset	322 setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
37360 98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	323 if n <= setsize or hasattr(population, "keys"):
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	324 # An n-length list is smaller than a k-length set, or this is a
98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	325 # mapping type so the other algorithm wouldn't work.
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	326 pool = list(population)
42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	327 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	328 j = _int(random() * (n-i))
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	329 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	330 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	331 else:
30346 aaf6b6a8510b SF bug #801342: Bug (documentation or real, your choice) in random.sample. Raymond Hettinger <python@rcn.com> parents: 30243 diff changeset	332 try:
37293 1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	333 selected = set()
1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	334 selected_add = selected.add
1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	335 for i in xrange(k):
29430 b80a22250e4f SF bug #753602: random.sample not properly documented Raymond Hettinger <python@rcn.com> parents: 29250 diff changeset	336 j = _int(random() * n)
37293 1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	337 while j in selected:
1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	338 j = _int(random() * n)
1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	339 selected_add(j)
1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	340 result[i] = population[j]
37360 98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	341 except (TypeError, KeyError): # handle (at least) sets
37293 1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	342 if isinstance(population, list):
1ca012ce427e SF bug #1460340: random.sample can raise KeyError Raymond Hettinger <python@rcn.com> parents: 35465 diff changeset	343 raise
37360 98251780236d Another crack at bug #1460340: make random.sample(dict) Tim Peters <tim.peters@gmail.com> parents: 37293 diff changeset	344 return self.sample(tuple(population), k)
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	345 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	346
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	347 ## -------------------- real-valued distributions -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	348
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	349 ## -------------------- 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	350
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	351 def uniform(self, a, b):
54708 7cf89ed90f9d Issue 6261: Clarify behavior of random.uniform(). Raymond Hettinger <python@rcn.com> parents: 50786 diff changeset	352 "Get a random number in the range [a, b) or [a, b] depending on rounding."
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	353 return a + (b-a) * self.random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	354
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	355 ## -------------------- triangular --------------------
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	356
46030 1d5a11619eca Adopt Nick's suggestion for useful default arguments. Raymond Hettinger <python@rcn.com> parents: 46029 diff changeset	357 def triangular(self, low=0.0, high=1.0, mode=None):
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	358 """Triangular distribution.
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	359
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	360 Continuous distribution bounded by given lower and upper limits,
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	361 and having a given mode value in-between.
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	362
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	363 http://en.wikipedia.org/wiki/Triangular_distribution
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	364
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	365 """
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	366 u = self.random()
46030 1d5a11619eca Adopt Nick's suggestion for useful default arguments. Raymond Hettinger <python@rcn.com> parents: 46029 diff changeset	367 c = 0.5 if mode is None else (mode - low) / (high - low)
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	368 if u > c:
46030 1d5a11619eca Adopt Nick's suggestion for useful default arguments. Raymond Hettinger <python@rcn.com> parents: 46029 diff changeset	369 u = 1.0 - u
1d5a11619eca Adopt Nick's suggestion for useful default arguments. Raymond Hettinger <python@rcn.com> parents: 46029 diff changeset	370 c = 1.0 - c
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	371 low, high = high, low
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	372 return low + (high - low) * (u * c) ** 0.5
f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	373
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	374 ## -------------------- normal distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	375
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	376 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	377 """Normal distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	378
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	379 mu is the mean, and sigma is the standard deviation.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	380
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	381 """
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	382 # 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	383
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	384 # 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	385 # 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	386 # 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	387 # Math Software, 3, (1977), pp257-260.
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	388
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	389 random = self.random
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	390 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	391 u1 = random()
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	392 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	393 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	394 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	395 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	396 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	397 return mu + z*sigma
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	398
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	399 ## -------------------- lognormal distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	400
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	401 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	402 """Log normal distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	403
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	404 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	405 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	406 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	407
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	408 """
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	409 return _exp(self.normalvariate(mu, sigma))
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	410
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	411 ## -------------------- exponential distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	412
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	413 def expovariate(self, lambd):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	414 """Exponential distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	415
50786 2d453b221bec Merged revisions 68292,68344,68361,68378,68424,68426,68429-68430,68450,68457,68480-68481,68493,68495,68499,68501,68512,68514-68515 via svnmerge from Georg Brandl <georg@python.org> parents: 48100 diff changeset	416 lambd is 1.0 divided by the desired mean. It should be
2d453b221bec Merged revisions 68292,68344,68361,68378,68424,68426,68429-68430,68450,68457,68480-68481,68493,68495,68499,68501,68512,68514-68515 via svnmerge from Georg Brandl <georg@python.org> parents: 48100 diff changeset	417 nonzero. (The parameter would be called "lambda", but that is
2d453b221bec Merged revisions 68292,68344,68361,68378,68424,68426,68429-68430,68450,68457,68480-68481,68493,68495,68499,68501,68512,68514-68515 via svnmerge from Georg Brandl <georg@python.org> parents: 48100 diff changeset	418 a reserved word in Python.) Returned values range from 0 to
2d453b221bec Merged revisions 68292,68344,68361,68378,68424,68426,68429-68430,68450,68457,68480-68481,68493,68495,68499,68501,68512,68514-68515 via svnmerge from Georg Brandl <georg@python.org> parents: 48100 diff changeset	419 positive infinity if lambd is positive, and from negative
2d453b221bec Merged revisions 68292,68344,68361,68378,68424,68426,68429-68430,68450,68457,68480-68481,68493,68495,68499,68501,68512,68514-68515 via svnmerge from Georg Brandl <georg@python.org> parents: 48100 diff changeset	420 infinity to 0 if lambd is negative.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	421
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	422 """
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	423 # 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	424 # ('lambda' is a Python reserved word)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: 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 random = self.random
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	427 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	428 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	429 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	430 return -_log(u)/lambd
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	431
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	432 ## -------------------- von Mises distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	433
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	434 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	435 """Circular data distribution.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	436
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	437 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	438 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	439 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	440 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	441
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	442 """
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	443 # 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	444 # 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	445 # if kappa = 0 generate uniform random angle
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	446
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	447 # 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	448 # "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	449 # 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	450
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	451 # 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	452 # 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	453
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	454 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	455 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	456 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	457
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	458 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	459 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	460 r = (1.0 + b * b)/(2.0 * b)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	461
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	462 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	463 u1 = random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	464
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	465 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	466 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	467 c = kappa * (r - f)
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 u2 = random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	470
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	471 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	472 break
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	473
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	474 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	475 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	476 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	477 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	478 theta = (mu % TWOPI) - _acos(f)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	479
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	480 return theta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	481
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	482 ## -------------------- gamma distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	483
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	484 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	485 """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	486
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	487 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	488
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	489 """
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	490
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	491 # 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	492
23451 273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	493 # 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	494 # of alpha > -1.0
273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	495 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	496 raise ValueError, 'gammavariate: alpha and beta must be > 0.0'
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 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 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	499 if alpha > 1.0:
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	500
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 # 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	502 # 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	503 # Applied Statistics, (1977), 26, No. 1, p71-74
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	504
23442 b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	505 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	506 bbb = alpha - LOG4
b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	507 ccc = alpha + ainv
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	508
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	509 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	510 u1 = random()
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	511 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	512 continue
90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	513 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	514 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	515 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	516 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	517 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	518 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	519 return x * beta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	520
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	521 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	522 # expovariate(1)
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	523 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	524 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	525 u = random()
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	526 return -_log(u) * beta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: 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 else: # alpha is between 0 and 1 (exclusive)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	529
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	530 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	531
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	532 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	533 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	534 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	535 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	536 if p <= 1.0:
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	537 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	538 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	539 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	540 u1 = random()
34942 7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	541 if p > 1.0:
7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	542 if u1 <= x ** (alpha - 1.0):
7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	543 break
7287b41145ae SF patch #1191489: Simplify logic in random.py Raymond Hettinger <python@rcn.com> parents: 34312 diff changeset	544 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	545 break
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	546 return x * beta
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	547
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	548 ## -------------------- 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	549
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	550 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	551 """Gaussian distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	552
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	553 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	554 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	555
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	556 Not thread-safe without a lock around calls.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	557
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	558 """
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	559
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	560 # 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	561 # 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	562 #
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	563 # 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	564 # 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	565 #
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	566 # 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	567 # (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	568 # (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	569 # (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	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 # 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	572 # 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	573 # 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	574 # 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	575 # 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	576 # lock here.)
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	577
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	578 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	579 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	580 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	581 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	582 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	583 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	584 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	585 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	586
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	587 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	588
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	589 ## -------------------- beta --------------------
16271 7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	590 ## See
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	591 ## 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	592 ## 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	593 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	594 ## def betavariate(self, alpha, beta):
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	595 ## # 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	596 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	597 ## y = self.expovariate(alpha)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	598 ## 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	599 ## return z/(y+z)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	600 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	601 ## 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	602
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	603 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	604 """Beta distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	605
40673 2f80af674074 SF# 1635892: Fix docs for betavariate's input parameters . Raymond Hettinger <python@rcn.com> parents: 40488 diff changeset	606 Conditions on the parameters are alpha > 0 and beta > 0.
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	607 Returned values range between 0 and 1.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	608
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	609 """
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	610
16271 7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	611 # 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	612 # 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	613 y = self.gammavariate(alpha, 1.)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	614 if y == 0:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	615 return 0.0
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	616 else:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	617 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	618
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	619 ## -------------------- Pareto --------------------
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	620
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	621 def paretovariate(self, alpha):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	622 """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	623 # Jain, pg. 495
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	624
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	625 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	626 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	627
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	628 ## -------------------- Weibull --------------------
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	629
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	630 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	631 """Weibull distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	632
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	633 alpha is the scale parameter and beta is the shape parameter.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	634
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	635 """
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	636 # 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	637
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	638 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	639 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	640
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	641 ## -------------------- 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	642
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	643 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	644
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	645 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	646
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	647 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	648 """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	649
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	650 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	651 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	652
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	653 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	654
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	655 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	656 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	657 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	658 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	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
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	661 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	662 try:
8e23bd3d5b1a Fulfill Martin's request to use try/except rather than a "look before Raymond Hettinger <python@rcn.com> parents: 33399 diff changeset	663 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	664 except NotImplementedError:
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	665 import time
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	666 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	667
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	668 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	669 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	670
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	671 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	672 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	673 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	674 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	675
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	676 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	677
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	678 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	679 """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	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 # 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	682 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	683 # 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	684 # 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	685 # 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	686 # 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	687 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	688 # 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	689 # 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	690 # 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	691 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	692 # 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	693 # 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	694 # 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	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 # 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	697 # 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	698 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	699 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	700 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	701 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	702 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	703 # 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	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 # 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	706 # 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	707 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	708
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	709 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	710 """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	711 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	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 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	714 """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	715 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	716 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	717 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	718 else:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	719 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	720 "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	721 (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	722
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	723 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	724 """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	725
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	726 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	727
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	728 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	729 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	730 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	731 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	732 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	733 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	734 period.
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
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	737 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	738 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	739 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	740 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	741 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	742 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	743 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	744
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	745 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	746 """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	747
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	748 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	749 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	750
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	751 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	752 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	753 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	754 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	755 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	756 # 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	757 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	758 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	759 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	760 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	761 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	762 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	763 # 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	764 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	765
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	766 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	767
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	768 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	769 """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	770
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	771 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	772 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	773 states.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	774
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	775 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	776 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	777 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	778
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	779 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	780 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	781 return
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	782 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	783 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	784 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	785 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	786 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	787 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	788 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	789 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	790
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	791 ## --------------- Operating System Random Source ------------------
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	792
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	793 class SystemRandom(Random):
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	794 """Alternate random number generator using sources provided
eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	795 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	796 CryptGenRandom on Windows).
33329 97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	797
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	798 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	799 """
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	800
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	801 def random(self):
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	802 """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	803 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	804
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	805 def getrandbits(self, k):
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	806 """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	807 if k <= 0:
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	808 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	809 if k != int(k):
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	810 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	811 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	812 x = long(_hexlify(_urandom(bytes)), 16)
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	813 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	814
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	815 def _stub(self, args, *kwds):
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	816 "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	817 return None
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	818 seed = jumpahead = _stub
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	819
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	820 def _notimplemented(self, args, *kwds):
33481 eacdc29606d8 SF #1027105: HardwareRandom should be renamed OSRandom Raymond Hettinger <python@rcn.com> parents: 33409 diff changeset	821 "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	822 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	823 getstate = setstate = _notimplemented
97fca735c8da Teach the random module about os.urandom(). Raymond Hettinger <python@rcn.com> parents: 32287 diff changeset	824
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	825 ## -------------------- test program --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	826
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	827 def _test_generator(n, func, args):
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	828 import time
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	829 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	830 total = 0.0
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	831 sqsum = 0.0
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	832 smallest = 1e10
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	833 largest = -1e10
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	834 t0 = time.time()
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	835 for i in range(n):
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	836 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	837 total += x
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	838 sqsum = sqsum + x*x
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	839 smallest = min(x, smallest)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	840 largest = max(x, largest)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	841 t1 = time.time()
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	842 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	843 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	844 stddev = _sqrt(sqsum/n - avg*avg)
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	845 print 'avg %g, stddev %g, min %g, max %g' % \
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	846 (avg, stddev, smallest, largest)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	847
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	848
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	849 def _test(N=2000):
30243 53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	850 _test_generator(N, random, ())
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	851 _test_generator(N, normalvariate, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	852 _test_generator(N, lognormvariate, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	853 _test_generator(N, vonmisesvariate, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	854 _test_generator(N, gammavariate, (0.01, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	855 _test_generator(N, gammavariate, (0.1, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	856 _test_generator(N, gammavariate, (0.1, 2.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	857 _test_generator(N, gammavariate, (0.5, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	858 _test_generator(N, gammavariate, (0.9, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	859 _test_generator(N, gammavariate, (1.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	860 _test_generator(N, gammavariate, (2.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	861 _test_generator(N, gammavariate, (20.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	862 _test_generator(N, gammavariate, (200.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	863 _test_generator(N, gauss, (0.0, 1.0))
53a322c6de52 Eliminate unnecessary eval() in tests Raymond Hettinger <python@rcn.com> parents: 30114 diff changeset	864 _test_generator(N, betavariate, (3.0, 3.0))
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	865 _test_generator(N, triangular, (0.0, 1.0, 1.0/3.0))
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	866
16292 0501c2a10315 New comment block to Clarify a subtlety. Tim Peters <tim.peters@gmail.com> parents: 16272 diff changeset	867 # 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	868 # 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	869 #(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	870 # 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	871 # 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	872
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	873 _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	874 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	875 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	876 uniform = _inst.uniform
46029 f1e51785947f Issue 1681432: Add triangular distribution the random module. Raymond Hettinger <python@rcn.com> parents: 44122 diff changeset	877 triangular = _inst.triangular
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	878 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	879 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	880 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	881 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	882 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	883 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	884 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	885 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	886 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	887 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	888 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	889 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	890 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	891 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	892 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	893 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	894 jumpahead = _inst.jumpahead
30649 8841d34a2c37 SF bug #812202: randint is always even Raymond Hettinger <python@rcn.com> parents: 30346 diff changeset	895 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	896
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	897 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	898 _test()

Mercurial > cpython-lru_cache-weakref

annotate Lib/random.py @ 58765:2ba7677bfa95 legacy-trunk