C提供的标准随机函数是rand()，返回0~RAND_MAX，共RAND_MAX+1个随机数，如果我需要更大的随机数范围应如何做？

试设计：
long random(long n);返回0~n-1间的等概率随机数

分情况讨论

如果n<RAND_MAX+1，大可以用rand()%n的方法做，但这样做也并不能满足等概率性，设r=RAND_MAX%n，得到0~r的概率要稍大一些，尤其在n较接近RAND_MAX时，当n较小时影响可以忽略。

if(n<=RAND_MAX)
    {
        r=RAND_MAX-(RAND_MAX+1)%n;//尾数
        t=rand();
        while(t>r)t=rand();
        return t%n;
    }

如果n>=RAND_MAX+1，我的想法是分段抽样，分成[n/(RNAD_MAX+1)]段，先等概率得到段再得到每段内的某个元素，这样分段也类似地有一个尾数问题，不是每次都刚好分到整数段，一定或多或少有一个余数段，这部分的值如何选取？

选到余数段的数据拿出来选取，先进行一次选到余数段概率的事件发生，然后进行单独选取：

else
    {
        r=n%(RAND_MAX+1);//余数
        if(happened((double)r/n))//选到余数段的概率
            return n-r+random(r);
        else
            return rand()+random(n/RAND_MAX)*RAND_MAX;
    }
如果选不到余数段再进行分段选取：
return rand()+random(n/(RAND_MAX+1))*(RAND_MAX+1);

完整的代码：

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
static const double MinProb=1.0/(RAND_MAX+1);
bool happened(double probability)//probability 0~1
{
    if(probability<=0)return false;
    if(probability<MinProb)
        return rand()==0&&happened(probability*(RAND_MAX+1));
    if(rand()<=probability*(RAND_MAX+1))
        return true;
    return false;
}
long random(long n)//产生0~n-1之间的等概率随机数
{
    long r,t;
    if(n<=RAND_MAX)
    {
        r=RAND_MAX-(RAND_MAX+1)%n;//尾数
        t=rand();
        while(t>r)t=rand();
        return t%n;
    }
    else
    {
        r=n%(RAND_MAX+1);//余数
        if(happened((double)r/n))//取到余数的概率
            return n-r+random(r);
        else
            return rand()+random(n/(RAND_MAX+1))*(RAND_MAX+1);
    }
}
void main()
{
    int v[10000];
    long i;
    for(i=0;i<10000;++i)
        v[i]=0;
    for(i=0;i<500000;++i)
        v[random(10000)]++;
    for(i=0;i<10000;++i)
        cout<<v[i]<<",";
    cout<<endl;
}

评论