一些随机算法

2183阅读 0评论2012-12-09 datao0907
分类:C/C++

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

  1. 冯诺依曼最初提出一个算法公式计算:Xn+1 = mid(Xn2):Xn2的中间位数(与X,,n,,位数保持一致),如 Xn = 5772156649, Xn2 = 33317792380594909201,Xn+1 = mid(Xn2) = 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=2w-1 (w为机器字长)

    • 当c=0时,满足:

      • X0与m互质
      • a mod m为质数 在计算时,只需要计算一次乘法即可。 aXn = q2w + r = q(m-1) + r = qm + r - q
    • 当c!=0时,b = a-1,满足:

      • c与m互质
      • b是p的质数,p能被m整除
      • 如果m是4的质数,b也为4的倍数
上一篇:最大子数组连续和问题(数组为环)
下一篇:python 多继承分析