Mercurial > cpython-lru_cache-weakref

annotate Lib/random.py @ 14984:ece6c19edcc1 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove some debugging prints.
author Greg Ward <gward@python.net>
date Tue, 03 Oct 2000 03:32:37 +0000
parents 9d798a763d24
children 62aeefa01fdd
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
3 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
4 ------------------------------
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
5 normal (Gaussian)
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
6 lognormal
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
7 negative exponential
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
8 gamma
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
9 beta
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
10
11707
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
11 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
12 ---------------------------------------------
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
13 circular uniform
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
14 von Mises
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
15
11707
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
16 Translated from anonymously contributed C/C++ source.
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
17
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
18 Multi-threading note: the random number generator used here is not
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
19 thread-safe; it is possible that two calls return the same random
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
20 value. See whrandom.py for more info.
6f4146846337 The third and final doc-string sweep by Ka-Ping Yee.
Guido van Rossum <guido@python.org>
parents: 11200
diff changeset
21 """
8455
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
22
8393
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
23 import whrandom
8802
81cb9401a21b Added randrange to list of exported functions.
Guido van Rossum <guido@python.org>
parents: 8455
diff changeset
24 from whrandom import random, uniform, randint, choice, randrange # For export!
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
25 from math import log, exp, pi, e, sqrt, acos, cos, sin
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
26
8393
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
27 # Interfaces to replace remaining needs for importing whrandom
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
28 # XXX TO DO: make the distribution functions below into methods.
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
29
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
30 def makeseed(a=None):
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
31 """Turn a hashable value into three seed values for whrandom.seed().
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
32
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
33 None or no argument returns (0, 0, 0), to seed from current time.
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
34
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
35 """
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
36 if a is None:
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
37 return (0, 0, 0)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
38 a = hash(a)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
39 a, x = divmod(a, 256)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
40 a, y = divmod(a, 256)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
41 a, z = divmod(a, 256)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
42 x = (x + a) % 256 or 1
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
43 y = (y + a) % 256 or 1
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
44 z = (z + a) % 256 or 1
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
45 return (x, y, z)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
46
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
47 def seed(a=None):
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
48 """Seed the default generator from any hashable value.
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
49
14617
9d798a763d24 Repair senseless random.seed docstring (reported on c.l.py).
Tim Peters <tim.peters@gmail.com>
parents: 11707
diff changeset
50 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
51
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
52 """
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
53 x, y, z = makeseed(a)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
54 whrandom.seed(x, y, z)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
55
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
56 class generator(whrandom.whrandom):
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
57 """Random generator class."""
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
58
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
59 def __init__(self, a=None):
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
60 """Constructor. Seed from current time or hashable value."""
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
61 self.seed(a)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
62
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
63 def seed(self, a=None):
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
64 """Seed the generator from current time or hashable value."""
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
65 x, y, z = makeseed(a)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
66 whrandom.whrandom.seed(self, x, y, z)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
67
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
68 def new_generator(a=None):
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
69 """Return a new random generator instance."""
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
70 return generator(a)
7669ddf0e7d4 Add Interfaces to replace remaining needs for importing whrandom.
Guido van Rossum <guido@python.org>
parents: 7881
diff changeset
71
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
72 # Housekeeping function to verify that magic constants have been
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
73 # computed correctly
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
74
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
75 def verify(name, expected):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
76 computed = eval(name)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
77 if abs(computed - expected) > 1e-7:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
78 raise ValueError, \
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
79 'computed value for %s deviates too much (computed %g, expected %g)' % \
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
80 (name, computed, expected)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
81
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
82 # -------------------- normal distribution --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
83
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
84 NV_MAGICCONST = 4*exp(-0.5)/sqrt(2.0)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
85 verify('NV_MAGICCONST', 1.71552776992141)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
86 def normalvariate(mu, sigma):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
87 # mu = mean, sigma = standard deviation
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
88
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
89 # Uses Kinderman and Monahan method. Reference: Kinderman,
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
90 # A.J. and Monahan, J.F., "Computer generation of random
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
91 # variables using the ratio of uniform deviates", ACM Trans
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
92 # Math Software, 3, (1977), pp257-260.
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
93
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
94 while 1:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
95 u1 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
96 u2 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
97 z = NV_MAGICCONST*(u1-0.5)/u2
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
98 zz = z*z/4.0
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
99 if zz <= -log(u2):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
100 break
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
101 return mu+z*sigma
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
102
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
103 # -------------------- lognormal distribution --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
104
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
105 def lognormvariate(mu, sigma):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
106 return exp(normalvariate(mu, sigma))
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
107
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
108 # -------------------- circular uniform --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
109
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
110 def cunifvariate(mean, arc):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
111 # mean: mean angle (in radians between 0 and pi)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
112 # arc: range of distribution (in radians between 0 and pi)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
113
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
114 return (mean + arc * (random() - 0.5)) % pi
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
115
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
116 # -------------------- exponential distribution --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
117
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
118 def expovariate(lambd):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
119 # lambd: rate lambd = 1/mean
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
120 # ('lambda' is a Python reserved word)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
121
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
122 u = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
123 while u <= 1e-7:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
124 u = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
125 return -log(u)/lambd
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
126
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
127 # -------------------- von Mises distribution --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
128
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
129 TWOPI = 2.0*pi
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
130 verify('TWOPI', 6.28318530718)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
131
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
132 def vonmisesvariate(mu, kappa):
7881
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
133 # mu: mean angle (in radians between 0 and 2*pi)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
134 # kappa: concentration parameter kappa (>= 0)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
135 # if kappa = 0 generate uniform random angle
7881
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
136
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
137 # Based upon an algorithm published in: Fisher, N.I.,
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
138 # "Statistical Analysis of Circular Data", Cambridge
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
139 # University Press, 1993.
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
140
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
141 # Thanks to Magnus Kessler for a correction to the
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
142 # implementation of step 4.
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
143
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
144 if kappa <= 1e-6:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
145 return TWOPI * random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
146
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
147 a = 1.0 + sqrt(1.0 + 4.0 * kappa * kappa)
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
148 b = (a - sqrt(2.0 * a))/(2.0 * kappa)
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
149 r = (1.0 + b * b)/(2.0 * b)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
150
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
151 while 1:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
152 u1 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
153
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
154 z = cos(pi * u1)
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
155 f = (1.0 + r * z)/(r + z)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
156 c = kappa * (r - f)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
157
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
158 u2 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
159
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
160 if not (u2 >= c * (2.0 - c) and u2 > c * exp(1.0 - c)):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
161 break
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
162
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
163 u3 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
164 if u3 > 0.5:
7881
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
165 theta = (mu % TWOPI) + acos(f)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
166 else:
7881
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
167 theta = (mu % TWOPI) - acos(f)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
168
7881
6370f1593c72 Correction to vonmisesvariate() by Magnus Kessler: it should take and
Guido van Rossum <guido@python.org>
parents: 7412
diff changeset
169 return theta
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
170
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
171 # -------------------- gamma distribution --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
172
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
173 LOG4 = log(4.0)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
174 verify('LOG4', 1.38629436111989)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
175
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
176 def gammavariate(alpha, beta):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
177 # beta times standard gamma
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
178 ainv = sqrt(2.0 * alpha - 1.0)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
179 return beta * stdgamma(alpha, ainv, alpha - LOG4, alpha + ainv)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
180
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
181 SG_MAGICCONST = 1.0 + log(4.5)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
182 verify('SG_MAGICCONST', 2.50407739677627)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
183
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
184 def stdgamma(alpha, ainv, bbb, ccc):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
185 # ainv = sqrt(2 * alpha - 1)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
186 # bbb = alpha - log(4)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
187 # ccc = alpha + ainv
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
188
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
189 if alpha <= 0.0:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
190 raise ValueError, 'stdgamma: alpha must be > 0.0'
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
191
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
192 if alpha > 1.0:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
193
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
194 # Uses R.C.H. Cheng, "The generation of Gamma
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
195 # variables with non-integral shape parameters",
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
196 # Applied Statistics, (1977), 26, No. 1, p71-74
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
197
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
198 while 1:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
199 u1 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
200 u2 = random()
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
201 v = log(u1/(1.0-u1))/ainv
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
202 x = alpha*exp(v)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
203 z = u1*u1*u2
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
204 r = bbb+ccc*v-x
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
205 if r + SG_MAGICCONST - 4.5*z >= 0.0 or r >= log(z):
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
206 return x
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
207
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
208 elif alpha == 1.0:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
209 # expovariate(1)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
210 u = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
211 while u <= 1e-7:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
212 u = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
213 return -log(u)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
214
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
215 else: # alpha is between 0 and 1 (exclusive)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
216
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
217 # Uses ALGORITHM GS of Statistical Computing - Kennedy & Gentle
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
218
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
219 while 1:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
220 u = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
221 b = (e + alpha)/e
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
222 p = b*u
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
223 if p <= 1.0:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
224 x = pow(p, 1.0/alpha)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
225 else:
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
226 # p > 1
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
227 x = -log((b-p)/alpha)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
228 u1 = random()
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
229 if not (((p <= 1.0) and (u1 > exp(-x))) or
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
230 ((p > 1) and (u1 > pow(x, alpha - 1.0)))):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
231 break
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
232 return x
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
233
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
234
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
235 # -------------------- Gauss (faster alternative) --------------------
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
236
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
237 gauss_next = None
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
238 def gauss(mu, sigma):
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
239
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
240 # When x and y are two variables from [0, 1), uniformly
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
241 # distributed, then
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
242 #
7412
297bea233e03 Fixed a bug in the gauss() function. The bug was reported by Mike
Guido van Rossum <guido@python.org>
parents: 6801
diff changeset
243 # cos(2*pi*x)*sqrt(-2*log(1-y))
297bea233e03 Fixed a bug in the gauss() function. The bug was reported by Mike
Guido van Rossum <guido@python.org>
parents: 6801
diff changeset
244 # sin(2*pi*x)*sqrt(-2*log(1-y))
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
245 #
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
246 # are two *independent* variables with normal distribution
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
247 # (mu = 0, sigma = 1).
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
248 # (Lambert Meertens)
7412
297bea233e03 Fixed a bug in the gauss() function. The bug was reported by Mike
Guido van Rossum <guido@python.org>
parents: 6801
diff changeset
249 # (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
250
8455
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
251 # Multithreading note: When two threads call this function
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
252 # simultaneously, it is possible that they will receive the
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
253 # same return value. The window is very small though. To
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
254 # avoid this, you have to use a lock around all calls. (I
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
255 # didn't want to slow this down in the serial case by using a
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
256 # lock here.)
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
257
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
258 global gauss_next
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
259
8455
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
260 z = gauss_next
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
261 gauss_next = None
af9273b1073a Make gauss() semi-thread-safe. It can still give duplicate results,
Guido van Rossum <guido@python.org>
parents: 8393
diff changeset
262 if z is None:
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
263 x2pi = random() * TWOPI
7412
297bea233e03 Fixed a bug in the gauss() function. The bug was reported by Mike
Guido van Rossum <guido@python.org>
parents: 6801
diff changeset
264 g2rad = sqrt(-2.0 * log(1.0 - random()))
297bea233e03 Fixed a bug in the gauss() function. The bug was reported by Mike
Guido van Rossum <guido@python.org>
parents: 6801
diff changeset
265 z = cos(x2pi) * g2rad
297bea233e03 Fixed a bug in the gauss() function. The bug was reported by Mike
Guido van Rossum <guido@python.org>
parents: 6801
diff changeset
266 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
267
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
268 return mu + z*sigma
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
269
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
270 # -------------------- beta --------------------
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
271
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
272 def betavariate(alpha, beta):
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
273
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
274 # Discrete Event Simulation in C, pp 87-88.
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
275
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
276 y = expovariate(alpha)
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
277 z = expovariate(1.0/beta)
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
278 return z/(y+z)
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
279
6801
bca948194dea # Typos in the comments giving the names of two recently added distributions.
Guido van Rossum <guido@python.org>
parents: 6698
diff changeset
280 # -------------------- Pareto --------------------
6698
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
281
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
282 def paretovariate(alpha):
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
283 # Jain, pg. 495
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
284
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
285 u = random()
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
286 return 1.0 / pow(u, 1.0/alpha)
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
287
6801
bca948194dea # Typos in the comments giving the names of two recently added distributions.
Guido van Rossum <guido@python.org>
parents: 6698
diff changeset
288 # -------------------- Weibull --------------------
6698
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
289
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
290 def weibullvariate(alpha, beta):
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
291 # Jain, pg. 499; bug fix courtesy Bill Arms
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
292
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
293 u = random()
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
294 return alpha * pow(-log(u), 1.0/beta)
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
295
11200
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
296 # -------------------- shuffle --------------------
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
297 # Not quite a random distribution, but a standard algorithm.
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
298 # This implementation due to Tim Peters.
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
299
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
300 def shuffle(x, random=random, int=int):
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
301 """x, random=random.random -> shuffle list x in place; return None.
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
302
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
303 Optional arg random is a 0-argument function returning a random
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
304 float in [0.0, 1.0); by default, the standard random.random.
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
305
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
306 Note that for even rather small len(x), the total number of
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
307 permutations of x is larger than the period of most random number
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
308 generators; this implies that "most" permutations of a long
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
309 sequence can never be generated.
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
310 """
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
311
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
312 for i in xrange(len(x)-1, 0, -1):
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
313 # pick an element in x[:i+1] with which to exchange x[i]
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
314 j = int(random() * (i+1))
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
315 x[i], x[j] = x[j], x[i]
bca2d14f3e36 Add Tim Peters' shuffle() algorithm.
Guido van Rossum <guido@python.org>
parents: 8802
diff changeset
316
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
317 # -------------------- test program --------------------
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
318
1618
7f891f32864c Changes to use default argument values where possible
Guido van Rossum <guido@python.org>
parents: 1577
diff changeset
319 def test(N = 200):
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
320 print 'TWOPI =', TWOPI
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
321 print 'LOG4 =', LOG4
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
322 print 'NV_MAGICCONST =', NV_MAGICCONST
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
323 print 'SG_MAGICCONST =', SG_MAGICCONST
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
324 test_generator(N, 'random()')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
325 test_generator(N, 'normalvariate(0.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
326 test_generator(N, 'lognormvariate(0.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
327 test_generator(N, 'cunifvariate(0.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
328 test_generator(N, 'expovariate(1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
329 test_generator(N, 'vonmisesvariate(0.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
330 test_generator(N, 'gammavariate(0.5, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
331 test_generator(N, 'gammavariate(0.9, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
332 test_generator(N, 'gammavariate(1.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
333 test_generator(N, 'gammavariate(2.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
334 test_generator(N, 'gammavariate(20.0, 1.0)')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
335 test_generator(N, 'gammavariate(200.0, 1.0)')
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
336 test_generator(N, 'gauss(0.0, 1.0)')
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
337 test_generator(N, 'betavariate(3.0, 3.0)')
6698
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
338 test_generator(N, 'paretovariate(1.0)')
b73eb4e6face Added Pareto and Weibull distributions, courtesy Jeremy Hylton.
Guido van Rossum <guido@python.org>
parents: 1618
diff changeset
339 test_generator(N, 'weibullvariate(1.0, 1.0)')
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
340
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
341 def test_generator(n, funccall):
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
342 import time
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
343 print n, 'times', funccall
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
344 code = compile(funccall, funccall, 'eval')
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
345 sum = 0.0
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
346 sqsum = 0.0
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
347 smallest = 1e10
1577
444e349f962f Use float constants directly; cosmetic changes; initialize largest
Guido van Rossum <guido@python.org>
parents: 1576
diff changeset
348 largest = -1e10
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
349 t0 = time.time()
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
350 for i in range(n):
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
351 x = eval(code)
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
352 sum = sum + x
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
353 sqsum = sqsum + x*x
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
354 smallest = min(x, smallest)
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
355 largest = max(x, largest)
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
356 t1 = time.time()
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
357 print round(t1-t0, 3), 'sec,',
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
358 avg = sum/n
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
359 stddev = sqrt(sqsum/n - avg*avg)
1576
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
360 print 'avg %g, stddev %g, min %g, max %g' % \
695fb494a3a2 Added gauss() (same as normal but twice as fast) and betavariate();
Guido van Rossum <guido@python.org>
parents: 1575
diff changeset
361 (avg, stddev, smallest, largest)
1575
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
362
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
363 if __name__ == '__main__':
45728bfecb76 Random variable generators
Guido van Rossum <guido@python.org>
parents:
diff changeset
364 test()