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