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
– pjs, Commented Oct 2, 2013 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
– Siddharth Dhingra, Commented Oct 2, 2013 at 15:31
Reasonable answer. Now you know that the answer for how an LCG works is "poorly". — pjs
– pjs, Commented Oct 2, 2013 at 15:32
Why don't you use: random.seed(initval) and to get a new value: random.randint(0, 2**24) ? — Michel Keijzers
– Michel Keijzers, Commented Oct 2, 2013 at 15:34

Community · Accepted Answer · 2017-05-23 12:13:05Z

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, 2017 at 12:13

CommunityBot

11 silver badge

answered Oct 2, 2013 at 15:27

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Siddharth Dhingra Over a year ago

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?

Fred Foo Over a year ago

@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.

ulrichtsblr · Accepted Answer · 2021-04-03 21:08:39Z

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]

sshine · Accepted Answer · 2018-11-21 08:35:28Z

2

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, 2018 at 8:35

sshine

16.2k1 gold badge45 silver badges71 bronze badges

answered Jun 26, 2017 at 0:43

Mark Switajski

571 gold badge1 silver badge6 bronze badges

1 Comment

user1441004 Over a year ago

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.

Collectives™ on Stack Overflow

Linear Congruential Generator in Python

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related