I'm using a 64 bit LCG (MMIX (by Knuth)). It generate a certain block of random numbers inside my code, which use them to perform some operations. My code works in single core and I would like to parallelize the work to reduce the execution time.
Before start thinking to more advanced methods in this sense I'd like to simply execute more identical codes in parallel (in fact the code repeats the same task over a certain numbers of indipendent simulation, so I can simply split the number of simulation between more identical codes and run them in parallel).
My only problem now is to find a seed for each code; in particular, to avoid the possibility of unwanted non trivial correlation between data generated in different codes, I have to be sure that the random number generated in the various codes don't overlap. To do so, starting from a certain seed in the first code I have to find a way to find a value (the next seed) very distant not in absolute value but in the pseudo-random sequence (so, such that, to go from the first to the second seed, I need a huge number of steps of LCG).
My first attempt was this:
starting from the LCG relation between 2 consecutive numbers generated in the sequence
So, in principle, I could calculate the above relation with, say, n = 2^40 and I_0 equal to the value of the first seed, and obtain a new seed distant 2^40 steps in the random CLG sequence from the first one.
The problem is that, doing so, I necessary go in overflow calculating a^n. In fact for MMIX (by Knuth) a~2^62 and i use unsigned long long int (64 bit). Note that the only problem here is the fraction in the above relation. If there only were sum and multiplication I could ignore the overflow problem due to the following modular properties (in fact I'm using 2^64 as c (64 bit generator)):
那么，从某个值（第一个种子）开始，我怎样才能在 LC 伪随机序列中找到距离大量步长的第二个种子呢？
[EDIT]
r3mainer solution is perfectly suited for python codes. I'm trying now to implement it in c using unsigned __int128 variables. I have only one problem: in principle I should compute:
假设，为了简单起见，我想计算：
其中 n = 2^40 和 c(a-1)~2^126。我继续一个循环。从temp = a，在每次迭代中我计算temp = temp*temp，然后我计算temp%c(a-1)。问题出在第二步（temp = temp*temp). temp事实上，原则上可以是任何 temp是一个很大的数字，比如说 > 2^64，我会溢出，在下一个模块操作之前达到 2^128 - 1。那么有没有办法避免呢？目前，我看到的唯一解决方案是通过位循环执行每个乘法，如下所示：c代码：防止在具有巨大模块的模块化操作中溢出（模块接近溢出阈值） https://stackoverflow.com/questions/66180370/c-code-prevent-overflow-in-modular-operation-with-huge-modules-modules-near-th还有另一种方法可以在乘法期间执行模运算吗？
（请注意，c = 2^64，使用 mod(c) 操作我没有相同的问题，因为溢出点（对于 ull int 变量）与模块一致）
任何以下形式的 LCGx[n+1] = (x[n] * a + c) % m可以非常快速地跳到任意位置。
从种子值为零开始，LCG 的前几次迭代将给出以下序列：
x₀ = 0
x₁ = c % m
x₂ = (c(a + 1)) % m
x₃ = (c(a² + a + 1)) % m
x₄ = (c(a³ + a² + a + 1)) % m
很容易看出，每一项实际上都是几何级数的总和，可以用以下公式计算：简单的公式 https://en.wikipedia.org/wiki/Geometric_series#Sum:
x_n = (c(a^{n-1} + a^{n-2} + ... + a + 1)) % m
= (c * (a^n - 1) / (a - 1)) % m
The (a^n - 1)项可以通过以下方式快速计算模幂 https://en.wikipedia.org/wiki/Modular_exponentiation，但除以(a-1)有点棘手，因为(a-1) and m都是偶数（即不互质），所以我们无法计算模乘逆 https://en.wikipedia.org/wiki/Modular_multiplicative_inverse of (a-1) mod m直接地。
相反，计算(a^n-1) mod m*(a-1)，然后对结果进行直接（非模块化）除法a-1。在 Python 中，计算过程如下：
def lcg_skip(m, a, c, n):
# Calculate nth term of LCG sequence with parameters m (modulus),
# a (multiplier) and c (increment), assuming an initial seed of zero
a1 = a - 1
t = pow(a, n, m * a1) - 1
t = (t * c // a1) % m
return t
def test(nsteps):
m = 2**64
a = 6364136223846793005
c = 1442695040888963407
#
print("Calculating by brute force:")
seed = 0
for i in range(nsteps):
seed = (seed * a + c) % m
print(seed)
#
print("Calculating by fast method:")
# Calculate nth term by modular exponentiation
print(lcg_skip(m, a, c, nsteps))
test(1000000)
因此，要创建具有不重叠输出序列的 LCG，您需要做的就是使用由lcg_skip()值为n相距足够远。