Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from math import log, exp, sqrt, floor, ceil, log2
- import itertools as IT
- import random
- from collections import Counter
- MOD = 2**31
- def rint(m):
- return random.randrange(0, m)
- def ansic(seed=None):
- M = 2**31
- if seed is None:
- seed = rint(0, M)
- while True:
- seed = (seed * 1103515245 + 12345) % M
- yield seed >> 16
- def randu(seed=None):
- if seed is None:
- seed = rint(MOD)
- while True:
- seed = (seed * 65539) % MOD
- yield seed
- def park_miller(seed=None):
- if seed is None:
- seed = rint(MOD)
- while True:
- seed = (seed * 16807) % (MOD-1)
- yield seed
- def java(seed=None):
- F = 2**48
- if seed is None:
- seed = rint(F)
- while True:
- seed = (seed * 25214903917 + 11) % (F-1)
- yield seed >> 16
- def prng_to_bits(rng, nbits):
- while True:
- b = bin(next(rng))[2:]
- yield from (int(bi) for bi in reversed(b))
- yield from IT.repeat(0, nbits - len(b))
- def create_bits(rng, nbits, m):
- def bits():
- yield from prng_to_bits(rng(rint(m)), nbits)
- bits.__name__ = rng.__name__ + "_bits"
- return bits
- park_miller_bits = create_bits(park_miller, 31, MOD)
- randu_bits = create_bits(randu, 31, MOD)
- ansic_bits = create_bits(ansic, 15, MOD)
- java_bits = create_bits(java, 32, 2**48)
- def python_bits():
- while True:
- yield random.getrandbits(1)
- def count_bits(n):
- return bin(n).count("1")
- def ones_test(prng, n=200):
- ones = sum(count_bits(next(prng)) for _ in range(n))
- expected = n / 2
- stdev = sqrt(n / 4)
- lo, hi = round(expected - 2 *stdev), round(expected + 2 * stdev)
- if not lo < ones < hi:
- # print("Ones not {} < {} < {} - {}".format(lo, ones, hi, prng.__name__))
- return 0
- return 1
- def count_bit_runs(prng, n=1000):
- return Counter(len(list(g)) for
- k, g in IT.groupby(IT.islice(prng, n)) if k == 1)
- def runs_test(prng, nbits=100000):
- runs = count_bit_runs(prng, nbits)
- longest_run = max(runs.keys())
- eruns, esdev = -log(nbits/2)/log(0.5), 1 / log(2)
- rlo, rhi = ceil(eruns - 2 * esdev), floor(eruns + 2 * esdev)
- if not rlo <= longest_run <= rhi:
- # print("Run not {} < {} < {} - {}".format(rlo, longest_run, rhi, prng.__name__))
- return 0
- return 1
- def tests(prng, nbits=100000):
- s1 = ones_test(prng, n=nbits)
- s2 = runs_test(prng, nbits)
- return s1 + s2
- N = 10000
- ncases = 50
- for rng in (park_miller_bits, randu_bits, java_bits, python_bits, ansic_bits):
- score = 0
- for i in range(ncases):
- score += tests(rng(), N)
- print("{:16s} {}/{}".format(rng.__name__, score, 2*ncases))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement