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