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

annotate Lib/random.py @ 28646:193b8aec00ce legacy-trunk

Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to work. This includes some more code that used to be part of pgen in the main parser; I'm okay with that. I'll see if the Windows build needs work next.

author	Guido van Rossum <guido@python.org>
date	Thu, 17 Apr 2003 14:55:42 +0000
parents	9de064c7a247
children	34609fa35b11

rev	line source
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	1 """Random variable generators.
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	2
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	3 integers
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	4 --------
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	5 uniform within range
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	6
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	7 sequences
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	8 ---------
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	9 pick random element
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	10 pick random sample
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	11 generate random permutation
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	12
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	13 distributions on the real line:
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	14 ------------------------------
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	15 uniform
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	16 normal (Gaussian)
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	17 lognormal
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	18 negative exponential
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	19 gamma
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	20 beta
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	21 pareto
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	22 Weibull
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	23
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	24 distributions on the circle (angles 0 to 2pi)
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	25 ---------------------------------------------
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	26 circular uniform
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	27 von Mises
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	28
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	29 General notes on the underlying Mersenne Twister core generator:
16272 835e9dd54bfb The combo of getstate/setstate/jumpahead is very powerful, but needs Tim Peters <tim.peters@gmail.com> parents: 16271 diff changeset	30
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	31 * The period is 2**19937-1.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	32 * It is one of the most extensively tested generators in existence
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	33 * Without a direct way to compute N steps forward, the
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	34 semantics of jumpahead(n) are weakened to simply jump
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	35 to another distant state and rely on the large period
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	36 to avoid overlapping sequences.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	37 * The random() method is implemented in C, executes in
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	38 a single Python step, and is, therefore, threadsafe.
16272 835e9dd54bfb The combo of getstate/setstate/jumpahead is very powerful, but needs Tim Peters <tim.peters@gmail.com> parents: 16271 diff changeset	39
11707 6f4146846337 The third and final doc-string sweep by Ka-Ping Yee. Guido van Rossum <guido@python.org> parents: 11200 diff changeset	40 """
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	41
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	42 from math import log as _log, exp as _exp, pi as _pi, e as _e
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	43 from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
24861 4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	44 from math import floor as _floor
8455 af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results, Guido van Rossum <guido@python.org> parents: 8393 diff changeset	45
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	46 __all__ = ["Random","seed","random","uniform","randint","choice","sample",
16613 f68dbffff927 bunch more __all__ lists Skip Montanaro <skip@pobox.com> parents: 16386 diff changeset	47 "randrange","shuffle","normalvariate","lognormvariate",
f68dbffff927 bunch more __all__ lists Skip Montanaro <skip@pobox.com> parents: 16386 diff changeset	48 "cunifvariate","expovariate","vonmisesvariate","gammavariate",
f68dbffff927 bunch more __all__ lists Skip Montanaro <skip@pobox.com> parents: 16386 diff changeset	49 "stdgamma","gauss","betavariate","paretovariate","weibullvariate",
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	50 "getstate","setstate","jumpahead"]
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	51
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	52 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	53 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	54 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	55 SG_MAGICCONST = 1.0 + _log(4.5)
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 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 # 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	58 # Adrian Baddeley. Adapted by Raymond Hettinger for use with
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	59 # the Mersenne Twister core generator.
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	60
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	61 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	62
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	63 class Random(_random.Random):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	64 """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	65
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	66 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	67 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	68 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	69 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	70 overlap.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	71
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	72 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	73 generator of your own devising: in that case, override the following
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	74 methods: random(), seed(), getstate(), setstate() and jumpahead().
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	75
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	76 """
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	77
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	78 VERSION = 2 # used by getstate/setstate
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	79
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	80 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	81 """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	82
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	83 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	84 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	85
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	86 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	87 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	88
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	89 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	90 """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	91
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	92 None or no argument seeds from current time.
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	93
16386 c2555b4f38a3 Repaired a docstring. Tim Peters <tim.peters@gmail.com> parents: 16379 diff changeset	94 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	95 """
8393 7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom. Guido van Rossum <guido@python.org> parents: 7881 diff changeset	96
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	97 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	98 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	99
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	100 def getstate(self):
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	101 """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	102 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	103
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	104 def setstate(self, state):
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	105 """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	106 version = state[0]
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	107 if version == 2:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	108 version, internalstate, self.gauss_next = state
27131 e87d590a5de1 Much clearer when super() is used. Raymond Hettinger <python@rcn.com> parents: 27094 diff changeset	109 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	110 else:
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	111 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	112 "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	113 (version, self.VERSION))
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	114
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	115 ## ---- 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	116 ## ---- 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	117
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	118 ## -------------------- pickle support -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	119
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	120 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	121 return self.getstate()
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	122
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	123 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	124 self.setstate(state)
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	125
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	126 ## -------------------- integer methods -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	127
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	128 def randrange(self, start, stop=None, step=1, int=int, default=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	129 """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	130
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	131 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	132 endpoint; in Python this is usually not what you want.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	133 Do not supply the 'int' and 'default' arguments.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	134 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	135
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	136 # 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	137 # 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	138 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	139 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	140 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	141 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	142 if istart > 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	143 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	144 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	145
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	146 # 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	147 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	148 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	149 raise ValueError, "non-integer stop for randrange()"
24861 4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	150 if step == 1 and istart < istop:
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	151 try:
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	152 return istart + int(self.random()*(istop - istart))
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	153 except OverflowError:
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	154 # This can happen if istop-istart > sys.maxint + 1, and
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	155 # multiplying by random() doesn't reduce it to something
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	156 # <= sys.maxint. We know that the overall result fits
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	157 # in an int, and can still do it correctly via math.floor().
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	158 # But that adds another function call, so for speed we
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	159 # avoided that whenever possible.
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	160 return int(istart + _floor(self.random()*(istop - 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	161 if step == 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	162 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	163
4e795fe9f54b SF bug 594996: OverflowError in random.randrange Tim Peters <tim.peters@gmail.com> parents: 23536 diff changeset	164 # 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	165 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	166 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	167 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	168 if istep > 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	169 n = (istop - istart + istep - 1) / istep
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	170 elif istep < 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	171 n = (istop - istart + istep + 1) / istep
3c5f09422b69 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 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	173 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	174
3c5f09422b69 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 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	176 raise ValueError, "empty range 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	177 return istart + istepint(self.random() n)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	178
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	179 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	180 """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	181 """
3c5f09422b69 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
3c5f09422b69 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 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	184
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	185 ## -------------------- sequence methods -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	186
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	187 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	188 """Choose a random element from a non-empty sequence."""
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	189 return seq[int(self.random() * len(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	190
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	191 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	192 """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	193
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	194 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	195 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	196
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	197 Note that for even rather small len(x), the total number of
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	198 permutations of x is larger than the period of most random number
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	199 generators; this implies that "most" permutations of a long
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	200 sequence can never be generated.
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	201 """
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	202
3c5f09422b69 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 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	204 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	205 for i in xrange(len(x)-1, 0, -1):
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	206 # 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	207 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	208 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	209
27080 2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	210 def sample(self, population, k, int=int):
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	211 """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	212
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	213 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	214 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	215 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	216 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	217 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	218
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	219 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	220 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	221 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	222
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	223 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	224 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	225 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	226 """
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	227
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	228 # Sampling without replacement entails tracking either potential
27080 2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	229 # selections (the pool) in a list or previous selections in a
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	230 # dictionary.
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	231
27080 2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	232 # When the number of selections is small compared to the population,
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	233 # then tracking selections is efficient, requiring only a small
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	234 # dictionary and an occasional reselection. For a larger number of
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	235 # selections, the pool tracking method is preferred since the list takes
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	236 # less space than the dictionary and it doesn't suffer from frequent
2ae1d17572da Remove the random=None nonsense from sample() before it gets set in stone. Raymond Hettinger <python@rcn.com> parents: 26829 diff changeset	237 # reselections.
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	238
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	239 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	240 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	241 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	242 random = self.random
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	243 result = [None] * k
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	244 if n < 6 * k: # if n len list takes less space than a k len dict
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	245 pool = list(population)
42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	246 for i in xrange(k): # invariant: non-selected at [0,n-i)
42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	247 j = int(random() * (n-i))
42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	248 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	249 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	250 else:
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	251 selected = {}
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	252 for i in xrange(k):
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	253 j = int(random() * n)
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	254 while j in selected:
26178 83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	255 j = int(random() * n)
83ae4a902df0 Improved clarity and thoroughness of docstring. Raymond Hettinger <python@rcn.com> parents: 26172 diff changeset	256 result[i] = selected[j] = population[j]
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	257 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	258
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	259 ## -------------------- real-valued distributions -------------------
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	260
d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	261 ## -------------------- 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	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 uniform(self, a, b):
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	264 """Get a random number in the range [a, b)."""
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	265 return a + (b-a) * self.random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	266
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	267 ## -------------------- normal distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	268
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	269 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	270 """Normal distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	271
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	272 mu is the mean, and sigma is the standard deviation.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	273
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	274 """
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	275 # 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	276
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	277 # 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	278 # 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	279 # 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	280 # Math Software, 3, (1977), pp257-260.
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	281
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	282 random = self.random
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	283 while True:
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	284 u1 = random()
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	285 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	286 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	287 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	288 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	289 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	290 return mu + z*sigma
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	291
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	292 ## -------------------- lognormal distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	293
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	294 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	295 """Log normal distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	296
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	297 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	298 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	299 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	300
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	301 """
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	302 return _exp(self.normalvariate(mu, sigma))
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	303
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	304 ## -------------------- circular uniform --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	305
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	306 def cunifvariate(self, mean, arc):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	307 """Circular uniform distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	308
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	309 mean is the mean angle, and arc is the range of the distribution,
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	310 centered around the mean angle. Both values must be expressed in
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	311 radians. Returned values range between mean - arc/2 and
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	312 mean + arc/2 and are normalized to between 0 and pi.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	313
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	314 Deprecated in version 2.3. Use:
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	315 (mean + arc * (Random.random() - 0.5)) % Math.pi
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	316
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	317 """
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	318 # mean: mean angle (in radians between 0 and 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	319 # arc: range of distribution (in radians between 0 and pi)
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	320 import warnings
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	321 warnings.warn("The cunifvariate function is deprecated; Use (mean "
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	322 "+ arc * (Random.random() - 0.5)) % Math.pi instead",
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	323 DeprecationWarning)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	324
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	325 return (mean + arc * (self.random() - 0.5)) % _pi
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	326
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	327 ## -------------------- exponential distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	328
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	329 def expovariate(self, lambd):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	330 """Exponential distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	331
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	332 lambd is 1.0 divided by the desired mean. (The parameter would be
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	333 called "lambda", but that is a reserved word in Python.) Returned
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	334 values range from 0 to positive infinity.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	335
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	336 """
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	337 # 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	338 # ('lambda' is a Python reserved word)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	339
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	340 random = self.random
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	341 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	342 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	343 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	344 return -_log(u)/lambd
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	345
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	346 ## -------------------- von Mises distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	347
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	348 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	349 """Circular data distribution.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	350
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	351 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	352 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	353 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	354 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	355
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	356 """
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	357 # 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	358 # 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	359 # if kappa = 0 generate uniform random angle
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	360
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	361 # 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	362 # "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	363 # 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	364
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	365 # 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	366 # 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	367
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	368 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	369 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	370 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	371
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	372 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	373 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	374 r = (1.0 + b * b)/(2.0 * b)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	375
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	376 while True:
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	377 u1 = random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	378
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	379 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	380 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	381 c = kappa * (r - f)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	382
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	383 u2 = random()
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	384
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	385 if not (u2 >= c * (2.0 - c) and u2 > c * _exp(1.0 - c)):
3c5f09422b69 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 break
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	387
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	388 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	389 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	390 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	391 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	392 theta = (mu % TWOPI) - _acos(f)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	393
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	394 return theta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	395
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	396 ## -------------------- gamma distribution --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	397
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	398 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	399 """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	400
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	401 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	402
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	403 """
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	404
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	405 # 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	406
23451 273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	407 # 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	408 # of alpha > -1.0
273dd2508c57 Use spaces, not tabs for indents. Guido van Rossum <guido@python.org> parents: 23447 diff changeset	409 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	410 raise ValueError, 'gammavariate: alpha and beta must be > 0.0'
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	411
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	412 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	413 if alpha > 1.0:
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	414
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	415 # 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	416 # 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	417 # Applied Statistics, (1977), 26, No. 1, p71-74
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	418
23442 b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	419 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	420 bbb = alpha - LOG4
b15896053933 Closes SF bug 527139. Moved temp variables inside guard. Raymond Hettinger <python@rcn.com> parents: 23380 diff changeset	421 ccc = alpha + ainv
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	422
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	423 while True:
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	424 u1 = random()
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	425 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	426 continue
90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	427 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	428 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	429 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	430 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	431 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	432 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	433 return x * beta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	434
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	435 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	436 # expovariate(1)
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	437 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	438 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	439 u = random()
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	440 return -_log(u) * beta
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	441
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	442 else: # alpha is between 0 and 1 (exclusive)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	443
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	444 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	445
26266 42279f7d244d Improve comments. Clarify docs. Raymond Hettinger <python@rcn.com> parents: 26178 diff changeset	446 while True:
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 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	448 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	449 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	450 if p <= 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	451 x = pow(p, 1.0/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	452 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	453 # p > 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	454 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	455 u1 = 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	456 if not (((p <= 1.0) and (u1 > _exp(-x))) or
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	457 ((p > 1) and (u1 > pow(x, 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	458 break
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	459 return x * beta
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	460
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	461
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	462 def stdgamma(self, alpha, ainv, bbb, ccc):
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	463 # This method was (and shall remain) undocumented.
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	464 # This method is deprecated
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	465 # for the following reasons:
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	466 # 1. Returns same as .gammavariate(alpha, 1.0)
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	467 # 2. Requires caller to provide 3 extra arguments
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	468 # that are functions of alpha anyway
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	469 # 3. Can't be used for alpha < 0.5
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	470
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	471 # ainv = sqrt(2 * alpha - 1)
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	472 # bbb = alpha - log(4)
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	473 # ccc = alpha + ainv
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	474 import warnings
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	475 warnings.warn("The stdgamma function is deprecated; "
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	476 "use gammavariate() instead",
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	477 DeprecationWarning)
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	478 return self.gammavariate(alpha, 1.0)
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	479
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	480
1576 695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate(); Guido van Rossum <guido@python.org> parents: 1575 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 ## -------------------- 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	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 gauss(self, mu, sigma):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	485 """Gaussian distribution.
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 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	488 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	489
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	490 Not thread-safe without a lock around calls.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	491
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	492 """
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	493
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	494 # 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	495 # 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	496 #
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	497 # 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	498 # 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	499 #
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	500 # 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	501 # (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	502 # (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	503 # (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	504
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	505 # 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	506 # 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	507 # 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	508 # 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	509 # 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	510 # lock here.)
1577 444e349f962f Use float constants directly; cosmetic changes; initialize largest Guido van Rossum <guido@python.org> parents: 1576 diff changeset	511
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	512 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	513 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	514 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	515 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	516 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	517 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	518 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	519 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	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 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	522
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	523 ## -------------------- beta --------------------
16271 7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	524 ## See
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	525 ## 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	526 ## 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	527 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	528 ## def betavariate(self, alpha, beta):
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	529 ## # 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	530 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	531 ## y = self.expovariate(alpha)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	532 ## 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	533 ## return z/(y+z)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	534 ##
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	535 ## 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	536
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	537 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	538 """Beta distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	539
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	540 Conditions on the parameters are alpha > -1 and beta} > -1.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	541 Returned values range between 0 and 1.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	542
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	543 """
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	544
16271 7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	545 # 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	546 # 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	547 y = self.gammavariate(alpha, 1.)
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	548 if y == 0:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	549 return 0.0
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	550 else:
7ef2382f6123 SF bug 130030: Claim of bad betavariate algorithm. Tim Peters <tim.peters@gmail.com> parents: 16265 diff changeset	551 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	552
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	553 ## -------------------- Pareto --------------------
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	554
16242 3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	555 def paretovariate(self, alpha):
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	556 """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	557 # Jain, pg. 495
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	558
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	559 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	560 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	561
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	562 ## -------------------- Weibull --------------------
6698 b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton. Guido van Rossum <guido@python.org> parents: 1618 diff changeset	563
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	564 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	565 """Weibull distribution.
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	566
a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	567 alpha is the scale parameter and beta is the shape parameter.
23536 0a4c92559a0b Whitespace normalized. Raymond Hettinger <python@rcn.com> parents: 23531 diff changeset	568
23531 a98e93eafef7 Deprecated Random.cunifvariate clearing bug 506647. Also, added docstrings. Raymond Hettinger <python@rcn.com> parents: 23521 diff changeset	569 """
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	570 # 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	571
27085 90350b5d3397 Correct long standing bugs in the methods for random distributions. Raymond Hettinger <python@rcn.com> parents: 27080 diff changeset	572 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	573 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	574
26829 f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	575 ## -------------------- 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	576
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	577 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	578
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	579 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	580
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	581 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	582 """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	583
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	584 None or no argument seeds 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	585
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	586 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	587
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	588 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	589 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	590 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	591 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	592 """
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	593
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	594 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	595 # 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	596 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	597 a = 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	598
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	599 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	600 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	601
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	602 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	603 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	604 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	605 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	606
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	607 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	608
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	609 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	610 """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	611
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	612 # 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	613 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	614 # 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	615 # 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	616 # 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	617 # 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	618 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	619 # 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	620 # 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	621 # 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	622 #
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	623 # 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	624 # 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	625 # 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	626
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	627 # 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	628 # 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	629 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	630 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	631 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	632 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	633 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	634 # 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	635
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	636 # 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	637 # 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	638 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	639
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	640 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	641 """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	642 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	643
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	644 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	645 """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	646 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	647 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	648 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	649 else:
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	650 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	651 "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	652 (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	653
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	654 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	655 """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	656
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	657 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	658
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	659 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	660 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	661 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	662 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	663 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	664 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	665 period.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	666 """
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 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	669 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	670 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	671 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	672 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	673 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	674 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	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 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	677 """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	678
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	679 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	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
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	682 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	683 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	684 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	685 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	686 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	687 # 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	688 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	689 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	690 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	691 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	692 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	693 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	694 # 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	695 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	696
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	697 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	698
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	699 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	700 """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	701
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	702 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	703 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	704 states.
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	705
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	706 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	707 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	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
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	710 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	711 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	712 return
f64c96922708 SF patch 658251: Install a C implementation of the Mersenne Twister as the Raymond Hettinger <python@rcn.com> parents: 26564 diff changeset	713 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	714 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	715 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	716 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	717 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	718 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	719 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	720 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	721
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	722 ## -------------------- test program --------------------
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	723
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	724 def _test_generator(n, funccall):
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	725 import time
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	726 print n, 'times', funccall
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	727 code = compile(funccall, funccall, 'eval')
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	728 sum = 0.0
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	729 sqsum = 0.0
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	730 smallest = 1e10
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	731 largest = -1e10
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	732 t0 = time.time()
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	733 for i in range(n):
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	734 x = eval(code)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	735 sum = sum + x
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	736 sqsum = sqsum + x*x
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	737 smallest = min(x, smallest)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	738 largest = max(x, largest)
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	739 t1 = time.time()
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	740 print round(t1-t0, 3), 'sec,',
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	741 avg = sum/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	742 stddev = _sqrt(sqsum/n - avg*avg)
15871 62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	743 print 'avg %g, stddev %g, min %g, max %g' % \
62aeefa01fdd Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 14617 diff changeset	744 (avg, stddev, smallest, largest)
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	745
26155 8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	746
8ceb455f5541 SF patch 629637: Add sample(population, k) method to the random module. Raymond Hettinger <python@rcn.com> parents: 24861 diff changeset	747 def _test(N=2000):
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	748 _test_generator(N, '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	749 _test_generator(N, 'normalvariate(0.0, 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	750 _test_generator(N, 'lognormvariate(0.0, 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	751 _test_generator(N, 'cunifvariate(0.0, 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	752 _test_generator(N, 'vonmisesvariate(0.0, 1.0)')
23447 08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	753 _test_generator(N, 'gammavariate(0.01, 1.0)')
08ccb0f3e2d4 Closes patch 529408 deprecating random.stdgamma(). Raymond Hettinger <python@rcn.com> parents: 23442 diff changeset	754 _test_generator(N, 'gammavariate(0.1, 1.0)')
23521 a90faa5f9417 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 23451 diff changeset	755 _test_generator(N, 'gammavariate(0.1, 2.0)')
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	756 _test_generator(N, 'gammavariate(0.5, 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	757 _test_generator(N, 'gammavariate(0.9, 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	758 _test_generator(N, 'gammavariate(1.0, 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	759 _test_generator(N, 'gammavariate(2.0, 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	760 _test_generator(N, 'gammavariate(20.0, 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	761 _test_generator(N, 'gammavariate(200.0, 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	762 _test_generator(N, 'gauss(0.0, 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	763 _test_generator(N, 'betavariate(3.0, 3.0)')
16265 d614b6e9fb4e Cosmetic changes after some sleep; no change in semantics. Tim Peters <tim.peters@gmail.com> parents: 16243 diff changeset	764
16292 0501c2a10315 New comment block to Clarify a subtlety. Tim Peters <tim.peters@gmail.com> parents: 16272 diff changeset	765 # 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	766 # 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	767 #(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	768 # 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	769 # 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	770
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	771 _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	772 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	773 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	774 uniform = _inst.uniform
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	775 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	776 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	777 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	778 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	779 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	780 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	781 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	782 cunifvariate = _inst.cunifvariate
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	783 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	784 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	785 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	786 stdgamma = _inst.stdgamma
3c5f09422b69 Reworked random.py so that it no longer depends on, and offers all the Tim Peters <tim.peters@gmail.com> parents: 15871 diff changeset	787 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	788 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	789 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	790 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	791 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	792 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	793 jumpahead = _inst.jumpahead
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	794
1575 45728bfecb76 Random variable generators Guido van Rossum <guido@python.org> parents: diff changeset	795 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	796 _test()

Mercurial > cpython-lru_cache-weakref

annotate Lib/random.py @ 28646:193b8aec00ce legacy-trunk