generating_pseudorandom_numbers.py

"""
A function that generates pseudo-random numbers.

The approach generally taken in generating random numbers is to
simulate random processes by generating a deterministic sequence of
numbers with uniform distribution.

By choosing random numbers as the first input i.e. the seed to this
function the sequence of numbers generated by different seeds are
seemingly random and uniformly distributed as would be in truly
random processes.

The algorithm used is the linear congruential method.

Successive numbers in the sequence are generated by:

Xn+1 = (AXn + B) % M

where: 
- Xn+1 is the next number in the sequence
- Xn is the latest number in the sequence, or the seed
- A, B and M are the multiplier, increment and modulus respectively

The range of the seed should be 0 or greater but less than M
i.e.0 <= Xn < M and n = 1

M should be greater than or equal to the length of the random sequence
required.

If M is a power of 2, A mod 8 should be 5

If M is a power of 10, A mod 200 should be 21

A should be larger than sqrt(M) but less than M - sqrt(M)
i.e. sqrt(M) < A < (M - sqrt(M))

(A - 1) should be a multiple of every prime divisor of M, and if M is
a multiple of 4, then (A - 1) should also be a multiple of 4.

B should be relatively prime to M i.e. they should have a gcd of 1

B should be odd, and not a multiple of 5

A sample set of parameters that would satisfy the above criteria are:

- 4096 for M
- 109 for A
- 853 for B

The generator could be implemented as below:
"""


def make_lcm_generator(multiplier, increment, modulus):
    """Returns a pseudo-random lcm generator with the given params"""

    def lcm(x):
        """Xn+1 = (AXn + B) % M"""

        return (multiplier * x + increment) % modulus
        
    
    def lcm_generator(seed, count):
        """Generates random numbers of the given count using the seed

        The range of the seed should be 0 or greater but less than the
        modulus
        """
        assert 0 <= seed < modulus and count > 0

        x = seed
        for i in range(count):
            x = lcm(x)
            yield x

    return lcm_generator


lcm_generator = make_lcm_generator(multiplier=109, increment=853, modulus=4096)

assert list(lcm_generator(seed=42, count=3)) == [1335, 3008, 1045]


"""
The sequence should repeat itself after M random numbers, where M is
the modulus

"""
l = list(lcm_generator(seed=42, count=(4096 * 2)))

assert l[:4096] == l[4096:]


"""
Should display a uniform distribution. Plot with matplotlib if installed

> pip install matplotlib pyqt5
"""

try:
    import matplotlib.pyplot as plt
except ImportError:
    pass
else:
    l = l[:4096]
    num_bins = 64
    plt.hist(l, num_bins, facecolor='blue', alpha=0.5)
    plt.show()