Simple PRNG algorithm has different Python/C output - integer overflow differences?

Question

Edit: As it turns out, I typoed the seed value in my test code in the C version (It wasn't the same as I pasted in this question), so I was getting different output. Thanks everyone.

I need to generate psuedo random numbers in a C program, and then pass the seed to a Python program later and generate the same numbers.

PRNGs are something that I consider over my head, so I looked up an implemention (in C):

static unsigned long next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    next = next * 1103515245 + 12345;
    return((unsigned)(next/65536) % 32768);
}

And a naive port:

next = 1

def myrand():
    global next
    next = next * 1103515245 + 12345
    return (next / 65536) % 32768

However, these both produce different values. I'm guessing next in the C implementation overflows, and that's why the two functions produce different values. But in Python numbers have no explicit type, they don't overflow, and they're not unsigned. How can I replicate this behavior in Python?

Thanks in advance.

Answer 1

Taking every computation modulo (%) 2^32 (assuming 32 bit integer width) should work.

next = 1
modulo = 2**32
def myrand():
    global next
    next = ((next * 1103515245) + 12345) % modulo
    return (next / 65536) % 32768

Answer 2

You don't want to use a global variable here, the problem is more suited to a generator function. Also you certainly don't want to use next as a variable name in python because it shadows a very useful builtin name (actually I'm using it below!)

def myrand(seed=1):
    n = seed
    while True:
      n = n * 1103515245 + 12345
      yield (n // 65536) % 32768


g = myrand()
print(next(g))
print(next(g))
print(next(g))

This works for me on python3, apparently no overflow handling needn't, and matches your first 3 inputs. Could you post a few more so we can see where/why they may diverge?

Answer 3

next = 1
def myrand():
    global next
    next = next * 1103515245 + 12345
    return (next & 0xFFFFFFFF / 65536) % 32768