0

我能找到的大多数随机函数是一个序列函数，它将最后生成的结果作为下一次调用的种子

我想要一个可以自行运行的纯函数，并且可以给出看似随机的序列，给定从开始到结束的任何数字和一个种子

老实说，我想要一种算法来并行生成随机数（并且可以在 GPU 中使用），仅在开始时使用随机种子并将每个元素的索引作为输入

也许我可以使用哈希函数，但我想知道哪种算法可以给出最可能的均匀分布，并且在给定任何种子和任何长度的情况下总是看似随机的

编辑：谢谢你的所有建议。我对我想要的东西有一个更明确的想法，我可以解释

我不需要太多的雪崩属性，但我更关心均匀分布。并且要使其并行，它必须是无状态算法，因此大多数 PRNG 都不适合

但最不担心的是安全性。我想要一个看似随机的人类感知序列，但不要在任何安全性中使用它，仅用于视觉和界面

如果它是一个非常快的算法，将更加感激

4

2 回答 2

3

“纯”随机函数有多种选择。他们包括：

  • 一个哈希函数。
  • 使用其输入为伪随机数生成器 (PRNG) 播种并返回该 PRNG 输出的函数。
  • 一个接受内部状态并输出随机数和新内部状态的函数（这种方法非常适合 Haskell 和其他函数式编程语言）。

另请参阅我关于 PRNG 设计的文章或 L'Ecuyer、Munger 等人撰写的文章“并行计算机的随机数：要求和方法，强调 GPU”（2015 年）。

至于使用哪些哈希函数，有多种选择，包括SHA-1、SHA-256、xxHash、MurmurHash3等；某些散列函数可能比其他函数更合适，具体取决于您是否需要安全性以及其他因素。

大多数散列函数输出一个位序列，但不难看出如何将它们转换为数字 - 例如，请参阅这个问题或我关于以 0 和 1为界的数字的文章。

于 2019-05-20T12:01:56.483 回答
1

好的，这里有一些关于这个问题的想法。

假随机函数通常称为伪随机数生成器 (PRNG)。

您可能对 [0...1) 范围内的双精度数感兴趣，但 PRNG 通常会生成单个 64 位（适用于双精度）或 32 位（适用于浮点数）整数。转换为 double 虽然不是很简单，但操作相当简单。

典型的 PRNG 具有状态、用种子启动和输出。对于最简单的 PRNG（如 LCG）种子，状态和输出是一回事，但一般情况下并非如此。通常状态以位数为特征（例如，LCG 为 64 位，Mersenne twister 为 19937 位）。

从任何 PRNG 算法生成纯函数都相当简单——PRNG 只是一组三个函数，形式为

state_type make_state(seed_type seed) {
    // convert seeding to state, bits chopping
    return new_state;
}

state_type advance_state(state_type old_state) {
    // do bits chopping with old state
    // and advance to the next state
    return new_state;
}

uint64_t generate_output(state_type state) {
    // extract 64bits of randomness from state
    return new_random_number;
}

就是这样，除了这些功能之外，PRNG 中没有其他内容了。

而且，对于手头的问题

  1. 您可以使用具有良好Avalanche 属性的非加密哈希，基本上意味着输入值的单个位变化（输入增加 1）会导致输出发生很大变化。快速，合理，可能不是很随机。杂音还可以，还有妈妈哈希。

  2. 以计数器模式运行的加密密码。比选项 1 慢，但数字质量高。相对较大的状态（比如 512 位左右）。我更喜欢ChaCha20 - 它是众所周知的，合理的快速，看看这里的代码。选项 1 和 2 都假设您只有线性增加的计数器作为输入。

  3. 另一种选择是使用具有对数复杂度跳转功能的 PRNG。这你可以从全局种子开始，如果你有 2 10 个CUDA 核心，你的第一个核心将使用种子，第二个将向前跳跃 2 64 /2 10 =2 54，复杂度为 O(log 2 (N))只有 54 次操作，第三次将领先第二次另外 2 54步和 54 次操作，依此类推。在已知的 PRNG 中，对数跳转适用于 LCG 和PCG。我建议看看PCG。

这意味着存在以下形式的非平凡函数

state_type advance_state(state_type old_state, int64_t distance) {
    // non-trivial advance by distance
    // non-trivial means it is not just a loop, it is better than linear algorithm
    return new_state;
}
于 2019-05-20T21:20:24.000 回答