有什么比LCG更好的(伪)随机数生成器用于彩票调度程序？

Question

我想设计一个彩票调度程序，我需要一个非常好的(伪)随机数生成器，类似于LCG，但我想知道是否有其他更好的选择？我专门寻找用C编写的随机生成器。

LCG代码：

unsigned long lcg_rand(unsigned long a)
{
  return (a * 279470273UL) % 4294967291UL;
}

另外，我想知道srand()是否可以用于此目的，或者不是非常准确？

Answer 1

如果你需要简单但质量不错，我会使用64位LCG的高32位(或更少)，可能会对输出应用回调函数。在执行此操作时，我复制了Mersenne Twister中使用的优化函数。我不建议实际使用Mersenne Twister，因为它比其他没有明显更好质量的PRNG具有更多的复杂性和内部状态。

下面是一些示例代码：

static uint32_t temper(uint32_t x)
{
    x ^= x>>11;
    x ^= x<<7 & 0x9D2C5680;
    x ^= x<<15 & 0xEFC60000;
    x ^= x>>18;
    return x;
}
uint32_t lcg64_temper(uint64_t *seed)
{
    *seed = 6364136223846793005ULL * *seed + 1;
    return temper(*seed >> 32);
}

Answer 2

Mersenne Twister将是一种选择。另一个选项是Subtract with carry

Answer 3

大多数C rand()函数的实现都使用的变体。像任何计算机化的随机生成器一样，rand()也不是真正的随机，它只是伪随机的。使用srand()可以提高随机性，但不能使其变得完美。这取决于srand()中使用的种子的多样性和随机性。例如，如果您在srand()中使用相同的种子调用rand() n次，结果将是相同的。但是，如果您每次都调用srand(clock()) (并且调用之间的时间间隔大于clock()中的节拍周期)，那么您将拥有一个改进的随机生成器。

下面是一个简单的代码示例，其中使用了clock()和支持函数NotRecentlyUsed() (对于最小和最大的小样本)：

#include <ansi_c.h>

#define _UNIQUE_

int randomGenerator(int min, int max);
int NotUsedRecently (int number);

int main(void)
{
    int i=0;
    for(i=0;i<1000;i++)
    {
        printf("%d,\t", randomGenerator(0, 20));
            if(i%20 == 0) printf("\n");
    }
    getchar();
    return 0;   
}

//////////////////////////////////////////////////////
//generates pseudo random numbers between min and max
//If it is desired to use this without a guarantee of uniqueness
//for a specified span of values, un-define _UNIQUE_
//
int randomGenerator(int min, int max)
{
    int random, trying;

    trying = 1;         
    while(trying)
    {
        srand(clock());
        random = (rand()/32767.0)*(max+1);
        ((random >= min)
#ifdef _UNIQUE_
            && NotUsedRecently(random) 
#endif
            ) ? (trying = 0) : (trying = 1);
    }

    return random;
}

//This function is used to guarantee that a span of n generated values
//will not be the same. To adjust the span, change the index in 
//static int recent[n];  Note: it is required that n < (max-min)
//otherwise an infinite loop will occur
int NotUsedRecently (int number)
{
    static int recent[20];//Use No greater value for index than max - min
    int i,j;
    int notUsed = 1;

    for(i=0;i<(sizeof(recent)/sizeof(recent[0]));i++)  (number != recent[i]) ? (notUsed==notUsed) : (notUsed=0, i=(sizeof(recent)/sizeof(recent[0])));
    if(notUsed) 
    {
        for(j=(sizeof(recent)/sizeof(recent[0]));j>1;j--)
        {
            recent[j-1] = recent[j-2];
        }
        recent[j-1] = number;
    }
    return notUsed;
}