refined the errors in the os module, translating scheme errors to python errors....
[software/python-on-guile.git] / modules / language / python / module / random.py
1 module(random)
2
3 """Random variable generators.
4
5 integers
6 --------
7 uniform within range
8
9 sequences
10 ---------
11 pick random element
12 pick random sample
13 pick weighted random sample
14 generate random permutation
15
16 distributions on the real line:
17 ------------------------------
18 uniform
19 triangular
20 normal (Gaussian)
21 lognormal
22 negative exponential
23 gamma
24 beta
25 pareto
26 Weibull
27
28 distributions on the circle (angles 0 to 2pi)
29 ---------------------------------------------
30 circular uniform
31 von Mises
32
33 General notes on the underlying Mersenne Twister core generator:
34
35 * The period is 2**19937-1.
36 * It is one of the most extensively tested generators in existence.
37 * The random() method is implemented in C, executes in a single Python step,
38 and is, therefore, threadsafe.
39
40 """
41 from warnings import warn as _warn
42 from types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
43 from math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil
44 from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin
45 from os import urandom as _urandom
46 from collections.abc import Set as _Set, Sequence as _Sequence
47 from hashlib import sha512 as _sha512
48 import itertools as _itertools
49 import bisect as _bisect
50
51 __all__ = ["Random","seed","random","uniform","randint","choice","sample",
52 "randrange","shuffle","normalvariate","lognormvariate",
53 "expovariate","vonmisesvariate","gammavariate","triangular",
54 "gauss","betavariate","paretovariate","weibullvariate",
55 "getstate","setstate", "getrandbits", "choices",
56 "SystemRandom"]
57
58 NV_MAGICCONST = 4 * _exp(-0.5)/_sqrt(2.0)
59 TWOPI = 2.0*_pi
60 LOG4 = _log(4.0)
61 SG_MAGICCONST = 1.0 + _log(4.5)
62 BPF = 53 # Number of bits in a float
63 RECIP_BPF = 2**-BPF
64
65
66 # Translated by Guido van Rossum from C source provided by
67 # Adrian Baddeley. Adapted by Raymond Hettinger for use with
68 # the Mersenne Twister and os.urandom() core generators.
69
70 import _random
71
72 class Random (_random.Random):
73 """Random number generator base class used by bound module functions.
74
75 Used to instantiate instances of Random to get generators that don't
76 share state.
77
78 Class Random can also be subclassed if you want to use a different basic
79 generator of your own devising: in that case, override the following
80 methods: random(), seed(), getstate(), and setstate().
81 Optionally, implement a getrandbits() method so that randrange()
82 can cover arbitrarily large ranges.
83
84 """
85
86 VERSION = 3 # used by getstate/setstate
87
88 def __init__(self, x=None):
89 """Initialize an instance.
90
91 Optional argument x controls seeding, as for Random.seed().
92 """
93
94 self.seed(x)
95 self.gauss_next = False
96
97 def seed(self, a=None, version=2):
98 """Initialize internal state from hashable object.
99
100 None or no argument seeds from current time or from an operating
101 system specific randomness source if available.
102
103 If *a* is an int, all bits are used.
104
105 For version 2 (the default), all of the bits are used if *a* is a str,
106 bytes, or bytearray. For version 1 (provided for reproducing random
107 sequences from older versions of Python), the algorithm for str and
108 bytes generates a narrower range of seeds.
109
110 """
111
112 if version == 1 and isinstance(a, (str, bytes)):
113 a = a.decode('latin-1') if isinstance(a, bytes) else a
114 x = ord(a[0]) << 7 if a else 0
115 for c in map(ord, a):
116 x = ((1000003 * x) ^ c) & 0xFFFFFFFFFFFFFFFF
117 x ^= len(a)
118 a = -2 if x == -1 else x
119
120 if version == 2 and isinstance(a, (str, bytes, bytearray)):
121 if isinstance(a, str):
122 a = a.encode()
123 a += _sha512(a).digest()
124 a = int.from_bytes(a, 'big')
125
126 super().seed(a)
127 self.gauss_next = False
128
129 def getstate(self):
130 """Return internal state; can be passed to setstate() later."""
131 return self.VERSION, super().getstate(), self.gauss_next
132
133 def setstate(self, state):
134 """Restore internal state from object returned by getstate()."""
135 version = state[0]
136 if version == 3:
137 version, internalstate, self.gauss_next = state
138 super().setstate(internalstate)
139 elif version == 2:
140 version, internalstate, self.gauss_next = state
141 # In version 2, the state was saved as signed ints, which causes
142 # inconsistencies between 32/64-bit systems. The state is
143 # really unsigned 32-bit ints, so we convert negative ints from
144 # version 2 to positive longs for version 3.
145 try:
146 internalstate = tuple(x % (2**32) for x in internalstate)
147 except ValueError as e:
148 raise TypeError from e
149 super().setstate(internalstate)
150 else:
151 raise ValueError("state with version %s passed to "
152 "Random.setstate() of version %s" %
153 (version, self.VERSION))
154
155 ## ---- Methods below this point do not need to be overridden when
156 ## ---- subclassing for the purpose of using a different core generator.
157
158 ## -------------------- pickle support -------------------
159
160 # Issue 17489: Since __reduce__ was defined to fix #759889 this is no
161 # longer called; we leave it here because it has been here since random was
162 # rewritten back in 2001 and why risk breaking something.
163 def __getstate__(self): # for pickle
164 return self.getstate()
165
166 def __setstate__(self, state): # for pickle
167 self.setstate(state)
168
169 def __reduce__(self):
170 return self.__class__, (), self.getstate()
171
172 ## -------------------- integer methods -------------------
173
174 def _randrange_(self, start, stop, step, _int):
175 """Choose a random item from range(start, stop[, step]).
176
177 This fixes the problem with randint() which includes the
178 endpoint; in Python this is usually not what you want.
179
180 """
181
182 # This code is a bit messy to make it fast for the
183 # common case while still doing adequate error checking.
184 istart = _int(start)
185 if istart != start:
186 raise ValueError("non-integer arg 1 for randrange()")
187 if stop is None:
188 if istart > 0:
189 return self._randbelow(istart)
190 raise ValueError("empty range for randrange()")
191
192 # stop argument supplied.
193 istop = _int(stop)
194 if istop != stop:
195 raise ValueError("non-integer stop for randrange()")
196 width = istop - istart
197 if step == 1 and width > 0:
198 return istart + self._randbelow(width)
199 if step == 1:
200 raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))
201
202 # Non-unit step argument supplied.
203 istep = _int(step)
204 if istep != step:
205 raise ValueError("non-integer step for randrange()")
206 if istep > 0:
207 n = (width + istep - 1) // istep
208 elif istep < 0:
209 n = (width + istep + 1) // istep
210 else:
211 raise ValueError("zero step for randrange()")
212
213 if n <= 0:
214 raise ValueError("empty range for randrange()")
215
216 return istart + istep*self._randbelow(n)
217
218 ## -------------------- sequence methods -------------------
219
220 def choice(self, seq):
221 """Choose a random element from a non-empty sequence."""
222 try:
223 i = self._randbelow(len(seq))
224 except ValueError:
225 raise IndexError('Cannot choose from an empty sequence') from None
226 return seq[i]
227
228 def shuffle(self, x, random=None):
229 """Shuffle list x in place, and return None.
230
231 Optional argument random is a 0-argument function returning a
232 random float in [0.0, 1.0); if it is the default None, the
233 standard random.random will be used.
234
235 """
236
237 if random is None:
238 randbelow = self._randbelow
239 for i in reversed(range(1, len(x))):
240 # pick an element in x[:i+1] with which to exchange x[i]
241 j = randbelow(i+1)
242 x[i], x[j] = x[j], x[i]
243 else:
244 _int = int
245 for i in reversed(range(1, len(x))):
246 # pick an element in x[:i+1] with which to exchange x[i]
247 j = _int(random() * (i+1))
248 x[i], x[j] = x[j], x[i]
249
250 def sample(self, population, k):
251 """Chooses k unique random elements from a population sequence or set.
252
253 Returns a new list containing elements from the population while
254 leaving the original population unchanged. The resulting list is
255 in selection order so that all sub-slices will also be valid random
256 samples. This allows raffle winners (the sample) to be partitioned
257 into grand prize and second place winners (the subslices).
258
259 Members of the population need not be hashable or unique. If the
260 population contains repeats, then each occurrence is a possible
261 selection in the sample.
262
263 To choose a sample in a range of integers, use range as an argument.
264 This is especially fast and space efficient for sampling from a
265 large population: sample(range(10000000), 60)
266 """
267
268 # Sampling without replacement entails tracking either potential
269 # selections (the pool) in a list or previous selections in a set.
270
271 # When the number of selections is small compared to the
272 # population, then tracking selections is efficient, requiring
273 # only a small set and an occasional reselection. For
274 # a larger number of selections, the pool tracking method is
275 # preferred since the list takes less space than the
276 # set and it doesn't suffer from frequent reselections.
277
278 if isinstance(population, _Set):
279 population = tuple(population)
280 if not isinstance(population, _Sequence):
281 raise TypeError("Population must be a sequence or set. For dicts, use list(d).")
282 randbelow = self._randbelow
283 n = len(population)
284 if not 0 <= k <= n:
285 raise ValueError("Sample larger than population or is negative")
286 result = [None] * k
287 setsize = 21 # size of a small set minus size of an empty list
288 if k > 5:
289 setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
290 if n <= setsize:
291 # An n-length list is smaller than a k-length set
292 pool = list(population)
293 for i in range(k): # invariant: non-selected at [0,n-i)
294 j = randbelow(n-i)
295 result[i] = pool[j]
296 pool[j] = pool[n-i-1] # move non-selected item into vacancy
297 else:
298 selected = set()
299 selected_add = selected.add
300 for i in range(k):
301 j = randbelow(n)
302 while j in selected:
303 j = randbelow(n)
304 selected_add(j)
305 result[i] = population[j]
306 return result
307
308 def choices(self, population, weights=None, *, cum_weights=None, k=1):
309 """Return a k sized list of population elements chosen with replacement.
310
311 If the relative weights or cumulative weights are not specified,
312 the selections are made with equal probability.
313
314 """
315 random = self.random
316 if cum_weights is None:
317 if weights is None:
318 _int = int
319 total = len(population)
320 return [population[_int(random() * total)] for i in range(k)]
321 cum_weights = list(_itertools.accumulate(weights))
322 elif weights is not None:
323 raise TypeError('Cannot specify both weights and cumulative weights')
324 if len(cum_weights) != len(population):
325 raise ValueError('The number of weights does not match the population')
326 bisect = _bisect.bisect
327 total = cum_weights[-1]
328 return [population[bisect(cum_weights, random() * total)] for i in range(k)]
329
330 ## -------------------- real-valued distributions -------------------
331
332 ## -------------------- uniform distribution -------------------
333
334
335
336 ## --------------- Operating System Random Source ------------------
337
338 class SystemRandom(Random):
339 """Alternate random number generator using sources provided
340 by the operating system (such as /dev/urandom on Unix or
341 CryptGenRandom on Windows).
342
343 Not available on all systems (see os.urandom() for details).
344 """
345
346 def random(self):
347 """Get the next random number in the range [0.0, 1.0)."""
348 return (int.from_bytes(_urandom(7), 'big') >> 3) * RECIP_BPF
349
350 def getrandbits(self, k):
351 """getrandbits(k) -> x. Generates an int with k random bits."""
352 if k <= 0:
353 raise ValueError('number of bits must be greater than zero')
354 if k != int(k):
355 raise TypeError('number of bits should be an integer')
356 numbytes = (k + 7) // 8 # bits / 8 and rounded up
357 x = int.from_bytes(_urandom(numbytes), 'big')
358 return x >> (numbytes * 8 - k) # trim excess bits
359
360 def seed(self, *args, **kwds):
361 "Stub method. Not used for a system random number generator."
362 return None
363
364 def _notimplemented(self, *args, **kwds):
365 "Method should not be called for a system random number generator."
366 raise NotImplementedError('System entropy source does not have state.')
367 getstate = setstate = _notimplemented
368
369 ## -------------------- test program --------------------
370
371
372 def _test_generator(n, func, args):
373 import time
374 print(n, 'times', func.__name__)
375 total = 0.0
376 sqsum = 0.0
377 smallest = 1e10
378 largest = -1e10
379 t0 = time.time()
380 for i in range(n):
381 x = func(*args)
382 total += x
383 sqsum = sqsum + x*x
384 smallest = min(x, smallest)
385 largest = max(x, largest)
386
387 t1 = time.time()
388 print(round(t1-t0, 3), 'sec,', end=' ')
389 avg = total/n
390 stddev = _sqrt(sqsum/n - avg*avg)
391
392 print('avg %g, stddev %g, min %g, max %g\n' % \
393 (avg, stddev, smallest, largest))
394
395 def _test_generator0(n, func):
396 import time
397 print(n, 'times', func.__name__)
398 total = 0.0
399 sqsum = 0.0
400 smallest = 1e10
401 largest = -1e10
402 t0 = time.time()
403 for i in range(n):
404 x = func()
405 total += x
406 sqsum = sqsum + x*x
407 smallest = min(x, smallest)
408 largest = max(x, largest)
409
410 t1 = time.time()
411 print(round(t1-t0, 3), 'sec,', end=' ')
412 avg = total/n
413 stddev = _sqrt(sqsum/n - avg*avg)
414
415 print('avg %g, stddev %g, min %g, max %g\n' % \
416 (avg, stddev, smallest, largest))
417
418 x = _random.Random()
419 rand = x.random
420
421 def _test(N=2000):
422 _test_generator(N, randint, (10, 20))
423 _test_generator(N, random, ())
424 _test_generator0(N, random)
425 _test_generator0(N, rand)
426 _test_generator(N, normalvariate, (0.0, 1.0))
427 _test_generator(N, lognormvariate, (0.0, 1.0))
428 _test_generator(N, vonmisesvariate, (0.0, 1.0))
429 _test_generator(N, gammavariate, (0.01, 1.0))
430 _test_generator(N, gammavariate, (0.1, 1.0))
431 _test_generator(N, gammavariate, (0.1, 2.0))
432 _test_generator(N, gammavariate, (0.5, 1.0))
433 _test_generator(N, gammavariate, (0.9, 1.0))
434 _test_generator(N, gammavariate, (1.0, 1.0))
435 _test_generator(N, gammavariate, (2.0, 1.0))
436 _test_generator(N, gammavariate, (20.0, 1.0))
437 _test_generator(N, gammavariate, (200.0, 1.0))
438 _test_generator(N, gauss, (0.0, 1.0))
439 _test_generator(N, betavariate, (3.0, 3.0))
440 _test_generator(N, triangular, (0.0, 1.0, 1.0/3.0))
441
442 # Create one instance, seeded from current time, and export its methods
443 # as module-level functions. The functions share state across all uses
444 #(both in the user's code and in the Python libraries), but that's fine
445 # for most programs and is easier for the casual user than making them
446 # instantiate their own Random() instance.
447
448 _inst = Random()
449 seed = _inst.seed
450 random = _inst.random
451 uniform = _inst.uniform
452 triangular = _inst.triangular
453 randint = _inst.randint
454 choice = _inst.choice
455 randrange = _inst.randrange
456 sample = _inst.sample
457 shuffle = _inst.shuffle
458 choices = _inst.choices
459 normalvariate = _inst.normalvariate
460 lognormvariate = _inst.lognormvariate
461 expovariate = _inst.expovariate
462 vonmisesvariate = _inst.vonmisesvariate
463 gammavariate = _inst.gammavariate
464 gauss = _inst.gauss
465 betavariate = _inst.betavariate
466 paretovariate = _inst.paretovariate
467 weibullvariate = _inst.weibullvariate
468 getstate = _inst.getstate
469 setstate = _inst.setstate
470 getrandbits = _inst.getrandbits
471