Mercurial > public > think_complexity

annotate ch6ex2.py @ 41:d4d9650afe1e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Chapter 6, exercise 2, create a linear congruential generator.
author Brian Neal <bgneal@gmail.com>
date Sun, 13 Jan 2013 13:10:46 -0600
parents
children
rev   line source
bgneal@41 1 """Chapter 6, exercise 2 in Allen Downey's Think Complexity book.
bgneal@41 2
bgneal@41 3 1. Write a program that implements one of the linear congruential generators
bgneal@41 4 described at http://en.wikipedia.org/wiki/Linear_congruential_generator
bgneal@41 5
bgneal@41 6 """
bgneal@41 7
bgneal@41 8 class LCG(object):
bgneal@41 9 """A class to implement a Linear Congruential Generator (LCG) pseudo-random
bgneal@41 10 number generator.
bgneal@41 11
bgneal@41 12 """
bgneal@41 13 def __init__(self, a=1103515245, c=12345, m=2**31,
bgneal@41 14 output=lambda x: x & 0x7fffffff):
bgneal@41 15 """The parameters a, c, and m are the LCG parameters:
bgneal@41 16 xn = (a * xn + c) % m
bgneal@41 17
bgneal@41 18 The parameter output must be a function that transforms the next output
bgneal@41 19 value. This can be used to shift or mask off various bits to
bgneal@41 20 statistically improve the values produced.
bgneal@41 21
bgneal@41 22 """
bgneal@41 23 self.a = a
bgneal@41 24 self.c = c
bgneal@41 25 self.m = m
bgneal@41 26 self.xn = 0
bgneal@41 27 self.output = output
bgneal@41 28
bgneal@41 29 def seed(self, val):
bgneal@41 30 """Seed the pseudo-random number generator with the value val."""
bgneal@41 31 self.xn = val
bgneal@41 32
bgneal@41 33 def rand(self):
bgneal@41 34 """Generate and return the next pseudo-rando number in the sequence."""
bgneal@41 35 self.xn = (self.a * self.xn + self.c) % self.m
bgneal@41 36 return self.output(self.xn)
bgneal@41 37
bgneal@41 38
bgneal@41 39 def main(script, prng):
bgneal@41 40 """Rig up either our random number generator or Python's to produce output
bgneal@41 41 on stdout so we can test it with dieharder:
bgneal@41 42
bgneal@41 43 $ python ch6ex2.py lcg | dieharder -a -g 200 # to test ours
bgneal@41 44 $ python ch6ex2.py python | dieharder -a -g 200 # to test Python
bgneal@41 45
bgneal@41 46 """
bgneal@41 47 import struct
bgneal@41 48 import random
bgneal@41 49
bgneal@41 50 lcg = LCG()
bgneal@41 51 py_rng = lambda : random.randint(0, 0xffffffff)
bgneal@41 52
bgneal@41 53 if prng == 'python':
bgneal@41 54 r = py_rng
bgneal@41 55 else:
bgneal@41 56 r = lcg.rand
bgneal@41 57
bgneal@41 58 while True:
bgneal@41 59 n = r()
bgneal@41 60 s = struct.pack('>L', n)
bgneal@41 61 sys.stdout.write(s)
bgneal@41 62
bgneal@41 63
bgneal@41 64 if __name__ == '__main__':
bgneal@41 65 import sys
bgneal@41 66 main(*sys.argv)