是否有任何(非加密)伪随机数生成器可以在 O(1) 中跳过/删除 N 个绘图,或者可能是 O(log N) 但小于 O(N)。
特别是对于并行应用,拥有上述类型的发生器将是有利的。您想要生成随机数数组的图像。人们可以为此任务编写一个并行程序,并独立地为每个线程播种随机数生成器。但是,数组中的数字将与顺序情况不同(可能除了前半部分)。
如果存在上述类型的随机数生成器,则第一个线程可以使用用于顺序实现的种子进行播种。第二个线程也可以使用该种子进行播种,然后删除/跳过第一个线程生成的 N/2 个样本。输出数组将与串行情况相同(易于测试),但生成时间仍然较短。
下面是一些伪代码。
#define _POSIX_C_SOURCE 1
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
void rand_r_skip(unsigned int *p_seed, int N)
{
/* Stupid O(N) Implementation */
for (int i = 0; i < N; i++)
{
rand_r(p_seed);
}
}
int main()
{
int N = 1000000;
unsigned int seed = 1234;
int *arr = (int *)malloc(sizeof(int) * N);
#pragma omp parallel firstprivate(N, seed, arr) num_threads(2)
{
if (omp_get_thread_num() == 1)
{
// skip the samples, obviously doesn't exist
rand_r_skip(&seed, N / 2);
}
#pragma omp for schedule(static)
for (int i = 0; i < N; i++)
{
arr[i] = rand_r(&seed);
}
}
return 0;
}
非常感谢大家的帮助。我确实知道可能有证据表明这样的生成器不可能存在并且同时是“伪随机”的。我非常感谢您提供有关在哪里可以找到更多信息的提示。
Sure. 线性同余发生器及其后代可以跳过一代N
中的数字O(log(N))
时间。基于F.Brown的论文,link.
Here是这个想法的实现,C++11。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)