增量選取在平行化線性亂數產生器的應用

Abstract

線性同餘法（linear congruential generator，LCG）與k階乘餘法（multiple recursive generator，MRG）至今仍為亂數產生器常使用的兩大線性方法；而近日，由於電腦處理器成本下降，平行化計算因而被廣泛研究與使用，以改善因分析與模擬資料量與日俱增，電腦運算效率降低之問題。除此之外，平行化處理亦可能增強許多模擬數據時所需具備的統計性質，如隨機性等。傳統平行化線性亂數產生器之方式，譬如使用不同初始值，多僅改善運算速度，對於統計性質的改變，則助益不大；但藉由改變線性亂數產生器的增量（increment），則可坐收同時改善速度與性質之效，且計算簡單，易於推廣，尤其輔以平行設計之跳蛙法（leapfrogging method），綜效較順序切割法（sequence splitting method）更佳。

Two major linear random number generators (RNGs), the linear congruential generator (LCG) and the multiple recursive generator (MRG), have been widely studied and used for many decades. Nowadays, as the price decreasing of computer processors, parallelization of the generators is being concerned for, at least, the computational efficiency purpose. Besides, the proper design of parallel generator may also improve some statistical properties such as randomness. The Parallel linear random number generator with different increment shifts is efficient and feasible because the change of the increments only shifts the hyperplanes of the linear RNG. Additionally, parallelizing through the leapfrogging method can further improve than through the sequence splitting method.