C++ 快速随机数生成器

C++| 2015-11-06

问题：

在计算旅行商问题中的欧几里得距离时，我试图使用 3-opt 算法来交换某些节点；因为大多情况下我有大约超过500个节点，我需要随机地选择至少1/3的节点进行交换。

所以我需要一个快速产生随机数的函数（标准函数rand()太慢了）。不需要多么巧妙，差不多就行了。

注：忘了说，我无法使用除了标准库（比如 STL，iostream 等）以外的库，所以 boost 库也不行。

AndyV 的最佳答案：

其他人的答案提到了 Marsaglia 的 Xorshift 算法（https://en.wikipedia.org/wiki/Xorshift），但是没人贴代码。

static unsigned long x=123456789, y=362436069, z=521288629;

unsigned long xorshf96(void) {          //period 2^96-1
unsigned long t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;

   t = x;
   x = y;
   y = z;
   z = t ^ x ^ y;

  return z;
}

这段代码几乎在任何地方都适用；然而当我试图产生随机的二进制矩阵时，它却失败了。大概是 95×95 的矩阵，它生成了太多或太少的奇异矩阵（我忘了具体是多还是少了）。这个随机数生成器相当于一个线性反馈移位寄存器。不过如果你要做加密或者蒙特卡洛的相关工作，这个生成器就不能用了。

补充：Xorshift 算法介绍

Xorshift 随机数生成器是 George Marsaglia 发明的一类伪随机数生成器。它们通过和自己逻辑移位后的数进行异或操作来生成序列中的下一个数。这在现代计算机体系结构非常快。它们是线性反馈移位寄存器的一个子类，其简单的实现使它们速度更快且使用更少的空间。然而，必须仔细选择合适参数以达到长周期。

Xorshift生成器是非密码安全的随机数生成器中最快的一种，只需要非常短的代码和状态。虽然它们没有进一步改进以通过统计检验，这个缺点非常著名且容易修改（Marsaglia 在原来的论文中指出），用复合一个非线性函数的方式，可以得到比如像 xorshift+ 或 xorshift* 生成器。一个简单的C语言实现的 xorshift+ 生成器通过了所有的 BigCrush 的测试（比 Mersenne Twister 算法和 WELL 算法的失败次数减少了一个数量级），而且在 x86 上产生一个随机数通常只需要不到十个时钟周期，多亏了指令流水线。

因为一般的 xorshift 生成器（没有非线性这一步）在一些统计测试中失败了，所以经常被指责是不可靠的。

示例实现

一个 xorshift 生成器的 C/C++ 版本实现：

#include <stdint.h>

/* These state variables must be initialized so that they are not all zero. */
uint32_t x, y, z, w;

uint32_t xorshift128(void) {
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

这个算法有一个最大的周期2¹²⁸ − 1 ，且通过了 diehard 测试。不过，它在 TestU01 框架的 BigCrush 测试套件中的 MatrixRank 和 LinearComp 测试中失败了。

本文文字及图片出自伯乐在线