線性同餘法(LCG，Linear Congruential Method)之模擬結果－簡單也是另一種快樂

在看過介紹之後，想必一定要來跑跑模擬囉，天花亂墜了一番，到頭來還是得要實際的來做做看，看看是不是到底有沒有從中真正的學習到~

在線性同餘法(LCG，Linear Congruential Method)中介紹了四種LCG的作法，大同小異，在此礙於時間上的考量，我只做了最後一項稱做是目前最常被使用到的PMMLCG(Prime Modulus Multiplicative LCG)。(2001年，近乎10年前的作法…)

而測試的方式則採用頻率測試(Frequency test)，透過平均數的概念，觀察在一定的數量內是否每一個隨機數都能有較均勻的次數。

下圖是老師所做的結果，示意圖:

橫軸是設定的隨機數範圍，縱軸是迴圈執行 10000 次後 (加上初始的一次，合計 10001次)，隨機數範圍內每一個整數的發生次數。可以看的出來相當平均 (理論上的發生次數是 10001/501 = 19.962)。

圖檔源至: http://tw.myblog.yahoo.com/ericsu-blog/article?mid=757&prev=760&next=755

而我透過前兩篇的介紹，再加上老師所提供之程式碼加以調整後。

演算法的MATLAB程式:

f_low = 2250;

f_high = 2750;

Im=2^31+4633;

Ia=46340;

fran = 2500;

count(1:501) = 0;

for i=1:10000

fran = mod((Ia*fran),Im);

fsw = f_low + floor(((f_high-f_low+1)*fran)/Im);

count(fsw-(f_low-1)) = count(fsw-(f_low-1))+1;

end

y_min = min(count)-10;

y_max = max(count)+10;

h1=figure(1);

set(h1,'color','white');

plot(f_low:f_high, count);

axis([f_low f_high y_min y_max]);

xlabel('Switching frequency in Hz');

ylabel('number of times');

title('Generate random numbers in a specified range, 10000 times','FontSize',12);

------------------------------------------------------------------

先以10000次的亂數變化觀察其結果與老師所提供之差異，下圖為我所做的結果:

執行結果: 橫軸是設定的隨機數範圍，縱軸是迴圈執行 10000 次後 (加上初始的一次，合計 10001次)，隨機數範圍內每一個整數的發生次數。可以看的出來相當平均 (理論上的發生次數是 10001/501 = 19.962)。

接著在以50000次亂數數據與老師所提供之方式相較下如下圖所示:

執行結果: 橫軸是設定的隨機數範圍，縱軸是迴圈執行 50000 次後 (加上初始的一次，合計 50001次)，隨機數範圍內每一個整數的發生次數。可以看的出來相當平均 (理論上的發生次數是 50001/501 = 99.802)。

我所實作之結果圖(下圖):

老師所提供之程式範例結果圖(下圖):

從結果上可以發現均勻性相當良好，但是若從程式中觀察，細心的玩家可以發現到模數m使用到了2^31之多，若使用32位元的微處理器似乎相當的合適，但礙於我所使用之微處理器為Microchip disPIC 30F4011 ，此IC是屬於16位元，在程式上撰寫需要使用到long long的型態才有辦法進行運算處理，此運算會帶來較大的運算負擔，505us(如下圖所示):