Mercurial > public > think_complexity
annotate ch6ex2_4.py @ 42:039249efe42f
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 |
| rev | line source |
|---|---|
| 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) |