學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 GFSR亂數產生器的研究 作者 范雅燕 貢獻者 李子壩
范雅燕日期 1990
1989上傳時間 3-五月-2016 14:13:56 (UTC+8) 摘要 論文摘要 無論是在社會科學或是自然科學的研究中，經常會面對複雜難解的問題，需要利用電腦模擬一些自然狀態，此時亂數就會被應用來增加其可靠性，被少人為主觀的控制因素。 1973年Lewis & Payne 提出G F S R方法，這個方法所產生的擬隨機序列yt=O. atat+d........., t= 1 , 2 , .........。可以得到較線性除模法更長週期的序列，且可以改善在除模法中變數個數愈多，效果愈差的缺點，我們對此作理論上探討。 此外，我們比較幾個G F S R 的實際製作演算法討論G F S R 的優缺點。最後本文將探討有關此產生器的應用，如在部份判別分析及在K - S 統計量的修正上。 參考文獻 [l] A.C. Arvillias and D.G. Maritsas (1978) "Partitioning the Period of a Class of m-Sequence and Application to Pseudorandom Number Generation.",Journal of the ACM, Vol.25 , pp 675-686 [2]Alexander Haas (1987) "The Multiple Prime Random Number Generator." ACM Transactions on Mathematical Software. Vol.13 .PP 368-381 [3]R.J.Beckman and M.E.Johnson (1981) "A Ranking Procedure for Partial Discriminant Analysis.",Journal of the American Statistical Associatjon.Vol.76, pp 671-675 [4]J.D.Broffitt.R.H.Randles and R.V.Hogg (1976) "Distribution-Free Partial Discriminant Analysis.",Journal of the American Statistical Association.Vol.7l , pp 934-939 [5]Bruce Jay Collings (1987) "Compound Random Number Generators. ",Journal of the American Association.Vol.82 , pp 525-527 [6]Bruce Jay Collings and G.Barry Hembree (1986) "Initializing Generalized Feedback Shift Register Pseudorandom Number Generators.", Journal of the ACH,Vol.33 , pp 706-711 [7]R.R.Coveyou and R.D.Macpherson (1967) "Fourier Analysis of Uniform Random Number Generators.",Journal of the ACH,Vol.14 , pp 100-119 [8]Gentle and Kennedy (1980) Statistical Computing, Published by Marcel Dekker ,New York, Ch 6 [9]Herbert S. Bright and Richard L. Enison (1979) "Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography.",Computing Surveys ,Vol.ll ,pp 357-370 [10]D . E.Knuth (1981) The Art of Computer Programming, V2 : Semi-numericalAlgorithms ,2nd Edition, Addison-Wesley, Reading ,Mass. [11]T.G.Lewis and W.H. Payne (1973) "Generalized Feedback Shift Register Pseudorandom Number Algorithm.",Journal of the ACM.Vol.20 .PP 456-468 [12]W.H.Payne. J.R.Rdbung and T.P.Bogyo(1969) "Coding the Lehmer Pseudo-random Number Generator.", Communications of ACM.Vol.12 ? pp 85-86 [13]W.H. Payne and K.L. McMillen (978) "Orderly Enumeration of Nonsingular Binary Matrices Applied to Text Encryption.". Communications of ACM.Vol.21, pp 259-263 [14]Marsaglia George (1984) "A Current View of Randow Number Generation.", Computer Science and Statistics: Sixteenth Symposiumon the Interface, Proceedings, pp 3-10 [15]Marsaglia George and Liang-Huei-Tsay (1985) "Matrices and the Structure of Random Number Sequences.",Linear Algebra and its Appliations ,Vol.67,pp 147-156 [16]Masanori Fushimi (1988) "Designing a Uniform Random Number Gererator Whose Subsequences are k-Distributed.",SIAM on Computing,Vol.17 , pp 89-99 [17]M.Fushimi and S.Tezuka (1983) "The k-Distribution of Generalized Feedback Shift Register Pseudorandom Numbers." Communications of ACM , Vol.26 , pp 516-523 [18] L.H.Miller (956) "Table of Percentage Points of Kolomogorov Statistics.",Journal of the American Statistical Association,Vol.51 , pp 111-121 [19]Neal Zierler(1959) "Linear Recurring Sequence.",SIAM ,Vol.7 ,pp 31-48 [20]R.C.Tauworthe (1965) "Random Numbers Generated by Linear Recurrence modulo Two.",Math. Compo. Vol.19, pp 201-209 [21]J.P.R. Tootill,W.D.Robinsom and D.J.Eagle(1973) "An Asymptatically Random Tausworthe Sequence." Journal of the ACM , Vol.20 , pp 469-481 [22]M.S.Weiss (1978) "Modifications of the Kolomogorov-Smirnov Statistic for use with correlated data.", Journal Df the American Statistical Association . Vol.73 .PP 872-875 [23]何淮中（民76年3月） 淺論隨機數列的方法，數學傳播11.1 [24]林茂文（民75年10月) 時間數列分析與預測，華泰書局 [25]楊浩二（民73年月） 多變量統計方法，華泰書局 描述 碩士
國立政治大學
統計學系資料來源 http://thesis.lib.nccu.edu.tw/record/#B2002005376 資料類型 thesis dc.contributor.advisor 李子壩 zh_TW dc.contributor.author (作者) 范雅燕 zh_TW dc.creator (作者) 范雅燕 zh_TW dc.date (日期) 1990 en_US dc.date (日期) 1989 en_US dc.date.accessioned 3-五月-2016 14:13:56 (UTC+8) - dc.date.available 3-五月-2016 14:13:56 (UTC+8) - dc.date.issued (上傳時間) 3-五月-2016 14:13:56 (UTC+8) - dc.identifier (其他 識別碼) B2002005376 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/90100 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 統計學系 zh_TW dc.description.abstract (摘要) 論文摘要 無論是在社會科學或是自然科學的研究中，經常會面對複雜難解的問題，需要利用電腦模擬一些自然狀態，此時亂數就會被應用來增加其可靠性，被少人為主觀的控制因素。 1973年Lewis & Payne 提出G F S R方法，這個方法所產生的擬隨機序列yt=O. atat+d........., t= 1 , 2 , .........。可以得到較線性除模法更長週期的序列，且可以改善在除模法中變數個數愈多，效果愈差的缺點，我們對此作理論上探討。 此外，我們比較幾個G F S R 的實際製作演算法討論G F S R 的優缺點。最後本文將探討有關此產生器的應用，如在部份判別分析及在K - S 統計量的修正上。 zh_TW dc.description.tableofcontents 目錄 第一章 緒論……1 第一節 研究動機與目的……1 第二節 研究範圍……3 第三節 本文架構……4 第二章 G F S R 的介紹……6 第一節 G F S R 的起源……6 第二節 G F S R 的基本性質……12 第三節 G F S R 的相關重要定理……17 第四節 G F S R 的特點……28 第三章 G F S R 的製作與檢驗……29 第一節Lewis & Payne 方法……29 第二節Collings & Hembree 方法……31 第三節Fushimi & Tezuka 方法……37 第四節k - distribution 的測試……38 第五節G F S R 與統計檢定……44 第四章 應用……55 第一節 應用於部份判別分析……55 第二節 K - S 統計量應用於A R (2) …… 64 第五章 結論……73 參考資料……75 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#B2002005376 en_US dc.title (題名) GFSR亂數產生器的研究 zh_TW dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [l] A.C. Arvillias and D.G. Maritsas (1978) "Partitioning the Period of a Class of m-Sequence and Application to Pseudorandom Number Generation.",Journal of the ACM, Vol.25 , pp 675-686 [2]Alexander Haas (1987) "The Multiple Prime Random Number Generator." ACM Transactions on Mathematical Software. Vol.13 .PP 368-381 [3]R.J.Beckman and M.E.Johnson (1981) "A Ranking Procedure for Partial Discriminant Analysis.",Journal of the American Statistical Associatjon.Vol.76, pp 671-675 [4]J.D.Broffitt.R.H.Randles and R.V.Hogg (1976) "Distribution-Free Partial Discriminant Analysis.",Journal of the American Statistical Association.Vol.7l , pp 934-939 [5]Bruce Jay Collings (1987) "Compound Random Number Generators. ",Journal of the American Association.Vol.82 , pp 525-527 [6]Bruce Jay Collings and G.Barry Hembree (1986) "Initializing Generalized Feedback Shift Register Pseudorandom Number Generators.", Journal of the ACH,Vol.33 , pp 706-711 [7]R.R.Coveyou and R.D.Macpherson (1967) "Fourier Analysis of Uniform Random Number Generators.",Journal of the ACH,Vol.14 , pp 100-119 [8]Gentle and Kennedy (1980) Statistical Computing, Published by Marcel Dekker ,New York, Ch 6 [9]Herbert S. Bright and Richard L. Enison (1979) "Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography.",Computing Surveys ,Vol.ll ,pp 357-370 [10]D . E.Knuth (1981) The Art of Computer Programming, V2 : Semi-numericalAlgorithms ,2nd Edition, Addison-Wesley, Reading ,Mass. [11]T.G.Lewis and W.H. Payne (1973) "Generalized Feedback Shift Register Pseudorandom Number Algorithm.",Journal of the ACM.Vol.20 .PP 456-468 [12]W.H.Payne. J.R.Rdbung and T.P.Bogyo(1969) "Coding the Lehmer Pseudo-random Number Generator.", Communications of ACM.Vol.12 ? pp 85-86 [13]W.H. Payne and K.L. McMillen (978) "Orderly Enumeration of Nonsingular Binary Matrices Applied to Text Encryption.". Communications of ACM.Vol.21, pp 259-263 [14]Marsaglia George (1984) "A Current View of Randow Number Generation.", Computer Science and Statistics: Sixteenth Symposiumon the Interface, Proceedings, pp 3-10 [15]Marsaglia George and Liang-Huei-Tsay (1985) "Matrices and the Structure of Random Number Sequences.",Linear Algebra and its Appliations ,Vol.67,pp 147-156 [16]Masanori Fushimi (1988) "Designing a Uniform Random Number Gererator Whose Subsequences are k-Distributed.",SIAM on Computing,Vol.17 , pp 89-99 [17]M.Fushimi and S.Tezuka (1983) "The k-Distribution of Generalized Feedback Shift Register Pseudorandom Numbers." Communications of ACM , Vol.26 , pp 516-523 [18] L.H.Miller (956) "Table of Percentage Points of Kolomogorov Statistics.",Journal of the American Statistical Association,Vol.51 , pp 111-121 [19]Neal Zierler(1959) "Linear Recurring Sequence.",SIAM ,Vol.7 ,pp 31-48 [20]R.C.Tauworthe (1965) "Random Numbers Generated by Linear Recurrence modulo Two.",Math. Compo. Vol.19, pp 201-209 [21]J.P.R. Tootill,W.D.Robinsom and D.J.Eagle(1973) "An Asymptatically Random Tausworthe Sequence." Journal of the ACM , Vol.20 , pp 469-481 [22]M.S.Weiss (1978) "Modifications of the Kolomogorov-Smirnov Statistic for use with correlated data.", Journal Df the American Statistical Association . Vol.73 .PP 872-875 [23]何淮中（民76年3月） 淺論隨機數列的方法，數學傳播11.1 [24]林茂文（民75年10月) 時間數列分析與預測，華泰書局 [25]楊浩二（民73年月） 多變量統計方法，華泰書局 zh_TW
