Linear Congruential Generator in Python

Question

I am writing a LCG function in Python that I will use for a Monte Carlo type simulation for coin flips and generating runs. The problem I am facing is that when I generate a list of random numbers, the numbers are patterned such that odds and evens alternate. I don't know whether that is a property of the LCG function itself or a mistake in how I am generating the numbers.

Here is my code:

def seedLCG(initVal):
    global rand
    rand = initVal

def lcg():
    a = 1140671485
    c = 128201163
    m = 2**24
    global rand
    rand = (a*rand + c) % m
    return rand

seedLCG(1)

for i in range(10):
    print lcg()

Values Returned:

I'm assuming I don't need to worry about overflow and size because int and long are interchanged as needed by Python.

Why do you want to implement your own rather than using python's built-in generator or numpy's options? — pjs, Oct 02 '13 at 15:30
I am simply trying to learn how an LCG works. I did the same simulation with the built in generator as well. — Siddharth Dhingra, Oct 02 '13 at 15:31
Reasonable answer. Now you know that the answer for how an LCG works is "poorly". — pjs, Oct 02 '13 at 15:32
Why don't you use: random.seed(initval) and to get a new value: random.randint(0, 2**24) ? — Michel Keijzers, Oct 02 '13 at 15:34

score 6 · Accepted Answer · edited May 23 '17 at 12:13

6

a*rand multiplies rand by an odd number, so the result is always odd when rand is odd, and even when rand is even. You then add in the odd number c, which changes odd to even and vice versa. The modulo has no effect on the last bit. So, every call to lcg flips rand from odd to even or from even to odd.

If you're serious about random numbers (but you don't need crypto-strength ones), consider using numpy.random.

edited May 23 '17 at 12:13

Community

1
1

answered Oct 02 '13 at 15:27

Fred Foo

355,277
75
744
836

Okay, that makes sense. I have a couple follow up questions. Why does modulo have no effect on the last bit? Is this then a property of all LCG generators or would changing the parameter "a" change "a*rand" to always have an even value have an effect? – Siddharth Dhingra Oct 02 '13 at 15:33
@SiddharthDhingra: because modulo 2^k never affects the lower-order k bits. As for `a*rand`, that would multiply by an odd number, having no effect on the evenness. – Fred Foo Oct 02 '13 at 15:35

ulrichtsblr · Answer 2 · 2021-04-03T21:08:39.010

A tad late to the party, but it might be interesting to others. In Python 3, a pseudorandom number generator can be constructed by defining the following two functions:

def lcg(x, a, c, m):
    while True:
        x = (a * x + c) % m
        yield x


def random_uniform_sample(n, interval, seed=0):
    a, c, m = 1103515245, 12345, 2 ** 31
    bsdrand = lcg(seed, a, c, m)

    lower, upper = interval[0], interval[1]
    sample = []

    for i in range(n):
        observation = (upper - lower) * (next(bsdrand) / (2 ** 31 - 1)) + lower
        sample.append(round(observation))

    return sample

The first function is the actual LCG implemented as a generator (i.e. a function returning an iterable object), while the second function iterates over the generator object to obtain a sample. The latter function would typically be called by an end user to generate pseudorandom numbers within a given interval.

After defining both functions, they can be employed as follows:

# 30 numbers between 0 and 100
rus = random_uniform_sample(30, [0, 100])
print(rus)

Output:

[0, 66, 30, 67, 11, 52, 49, 60, 37, 26, 37, 83, 17, 30, 64, 79, 99, 80, 46, 54, 63, 25, 70, 72, 98, 33, 45, 71, 74, 17]

score 3 · Answer 3 · edited Nov 21 '18 at 08:35

3

I believe you forgot to divide rand by your mod in the return statement. It should look like this:

def lcg():
    a = 1140671485
    c = 128201163
    m = 2**24
    global rand
    rand = (a*rand + c) % m
    return rand / m

Source: http://people.duke.edu/~ccc14/sta-663-2016/15A_RandomNumbers.html

edited Nov 21 '18 at 08:35

sshine

15,635
1
41
66

answered Jun 26 '17 at 00:43

Mark Switajski

59
1
1
6

NB: "The LCG is typically coded to return z/m, a floating point number in (0, 1). This can be scaled to any other range (a,b)." Yes, if that is what one intends with their LCG, but if you want to generate numbers as the OP gave (i.e., in the range [0, 2**24 -1], then no, you wouldn't. – user1441004 Aug 25 '22 at 23:13

Linear Congruential Generator in Python

3 Answers3