Pseudo random number generator in python

Question

I tried to perform the following code using python:

My code is:

#UNIFORM RANDOM SAMPLING 

import numpy as np                #library needed for numerical calculations
import matplotlib.pyplot as plt   #library needed for plotting purposes
from time import process_time     #function needed for checking CPU time
from scipy.stats import chisquare #function needed for chi square test

#*******************************************************************************

i=np.uintc(987654321)              #unsigned int variable i with seed 987654321

r=2**30                            #range of the sequence

t1_start=process_time()            #process start time 

for count in range(r):             #for cycle over expected period and update i

    i=np.uintc(i*663608941)

t1_stop=process_time()             #process stop time
    
print("\nLoop stopped at the element:", i, ".\n")     
print("Is this the last element of the series? 1 for YES other numbers for NO", i/987654321,".\n")
print("The CPU time needed in order to take to go throught the whole sequence is", t1_stop-t1_start, "seconds.\n")

Meanwhile the output:

As you can see, the programm woks, but is not very optimized ( almost 1 hour of run).

How can I optimize it and obtain the desired output in many seconds?

Answer 1

Do you have to use Python?

The code will run much faster in C. When compiled with -O3 optimization, this takes about a second to run on my desktop:

#include <stdio.h>
#include <inttypes.h>

int main() {
    uint32_t i, n;
    i = 987654321;
    n = 0;
    while (1) {
        n++;
        i *= 663608941;
        if (i == 987654321) break;
    }
    printf("Sequence repeats after %" PRIu32 " iterations.\n", n);
    printf("Expected value: %d.\n", 1<<30);
    return 0;
}

I should also point out that your code isn't strictly correct. It confirms that the sequence returns to its initial state after 2³⁰ iterations, but doesn't check for other occurrences of i=987654321 during the loop.

---

If you're stuck using Python, it looks like numpy's integer types don't offer much of an advantage in terms of speed. The following code runs in about 200 seconds on my machine.:

def seq_check():
    x = 987654321
    n = 0
    while True:
        n += 1
        x = (x * 663608941) & 0xffffffff
        if x == 987654321:
            break
    return n