用于程序内容的快速伪随机数生成器

StackOverflow https://stackoverflow.com/questions/167735

  •  03-07-2019
  •  | 
  •  

题

我正在寻找一个伪随机数生成器，它可以专门在生成每个数字之前给定种子时快速工作。到目前为止，我见过的大多数生成器都假设您设置一次种子，然后生成一长串数字。到目前为止看起来与我见过的唯一相似的是Perlin Noise，但它也产生了“平滑”的特征。数据 - 对于类似的输入，它往往会产生类似的结果。

生成器的声明应该类似于：

int RandomNumber1(int seed);

或者：

int RandomNumber3(int seedX, int seedY, int seedZ);

我认为拥有良好的RandomNumber1应该足够了，因为可以通过对其输入进行散列并将结果传递给RandomNumber1来实现RandomNumber3，但我编写了第二个原型，以防某些实现可以使用独立输入。

此生成器的预期用途是将其用于程序内容生成器，例如通过将树放置在网格中来生成林，并确定每个位置的随机树种和随机空间偏移。

生成器需要非常高效（低于500个CPU周期），因为在渲染过程中会实时大量创建过程内容。

有帮助吗？

解决方案

好像你要求哈希函数而不是PRNG。谷歌搜索“快速哈希函数”产生了几个看起来很有希望的结果。

例如：

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

编辑：是的，有些哈希函数看起来比其他函数更合适。

出于您的目的，应该足以观察功能，并检查输入中的单位变化是否会传播到大量输出位。

其他提示

是的，您正在寻找快速整数哈希算法而不是PRNG。

这个页面有几个算法，我相信你现在你知道正确的搜索条件会发现更多。

修改：原始页面已被删除，实时版本可以在GitHub上找到。

这是George Marsaglia开发的一个小型随机数发生器。他是该领域的专家，因此您可以确信发电机具有良好的统计特性。

v = 36969*(v & 65535) + (v >> 16);
u = 18000*(u & 65535) + (u >> 16);
return (v << 16) + u;

这里你和v是无符号整数。将它们初始化为任何非零值。每次生成随机数时，请将u和v存储在某处。你可以将它包装在一个函数中，以匹配上面的签名（除了int是无符号的。）

参见 std :: tr1 :: ranlux3 ，或其他随机数生成器，它们是标准C ++库中TR1添加的一部分。我最初建议mt19937，但后来看到你的注意事项，它需要非常快。 TR1应该可以在 Microsoft VC ++ 和GCC上找到，也可以可以在支持更多编译器的boost库中找到。

示例改编自提升文档：

#include <random>
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
using namespace std::tr1;
int main(){
    random_device trueRand;
    ranlux3 rng(trueRand);  // produces randomness out of thin air
                            // see pseudo-random number generators
    uniform_int<> six(1,6); // distribution that maps to 1..6
                            // see random number distributions
    variate_generator<ranlux3&, uniform_int<> >
           die(rng, six);   // glues randomness with mapping

    // simulate rolling a die
    generate_n( ostream_iterator<int>(cout, " "), 10, ref(die));
}

示例输出：

2 4 4 2 4 5 4 3 6 2

任何TR1随机数生成器都可以播种任何其他随机数生成器。如果您需要更高质量的结果，请考虑将mt19937的输出（速度较慢但质量较高）输入minstd_rand或randlux3，它们是更快的发生器。

如果内存不是真正的问题而且速度至关重要，那么你可以预先建立一大堆随机数，并在运行时迭代它。例如，有一个单独的程序生成100,000个随机数，并将其保存为自己的文件，如

unsigned int randarray [] = {1,2,3，....}

然后将该文件包含到您的编译中，并且在运行时，您的随机数函数只需要从该数组中提取数字，并在它到达结束时循环回到开始。

我在Java随机数库中使用以下代码 - 这对我来说非常有用。我也用它来生成程序内容。

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top