Python中的伪随机数生成器。

Question

Python中的伪随机数生成器。

3

我尝试使用Python执行以下代码：

我的代码如下：

#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")

与此同时，输出结果如下：

可以看到，程序能够运行，但不是很优化（大约需要1小时的运行时间）。

我该如何优化它以在几秒钟内获得所需的输出？

- J.Snowden

我认为没有太多空间可以优化。那么987654321*pow(663608941, 2**30, 0xFFFFFFFF)怎么样？ - Dummmy

可以，谢谢！但是我不明白0xFFFFFFF是什么意思？ - J.Snowden

基本上是 987654321* 663608941^(2**30) % 0xFFFFFFFF)。0xFFFFFFFF 是32位整数的最大值。mod 0xFFFFFFFF 的目的是模拟32位整数的算术运算。pow 函数在内部使用模幂算法，比直接迭代算法更有效率。但正如 @r3mainer 所说，它不检查较短序列长度。因此可能偏离问题描述的要点。 - Dummmy

@r3mainer 你说得对。感谢指出这一点。应该是 987654321*pow(663608941, 2**30, 1<<32)。 - Dummmy

这个问题看起来像是对2000年前的递归印度指数算法的某种邀请。该算法的时间复杂度为O(log n)，而不是O(n)，其中n为指数。 - jpmarinier

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- r3mainer · Accepted Answer

你必须使用Python吗？

使用C编写的代码运行速度更快。当使用-O3优化进行编译时，在我的桌面上运行大约需要一秒钟：

#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;
}

我还应该指出你的代码并不严格正确。它确认序列在2的30次方次迭代后返回其初始状态，但没有检查循环期间i=987654321的其他出现情况。

如果你使用Python，似乎numpy的整数类型在速度方面并没有太大优势。下面的代码在我的机器上运行约200秒。

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