14

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

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

int RandomNumber1(int seed);

或者：

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

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

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

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

4

6 回答 6

21

似乎您要的是散列函数而不是 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;
}

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

出于您的目的，观察函数并检查输入中的单个位变化是否会传播到许多输出位就足够了。

于 2008-10-03T16:30:53.197 回答
9

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

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

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

于 2008-10-03T16:38:44.973 回答
5

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

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

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

于 2008-10-19T01:07:03.630 回答
2

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

改编自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，它们是更快的生成器。

于 2008-10-03T17:48:36.923 回答
0

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

无符号整数 randarray []={1,2,3,....}

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

于 2008-10-05T00:04:19.253 回答
0

我在我的 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;
}
于 2009-11-18T21:21:05.170 回答