线性同余是什么

Question

线性同余 是什么

Answer 1

自己领悟把
一．计算机中随机数的产生
现在,在计算机,用来产生随机数的算法是“线性同余”法.所谓线性同余,其实就是下面两个式子.假设I就是一个随机数的序列,Ij+1与Ij的关系如下：
Ij+1 =Ij * a+c (mod m)
或是Ij+1 =Ij *a (mod m),
其中,不妨取a=16807,m=2147483647,以为一常数.写个简单的程序就是：
long r;
void scand( long v)//初始化随机种子数
{
r = v;
}
long rand()//产生随机数
{
r = (r*a + c)%m;//a,c,m为常数
return r;
}
再看一下稍复杂一点的：(Random () 的 Borland 的实现)
long long RandSeed = #### ;
unsigned long Random(long max)
{
long long x ;
double i ;
unsigned long final ;
x = 0xffffffff;
x += 1 ;
RandSeed *= ((long long)134775813);
RandSeed += 1 ;
RandSeed = RandSeed % x ;
i = ((double)RandSeed) / (double)0xffffffff ;
final = (long) (max * i) ;
return (unsigned long)final;
}
二．计算机产生的随机数不是真的随机数
[引:]我们建立了真正调用伪随机数生成器的 random().但什么是伪随机数生成器?假定需要生成介于 1 和 10 之间的随机数,每一个数出现的几率都是一样的.理想情况下,应生成 0 到 1 之间的一个值,不考虑以前值,这个范围中的每一个值出现的几率都是一样的,然后再将该值乘以 10.请注意,在 0 和 1 之间有无穷多个值,而计算机不能提供这样的精度.
为了编写代码来实现类似于前面提到的算法,常见情况下,伪随机数生成器生成 0 到 N 之间的一个整数,返回的整数再除以 N.得出的数字总是处于 0 和 1 之间.对生成器随后的调用采用第一次运行产生的整数,并将它传给一个函数,以生成 0 到 N 之间的一个新整数,然后再将新整数除以 N 返回.这意味着,由任何伪随机数生成器返回的数目会受到 0 到 N 之间整数数目的限制.
在大多数的常见随机数发生器中,N 是 232?（大约等于 40 亿）,对于 32 位数字来说,这是最大的值.换句话说,我们经常碰到的这类生成器能够至多生成 40 亿个可能值.而这 40 亿个数根本不算大,只是指尖这么大.
伪随机数生成器将作为“种子”的数当作初始整数传给函数.这粒种子会使这个球（生成伪随机数）一直滚下去.伪随机数生成器的结果仅仅是不可预测.由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定（最终,该种子决定了一切）.如果知道用于计算任何一个值的那个整数,那么就可以算出从这个生成器返回的下一个值.
结果,伪随机数生成器是一个生成完全可预料的数列（称为流）的确定性程序.一个编写得很好的的 PRNG 可以创建一个序列,而这个序列的属性与许多真正随机数的序列的属性是一样的.例如：
PRNG 可以以相同几率在一个范围内生成任何数字.
PRNG 可以生成带任何统计分布的流.
由 PRNG 生成的数字流不具备可辨别的模式.
PRNG 所不能做的是不可预测.如果知道种子和算法,就可以很容易地推算出这个序列.
计算机产生的随机数一般都只是一个周期很长的数列,不是真的随机数.也就是说,随机数一般是伪随机数,每个随机数都是由随机种子开始的一个已定的数列（周期很长）.一般地,为了随机数更真一点,随机种子在系统中通常是参照系统时钟生成的.
看看下面这个例子,从中,读者应能有所体会.
main()
{
int i;
scand(time(NULL)); /＊可向计算机读取其时钟值,并把值自动设为随机数种子＊／
for(i=0;i