# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1358104246 21600
# Node ID d4d9650afe1e7ee1e05d8f1236ee3c71dc1dc578
# Parent  ae310a2f42b4c7fe8500448dce1fc036f9eeeb54
Chapter 6, exercise 2, create a linear congruential generator.

diff -r ae310a2f42b4 -r d4d9650afe1e ch6ex2.py
--- /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)