3

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

LCG代码：

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

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

4

3 回答 3

7

如果您需要简单但不错的质量，我会使用 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);
}
于 2013-09-29T21:54:13.387 回答
2

Mersenne Twister将是一种选择。另一种选择是带进位减法

于 2013-09-29T22:09:50.600 回答
1

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

这是一个简单的代码示例，其中同时clock()使用了一个支持函数NotRecentlyUsed()（对于min和max的小样本）：

#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;
}
于 2013-09-29T22:39:51.170 回答