需要一个用于c ++的快速随机生成器

Question

我正在尝试在我的TSP生成器上做一些opt-3交换以获得欧几里德距离,并且由于我在很多情况下有超过500个节点,我需要随机选择我想尝试交换的3个节点中的至少1个.

所以基本上我需要一个快速的随机数函数.(正常的rand()太慢了)它不一定非常好,只是足够好.

编辑:我忘了提,我坐在一个环境,除了标准语言库(如STL,iostream等),我无法添加任何库.所以没有提升= /

Answer 1

另一个线程提到了Marsaglia的xorshf生成器,但没有人发布代码.

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;
}

我到处都用过这个.它失败的唯一地方是我试图生成随机二进制矩阵.过去大约95x95矩阵,它开始产生太少或太多的奇异矩阵(我忘了哪个).已经证明,该发生器相当于线性移位反馈寄存器.但除非你正在进行密码学或严肃的蒙特卡罗工作,否则这台发电机会晃动.

Answer 2

来自intel网站的两个不错的选择:

1)fastrand - 它比std rand()快2.01 X. 该例程返回一个整数,类似于C lib的输出值范围.

inline int fastrand() { 
  g_seed = (214013*g_seed+2531011); 
  return (g_seed>>16)&0x7FFF; 
} 

2)SSE版本(参见下面的链接)与std rand()的速度大约是5.5 X,但是它一次生成4个随机值,需要一个带有sse的处理器(几乎全部都是),并且更复杂.

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

Answer 3

从随机数发生器专家George Marsaglia 看这些发电机.它们被实现为C宏,并且它们快速闪电,每个数字生成一些操作.

Answer 4

在梅森倍捻机具有一定的快速实现.

Answer 5

从Ivy Bridge架构开始,英特尔增加了RdRand CPU指令,AMD在2015年6月晚些时候添加了它.因此,如果您的目标是处理器足够新并且不介意使用(内联)汇编,那么生成随机数的最快方法应该是在调用RdRandCPU指令描述得到一个16位或32位或64位的随机数这里.滚动到大约页面中间以获取代码示例.在该链接上还有一个代码示例,用于检查当前CPU是否支持RdRand指令,另请参阅Wikipedia以获取有关如何使用CPUID指令执行此操作的说明.

相关问题:利用沙桥的硬件真随机数发生器？(虽然根据维基百科的说法,RdRand指令首先出现在Ivy Bridge,但不是Sandy Bridge架构,因为那个问题说)

基于_rdrand64_step()的示例C++代码:

#include <immintrin.h>

uint64_t randVal;
if(!_rdrand64_step(&randVal)) {
  // Report an error here: random number generation has failed!
}
// If no error occured, randVal contains a random 64-bit number