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