一些随机算法

随机算法在计算机中还是由一个公式来进行计算的，不过尽量让随机周期变得长一些，这个过程也称为伪随机.TAOCP第2卷记录的大致算法如下:

1. 冯诺依曼最初提出一个算法公式计算:Xn+1 = mid(Xn²):Xn²的中间位数(与X,,n,,位数保持一致)，如 Xn = 5772156649, Xn² = 33317792380594909201,Xⁿ⁺¹ = mid(Xn²) = 7923805949. 缺点:

   1. 随机周期长度太短;
   2. 如果Xn中有0，则后面序列中会一直包含0

2. Algorithm K("Super-random" number generator),非常复杂，大致思想是通过Xn的某一位来决定下一步具体的执行操作(如Xn通过如何转换到Xn+1) 缺点:非常复杂，不利于计算机快速计算

3. 现在最常用的随机算法,Xn+1 = (aXn + c) mod m,其中 n >= 0, 0<= a w+1或m=2^w-1 (w为机器字长)

   • 当c=0时，满足:

     • X0与m互质
     • a mod m为质数 在计算时,只需要计算一次乘法即可。 aXn = q2^w + r = q(m-1) + r = qm + r - q

   • 当c!=0时，b = a-1,满足:

     • c与m互质
     • b是p的质数，p能被m整除
     • 如果m是4的质数，b也为4的倍数