快速、快速随机整数发生器

Question

有许多算法，比如XorShift，它们都是快速生成随机数的算法，可以满足一般的使用要求。不幸的是，我需要生成一个从0到10的随机整数，并且在我的代码中使用rand()函数会导致大约23%的减速。

问题：：从0到10生成整数的最快方法是什么？

编辑:基于布兰登评论的信息：

23%的减速假设你已经把它比作某种东西。你把它和什么比较？

>我正在做兰德()% 10 > 5。

另外：

• 在循环之外使用srand(time(0));什么都不做。
• rand() % 10的分离率为19%，因此比较对性能影响不大。

Answer 1

Xorshift是一个很好的算法。使用它生成一个充满随机位的缓冲区。仅仅因为它一次填充了32位缓冲区，就没有理由一次从缓冲区32位中读取它们。因为你想要速度，所以你要避免除法(和国防部)。唯一的方法是通过拒绝抽样(也是获得完全无偏数字的唯一方法)。

因为您只需要11个值(0到10)，所以每个样本只需要4位。您将拒绝每16次中的5次，但由于每32位将有8个样本，因此在Xorshift的每一次迭代中，平均输出值为5.5。

因此，从Xorshift中填充一个大缓冲区，然后用如下所示将该缓冲区转换为(0到10)值：

for (int b = 0; b < sizeof inbuf; b += 1) {
    uint8_t v = ((uint8_t *)inbuf)[b];

    if ((v & 0x0F) < 10) { *outbuf++ = v & 0x0F; }
    if (((v >> 4) & 0x0F) < 10) { *outbuf++ = ((v >> 4) & 0x0F; }
}

将outbuf设为inbuf的两倍大小的字节数组，它将满约11/16。根据需要重新填充两个缓冲器。

Answer 2

你试过标准的mersenne实现吗？以下示例来自Microsoft的联机帮助：

#include <random>
#include <iostream>

using namespace std;

int main()
{
    random_device rd;   // non-deterministic generator
    mt19937 gen(rd());  // to seed mersenne twister.
    uniform_int_distribution<> dist(0,10); // distribute results between 1 and 10 inclusive.

    for (int i = 0; i < 5; ++i) {
        cout << dist(gen) << " "; // pass the generator to the distribution.
    }
    cout << endl;
}

上一次我使用了来自松本真本的实现，它比rand()快得多。我没有对其进行基准测试，但我猜想标准实现也更快。

SSE2还特别支持随机数的生成，这可能会更快：https://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor