Mercurial > public > think_complexity

comparison ch6ex2_4.py @ 42:039249efe42f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 2, #4. Wrote a program to output the center column of a rule 30 CA as a stream of bytes. It is very slow though. It has to run a very long time to produce enough data for dieharder. Committing it now but will have to let it run overnight or something to generate a large file.
author Brian Neal <bgneal@gmail.com>
date Sun, 13 Jan 2013 16:24:00 -0600
parents
children
comparison
equal deleted inserted replaced
41:d4d9650afe1e 42:039249efe42f
1 """Chapter 6, exercise 2 in Allen Downey's Think Complexity book.
2
3 4. Implement a Rule 30 CA on a ring with a few hundred cells, run it for as many
4 time steps as you can in a reasonable amount of time, and output the center
5 column as a sequence of bits. Test it using DieHarder.
6
7 We'll take a slightly different tact. We will create a program that will
8 continually output the center column as a bit stream. Once we reach the end of
9 the time steps, we'll copy the last row to row 0 and start again. This way we
10 can feed the data into dieharder over a pipe without it exhausting our stream.
11
12 """
13 import sys
14
15 from CircularCA import CircularCA
16
17
18 def main(script, bytes_wanted):
19
20 bytes_wanted = int(bytes_wanted)
21
22 # Create a circular CA that is 257 columns; it is odd so that we have a true
23 # "center" column. Our CA will have 8192 steps. This will give us 8192
24 # / 8 == 1024 bytes of pseudo-random (we hope) data using rule 30. Once
25 # we've reached the end of the time steps, we'll copy the last row to the
26 # first and start over.
27
28 rows = 8193
29 cols = 257
30 mid = cols // 2
31 ca = CircularCA(30, rows, cols)
32 ca.start_single()
33
34 iters = 0
35 bytes_produced = 0
36 while True:
37 ca.loop(rows - 1)
38
39 iters += 1
40 if iters == 1:
41 # don't use the first iteration as the first few rows will have 0's
42 # until it fills up
43 ca.wrap()
44 continue
45
46 a = ca.get_array(mid, mid + 1)
47
48 # output the bit stream a byte at a time
49 x = 0
50 i = 0
51 for n, item in enumerate(a):
52 # don't use the first bit because it is a repeat from the previous
53 # iteration
54 if n == 0:
55 continue
56
57 x <<= 1
58 x |= item[0]
59 i += 1
60 if i == 8:
61 sys.stdout.write(chr(x))
62 x = 0
63 i = 0
64 bytes_produced += 1
65 if bytes_produced >= bytes_wanted:
66 return # we're done
67
68 # now start the CA over:
69 ca.wrap()
70
71
72 if __name__ == '__main__':
73 main(*sys.argv)