Mercurial > public > think_complexity

comparison ch6ex2.py @ 41:d4d9650afe1e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 2, create a linear congruential generator.
author Brian Neal <bgneal@gmail.com>
date Sun, 13 Jan 2013 13:10:46 -0600
parents
children
comparison
equal deleted inserted replaced
40:ae310a2f42b4 41:d4d9650afe1e
1 """Chapter 6, exercise 2 in Allen Downey's Think Complexity book.
2
3 1. Write a program that implements one of the linear congruential generators
4 described at http://en.wikipedia.org/wiki/Linear_congruential_generator
5
6 """
7
8 class LCG(object):
9 """A class to implement a Linear Congruential Generator (LCG) pseudo-random
10 number generator.
11
12 """
13 def __init__(self, a=1103515245, c=12345, m=2**31,
14 output=lambda x: x & 0x7fffffff):
15 """The parameters a, c, and m are the LCG parameters:
16 xn = (a * xn + c) % m
17
18 The parameter output must be a function that transforms the next output
19 value. This can be used to shift or mask off various bits to
20 statistically improve the values produced.
21
22 """
23 self.a = a
24 self.c = c
25 self.m = m
26 self.xn = 0
27 self.output = output
28
29 def seed(self, val):
30 """Seed the pseudo-random number generator with the value val."""
31 self.xn = val
32
33 def rand(self):
34 """Generate and return the next pseudo-rando number in the sequence."""
35 self.xn = (self.a * self.xn + self.c) % self.m
36 return self.output(self.xn)
37
38
39 def main(script, prng):
40 """Rig up either our random number generator or Python's to produce output
41 on stdout so we can test it with dieharder:
42
43 $ python ch6ex2.py lcg | dieharder -a -g 200 # to test ours
44 $ python ch6ex2.py python | dieharder -a -g 200 # to test Python
45
46 """
47 import struct
48 import random
49
50 lcg = LCG()
51 py_rng = lambda : random.randint(0, 0xffffffff)
52
53 if prng == 'python':
54 r = py_rng
55 else:
56 r = lcg.rand
57
58 while True:
59 n = r()
60 s = struct.pack('>L', n)
61 sys.stdout.write(s)
62
63
64 if __name__ == '__main__':
65 import sys
66 main(*sys.argv)