--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ch6ex2.py	Sun Jan 13 13:10:46 2013 -0600
@@ -0,0 +1,66 @@
+"""Chapter 6, exercise 2 in Allen Downey's Think Complexity book.
+
+1. Write a program that implements one of the linear congruential generators
+   described at http://en.wikipedia.org/wiki/Linear_congruential_generator
+
+"""
+
+class LCG(object):
+    """A class to implement a Linear Congruential Generator (LCG) pseudo-random
+    number generator.
+
+    """
+    def __init__(self, a=1103515245, c=12345, m=2**31,
+            output=lambda x: x & 0x7fffffff):
+        """The parameters a, c, and m are the LCG parameters:
+            xn = (a * xn + c) % m
+
+        The parameter output must be a function that transforms the next output
+        value. This can be used to shift or mask off various bits to
+        statistically improve the values produced.
+
+        """
+        self.a = a
+        self.c = c
+        self.m = m
+        self.xn = 0
+        self.output = output
+
+    def seed(self, val):
+        """Seed the pseudo-random number generator with the value val."""
+        self.xn = val
+
+    def rand(self):
+        """Generate and return the next pseudo-rando number in the sequence."""
+        self.xn = (self.a * self.xn + self.c) % self.m
+        return self.output(self.xn)
+
+
+def main(script, prng):
+    """Rig up either our random number generator or Python's to produce output
+    on stdout so we can test it with dieharder:
+
+        $ python ch6ex2.py lcg | dieharder -a -g 200        # to test ours
+        $ python ch6ex2.py python | dieharder -a -g 200     # to test Python
+
+    """
+    import struct
+    import random
+
+    lcg = LCG()
+    py_rng = lambda : random.randint(0, 0xffffffff)
+
+    if prng == 'python':
+        r = py_rng
+    else:
+        r = lcg.rand
+
+    while True:
+        n = r()
+        s = struct.pack('>L', n)
+        sys.stdout.write(s)
+
+
+if __name__ == '__main__':
+    import sys
+    main(*sys.argv)