相关疑难解决方法(0)

我需要一个能在给定范围内生成随机整数的函数(包括边界值).我没有不合理的质量/随机性要求,我有四个要求:

• 我需要快速.我的项目需要产生数百万(有时甚至数千万)的随机数,而我当前的发电机功能已被证明是一个瓶颈.
• 我需要它合理均匀(使用rand()非常好).
• min-max范围可以是<0,1>到<-32727,32727>.
• 它必须是可播种的.

我目前有以下C++代码:

output = min + (rand() * (int)(max - min) / RAND_MAX)

问题是,它并不是真正统一的 - 只有当rand()= RAND_MAX时才返回max(对于Visual C++,它是1/32727).这是小范围的主要问题,如<-1,1>,其中最后一个值几乎从不返回.

所以我抓住笔和纸,并提出了以下公式(它建立在(int)(n + 0.5)整数舍入技巧):

但它仍然没有给我统一的分配.对于值-1,0,0,重复运行10000个样本给出37:50:13的比率.

你能建议更好的配方吗？(甚至整个伪随机数发生器功能)

可能重复:
从范围生成随机整数

我正在尝试创建一个程序,其中计算机猜测用户在他/她心中的数字.唯一需要的用户输入是猜测是否过高,过低或正确.我在根据先前的猜测存储最小值和最大值的两个变量之间生成随机数时遇到问题.这是我的代码:

    #include <iostream>
    #include <cstdlib>
    #include <ctime>

    using namespace std;

    int main()
    {
        srand(static_cast <unsigned int> (time(0)));

        int compGuess = rand() % 100 +1; //Generates number between 1 - 100
        int highestNumber = 100;
        int lowestNumber = 1;
        char ready;
        char highLowSuccess;
        bool success;
        int tries = 0;


        cout << "Please pick a number between 1 - 100. I will guess your number. Don't tell me what it is!\n\n";


        do
        {
            cout << "Are you ready? (y/n)\n\n";
            cin …

在[0,n)中选择随机数的一种常用方法是采用rand()模n的结果:rand() % n.但是,即使可用rand()实现返回的结果完全一致,当n = n均匀分配时,结果[0,n]数的均匀性是否应该存在问题？例如假设为2,n为2.然后,在3个可能的输出中:0,1和2,当我们使用模n时,我们分别得到0,1和0 .因此输出将根本不是均匀的.RAND_MAX + 1RAND_MAXrand()

这在实践中是一个真正的问题吗？选择[0,n]中的随机数是一种更好的方法,从rand()输出中均匀推导出来,最好没有任何浮点运算？

我编写了一个C函数,我认为从范围[rangeLow,rangeHigh](包括范围)的均匀分布中选择整数.这不是功课 - 我只是在一些嵌入式系统中使用它来修补我正在做的事情.

在我的测试用例中,此代码似乎产生了适当的分布.但是,我并不完全相信实施是正确的.如果我在这里做错了什么,有人可以做一次健全检查并让我知道吗？

//uniform_distribution returns an INTEGER in [rangeLow, rangeHigh], inclusive.
int uniform_distribution(int rangeLow, int rangeHigh)
{
    int myRand = (int)rand(); 
    int range = rangeHigh - rangeLow + 1; //+1 makes it [rangeLow, rangeHigh], inclusive.
    int myRand_scaled = (myRand % range) + rangeLow;
    return myRand_scaled;
}
//note: make sure rand() was already initialized using srand()

PS我搜索了这样的其他问题.但是,很难过滤掉讨论随机整数而不是随机浮点数的小问题子集.

我听到一些人说，rand()即使在使用srand()获得种子后，使用也很糟糕。为什么呢？我想知道事情是如何发生的......还有另一个问题很抱歉......但是有什么替代方法呢？

我有一个(均匀的)随机位流,我希望在[0,n]范围内统一生成随机整数,而不会浪费比特.(我正在考虑超出楼层(log_2(n))+ 1的比特浪费,假设它总是可以使用不超过它.)例如,如果n = 5,那么算法我是寻找应该使用不超过三位.如何才能做到这一点？

因为鸽子洞原理，不能随便用

output = min + (rand() % (int)(max - min + 1))

生成无偏的、统一的结果。This answer to a similar question提供了一种解决方案，但就消耗的随机位而言，这是非常浪费的。

例如，如果源的随机范围很小，那么必须从源生成第二个值的机会可能会非常高。或者，使用更大的源范围本质上也是浪费。

虽然我确信可以推导出最佳的源范围大小，但这并没有解决可能存在更好算法的问题，而不是优化这个算法。

[编辑] 我的想法已在答案中显示，以产生有偏见的结果。

我想到的一种方法是

1. 消耗覆盖所需范围所需的最少位数。
2. 如果该值超出所需范围，则仅丢弃一位并再消耗一位。
3. 根据需要重复。