pattern

xorshift  linear

2 3 4 1  1 0 0 1
      2

0 0 0 1  0 0 0 0  10
0 0 1 0  1 0 0 1  29
0 1 0 0  0 0 1 0  42
1 0 0 1  1 0 1 1  9b
0 0 1 1  0 1 0 0  34
0 1 1 0  1 1 0 1  6d
1 1 0 1  0 1 1 0  d6
1 0 1 0  1 1 1 1  af
0 1 0 1  1 0 0 0  58
1 0 1 1  0 0 0 1  b1
0 1 1 1  1 0 1 0  7a
1 1 1 1  0 0 1 1  f3
1 1 1 0  1 1 0 0  ec
1 1 0 0  0 1 0 1  c5
1 0 0 0  1 1 1 0  8e
         0 1 1 1   7

prng.py

import math
import random


"""
start by defining functions for evaluating ideal qualities for a psuedo-random
sequence
"""


def distribution(xs):
    return {
        v: xs.count(v)
        for v in set(xs)
    }


def period(xs):
    xs = list(xs)
    l = len(xs)
    for n in range(1, l):
        if bool(l % n):
            continue
        k = l // n
        if xs == k * xs[:n]:
            return n
    return l


# https://en.wikipedia.org/wiki/Approximate_entropy
def appent(xs, m, r):
    xs = list(xs)
    def maxdist(xs, ys):
        return max(abs(x - y) for (x, y) in zip(xs, ys))
    def phi(xs, m, r):
        d = 1 + len(xs) - m
        ms = [xs[i:i + m] for i in range(d)]
        return 1 / d * sum(
            math.log(sum(int(maxdist(m1, m2) <= r) for m2 in ms) / d)
            for m1 in ms
        )
    return abs(phi(xs, 1+m, r) - phi(xs, m, r))


def doeval(xs):
    xs = list(xs)
    print("distribution:")
    for (v, n) in sorted(distribution(xs).items()):
        print("  {}: {}".format(v, n))
    print("period: {}".format(period(xs)))
    print("approximate entropy: {}".format(appent(xs, 2, 0.5)))


"""
provide reference data sets via native PRNG
"""


def reference(n):
    return [random.randint(0, n-1) for _ in range(240)]


"""
define PRNG to be evaluated
"""


def recur(func, seed, iterations):
    x = seed
    xs = []
    for i in range(iterations):
        xs += [x]
        x = func(x)
    return xs


f = lambda x: (x << 1 | (x >> 3) ^ (x >> 2 & 1)) % 16
g = lambda x: (x + 9) % 16

"""
f has a period of 15
g has a period of 16
combining the results of the two produces a period of 240
"""


q = lambda x: 16 * f(x // 16) + g(x % 16)
q = recur(q, 0x10, 240)

d2 = [(x // 16 ^ x // 8) % 2 for x in q]
d3 = [x % 3 for x in q]
d4 = [(x // 16 ^ x // 4) % 4 for x in q]
d5 = [x % 5 for x in q]
d6 = [(x // 16 ^ x) % 6 for x in q]
d8 = [(x // 16 ^ x // 2) % 8 for x in q]

prng.results

>>> doeval(reference(2))
distribution:
  0: 121
  1: 119
period: 240
approximate entropy: 0.6902154137814831
>>> doeval(d2)
distribution:
  0: 120
  1: 120
period: 240
approximate entropy: 0.6908940539488249

>>> doeval(reference(3))
distribution:
  0: 79
  1: 85
  2: 76
period: 240
approximate entropy: 1.0388759434520969
>>> doeval(d3)
distribution:
  0: 80
  1: 80
  2: 80
period: 240
approximate entropy: 0.9991869110581675

>>> doeval(reference(4))
distribution:
  0: 59
  1: 58
  2: 56
  3: 67
period: 240
approximate entropy: 1.2997511163853064
>>> doeval(d4)
distribution:
  0: 60
  1: 60
  2: 60
  3: 60
period: 240
approximate entropy: 1.3429198891196643

>>> doeval(reference(5))
distribution:
  0: 42
  1: 54
  2: 49
  3: 41
  4: 54
period: 240
approximate entropy: 1.284945103505628
>>> doeval(d5)
distribution:
  0: 48
  1: 48
  2: 48
  3: 48
  4: 48
period: 240
approximate entropy: 1.2002898658059271

>>> doeval(reference(6))
distribution:
  0: 49
  1: 42
  2: 38
  3: 38
  4: 33
  5: 40
period: 240
approximate entropy: 1.3711791365774526
>>> doeval(d6)
distribution:
  0: 40
  1: 40
  2: 40
  3: 40
  4: 40
  5: 40
period: 240
approximate entropy: 1.364340301927344

>>> doeval(reference(8))
distribution:
  0: 35
  1: 19
  2: 28
  3: 40
  4: 26
  5: 31
  6: 31
  7: 30
period: 240
approximate entropy: 1.1536780843024355
>>> doeval(d8)
distribution:
  0: 30
  1: 30
  2: 30
  3: 30
  4: 30
  5: 30
  6: 30
  7: 30
period: 240
approximate entropy: 1.1634445701682283