標籤：

隨機演算法線性同餘法的理解

05-14

線性同餘如何模擬隨機演算法

程序員對隨機數一般都不陌生，而且眾所周知，計算機中通常實現的是偽隨機數列。何為偽隨機數列？

偽隨機數（或稱偽亂數），是使用一個確定性的演算法計算出來的似乎是隨機的數序，因此偽隨機數實際上並不隨機

既然是通過演算法來模擬隨機過程，那什麼樣的演算法可以達到接近隨機的效果，它又是怎麼實現的呢？

比較簡單的一種便是線性同餘法。

用線性同餘法產生隨機數的特點是非常容易實現，生成速度快，但是弊端也很明顯，32位的數周期最長只能到 2^{32} ，達不到需要高質量隨機數的應用如加密應用的要求

了解這些以後，首先我腦中冒出一個疑問，為什麼線性同餘法可以做到模擬隨機過程呢？所謂隨機就是任何數字都有可能出現，也即所有數據出現是等概率的，符合均勻分布。那線性同餘法是如何做到均勻分布的線性同餘法是如何做到均勻分布的？

第一步我們需要理解線性同餘的周期，上述定義中有清晰的說明，對取模M的線性同餘產生的序列周期最大為M。設想下假設遞推公式為 N_{j+1}=(A*N_{j}+B)(mod M) , 若周期為T，則 N_{k+T}=N_{k} , 由於 N_{k+1}=(A*N_{k}+B)(mod M) , 也就是說唯一的 N_{k} 決定唯一的 N_{k+1} , 那麼T必小於等於M，因為取模M共有M個不同的整數結果，第M+1個數一定和前面某一個數相同，而由於一一對應的遞推關係，後面的序列也會依次與前面的數相同，最後必有周期T<=M。

其次乘積係數與取模最好互質，這個其實也比較好理解，仍以 N_{j+1}=(A*N_{j}+B)(mod M) 為例，若A與M不互質，那假設 A=a*d ， M=m*d ，其中 d>1 。擴展遞推公式為 N_{j+1}=A*N_{j}+B+k*M ，由於B為常數，可以當做一個偏移量，使兩邊都減去B，變換遞推公式為 N_{j+1}-B=(a*(N_{j}-B)+a*B+k*m)*d ，這樣可以很容易推知對所有的 N_{j+1}-B 均含有d這個因子，以 d=2 為例，序列中原有的M個可能數字在循環中只能取到偶數值加偏移量B，也就意味著周期T<=M/2，這便破壞了整個序列的均勻分布。舉幾個簡單的例子幫助理解，假設現在A=3，M=5，令 N_{0}=2 ，序列為{2，1，3，4，2，1....}周期為5，若取A=6，M=10，令 N_{0}=2 ，序列為{2，2，2....}周期為1

對應的其他條件，同樣是為了確保整個序列周期為M。詳細推導過於複雜，有想要了解的，建議參考這篇論文：

混合線性同餘發生器的周期分析_愛學術?

www.ixueshu.com圖標

回到最初的疑問，線性同餘法是如何做到均勻分布的。從上面我們可以得知，通過特定條件的參數選擇，我們可以構造一個序列周期為M，且M的周期中各數字只出現一次，因此在整個序列中，各數字出現的頻率是相同的，也就符合了均勻分布。

線性同餘方程如何求解

明白隨機分布與線性同餘的關係後，我們擴展一下知識，來了解下線性同餘方程的解法。這不僅僅是一個純數學問題，它實際上有很多應用的例子，比如：

在一個圓環上有兩隻青蛙A和B，從0點自東向西為正方向，兩隻青蛙的位置分別為x,y，A每次跳m,B每次跳n，環總長為L.兩隻青蛙同時出發，兩隻青蛙落在同一點視為相遇，問最少經過幾次跳躍兩隻青蛙相遇。

根據條件，我們列出解題方程： (x+m*k)≡(y+n*k)(mod L) 其中≡代表兩邊取模

展開為 x+m*k=y+n*k+L*k^{}

平移後轉換為 x-y=(n-m)*k+L*k^{} 即 (x-y)≡((n-m)*k)(mod L)

令 n-m=a , x-y=b 可得 a*k≡b(mod L) ,這便形如標準的一元線性同餘方程

定義:a,b是整數，形如 a*x≡b(mod M) ，且x是未知整數的同餘式稱為一元線性同餘方程，其中≡ 及(mod M)表示兩邊對M取模

求解一元線性同餘方程，首先需要將其一步步做如下變換：

  1. 標準的一元線性同餘方程 a*x≡b(mod M) 等價於 a*x+M*y=b
  2. 假設d為a與M的最大公約數，記為 gcd(a,M)=d ,易知若x，y有解d必為b的因子，因此等式變換為 a_{0}*x+M_{0}*y=b_{0} 其中 a=a_{0}*d , M=M_{0}*d , b=b_{0}*d ,且 a_{0},M_{0} 互質，即 gcd(a_{0},M_{0})=1
  3. 令 x=x_{0}*b_{0},y=y_{0}*b_{0} 方程變換為 a_{0}*x_{0}+M_{0}*y_{0}=1 即 a_{0}*x_{0}≡1(mod M_{0})

最後運用模逆計算出 x_{0}

定理：如果a和M為互素的整數，M>1，則存在a的模M的逆.而且這個逆模M是唯一.

這個定理的證明也比較簡單，推導過程如下：

若a與m互質，必存在 s*a+t*M=1 （若a,M有大於1的公因子d，則 s*a+t*M=d*k 而不可能等於1），兩邊取M的模，可得 s*a≡1(mod M) ,即s為a的模M的逆

若記 ar{a} 為a的模M的逆，即 x_{0}≡ar{a}(mod M_{0}) ,也就是 x_{0}≡ar{a}+k*M_{0}

舉個簡單的例子：

求解 5*x≡7(mod 9)

  1. 由於 gcd(5,9)=1 ,可知存在5模9的逆，易知 2*5+(-1)*9=1
  2. 得出2為5模9的逆，方程兩邊乘以2有 2*5*x≡2*7(mod 9)
  3. 化簡為 x≡10*x(mod9)≡14(mod 9)≡5(mod9)
  4. 得出 x=5+9k

綜合以上，我們將普通線性同餘方程 a*x≡b(mod L) 轉換為標準方程 a_{0}*x_{0}≡1(mod M_{0}) 進行求解，求解標準方程完畢後需要將解空間映射回去，若標準方程的解為 x_{0}in{x=p+q*M_{0}}

則由於 x=x_{0}*b_{0},y=y_{0}*b_{0} 且 b=b_{0}*d ，得出 xin{x=b/d*p+q^{}*M_{0}} 為方程 a*x+M*y=b 的解

至此，我們縷清楚了一元線性同餘方程的求解過程，也對線性同餘法有了更深的了解，基於以上知識，再回歸去看程序求解線性同餘的擴展歐幾里得演算法，就比較好理解了。 但是線性同餘法只是隨機演算法中最簡單的一種，可想而知其他可能看似簡單的演算法實際都有深挖的價值。

PS：以前經常聽人提起數學無用論，什麼這個定理那個法則在實際中都沒有用處，計算機行業中也不乏有這樣的聲音。但是現在逐漸發現如果你的工作中用不到這些看似深奧的理論，你就可以想想是不是你的工作本身或對工作的了解還不夠有深度。因此僅以此文自勉，希望之後自己工作可以逐步做深做精。

參考鏈接：

淺談線性同餘及中國剩餘定理 - Ivy - End?

www.ivy-end.com

線性同餘和擴展歐幾里得的運用小結 - CSDN博客?

blog.csdn.net


推薦閱讀：

※優秀的數學家不用Lebesuge積分？
※中國奧數精英兵敗里約，什麼打敗了我們？
※什麼是阿羅不可能定理？
※【拓撲】序拓撲、積拓撲、子空間拓撲
※題都城南庄（崔護）

TAG:數學 | 隨機演算法 |