रैखिक सर्वांगसम जनक: Difference between revisions
(Created page with "{{Short description|Algorithm for generating pseudo-randomized numbers}} File:Linear_congruential_generator_visualisation.svg|thumb|480px|दो मॉड्यूलो-9...") |
No edit summary |
||
(8 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Algorithm for generating pseudo-randomized numbers}} | {{Short description|Algorithm for generating pseudo-randomized numbers}} | ||
[[File:Linear_congruential_generator_visualisation.svg|thumb|480px|दो | [[File:Linear_congruential_generator_visualisation.svg|thumb|480px|दो मापांक-9 एलसीजी दर्शाते हैं कि कैसे अलग-अलग मापदण्ड अलग-अलग चक्र लंबाई की ओर ले जाते हैं। प्रत्येक पंक्ति तब तक विकसित होती स्थिति को दर्शाती है जब तक वह दोहराई न जाए। शीर्ष पंक्ति m = 9, a = 2, c = 0 और 1 के मूल के साथ एक जनक दर्शाती है, जो लंबाई 6 का एक चक्र उत्पन्न करती है। दूसरी पंक्ति 3 के मूल के साथ एक ही जनक है, जो एक चक्र का उत्पादन करती है। लंबाई 2. a = 4 और c = 1 (नीचे पंक्ति) का उपयोग करने से [0, 8] में किसी भी मूल के साथ 9 की चक्र लंबाई मिलती है।]]एक रैखिक सर्वांगसम जनक (LCG) एक [[कलन विधि]] है जो एक असंतत खंडशः रैखिक समीकरण के साथ गणना की गई कूट-यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है। यह विधि सबसे पुराने और सबसे प्रसिद्ध [[छद्म यादृच्छिक संख्या जनरेटर|कूट यादृच्छिक संख्या जनक]] कलन विधि में से एक का प्रतिनिधित्व करती है। उनके पीछे के सिद्धांत को समझना अपेक्षाकृत सरल है, और उन्हें सरलता से और तीव्रता से अनुप्रयुक्त किया जाता है, विशेषकर परिकलक हार्डवेयर पर जो भंडारण-बिट खंडन द्वारा [[मॉड्यूलर अंकगणित|प्रमापीय अंकगणित]] प्रदान कर सकता है। | ||
जनक को [[पुनरावृत्ति संबंध]] द्वारा परिभाषित किया गया है: | |||
:<math>X_{n+1} = \left( a X_n + c \right)\bmod m</math> | :<math>X_{n+1} = \left( a X_n + c \right)\bmod m</math> | ||
जहाँ <math>X</math> कूट-यादृच्छिक मानों का क्रम है, और | |||
: <math> m,\, 0<m </math> - [[मॉड्यूलो ऑपरेशन]] | : <math> m,\, 0<m </math> - [[मॉड्यूलो ऑपरेशन|"मापांक]]" | ||
: <math> a,\,0 < a < m</math> -गुणक | : <math> a,\,0 < a < m</math> - "गुणक" | ||
: <math> c,\,0 \le c < m</math> - वृद्धि | : <math> c,\,0 \le c < m</math> - "वृद्धि" | ||
: <math> X_0,\,0 \le X_0 < m</math> - | : <math> X_0,\,0 \le X_0 < m</math> - "मूल" या "प्रारंभ मान" | ||
[[पूर्णांक]] स्थिरांक हैं जो | [[पूर्णांक]] स्थिरांक हैं जो जनक को निर्दिष्ट करते हैं। यदि c = 0 है, तो जनक को प्रायः गुणक सर्वांगसम जनक (MCG), या लेहमर आरएनजी कहा जाता है। यदि c ≠ 0 है, तो विधि को मिश्रित सर्वांगसम जनक कहा जाता है।{{r|KnuthV2|p=4-}} | ||
जब c ≠ 0, एक गणितज्ञ पुनरावृत्ति को एक [[रैखिक परिवर्तन]] कहेगा, | जब c ≠ 0, एक गणितज्ञ पुनरावृत्ति को एक [[रैखिक परिवर्तन]] नहीं, बल्कि एक सजातीय परिवर्तन कहेगा, परन्तु परिकलक विज्ञान में यह मिथ्या नाम अच्छी तरह से स्थापित है।<ref name=Steele20>{{cite arXiv | ||
|title=Computationally easy, spectrally good multipliers for congruential pseudorandom number generators | |title=Computationally easy, spectrally good multipliers for congruential pseudorandom number generators | ||
|first1=Guy |last1=Steele |author-link1=Guy Steele |first2=Sebastiano |last2=Vigna |author-link2=Sebastiano Vigna | |first1=Guy |last1=Steele |author-link1=Guy Steele |first2=Sebastiano |last2=Vigna |author-link2=Sebastiano Vigna | ||
Line 22: | Line 22: | ||
==इतिहास== | ==इतिहास== | ||
लेहमर | लेहमर जनक 1951 में प्रकाशित हुआ था<ref>{{Cite journal|last=Lehmer|first=Derrick H.|date=1951|title=बड़े पैमाने की कंप्यूटिंग इकाइयों में गणितीय तरीके|journal=Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery|pages=141–146}}</ref> और रैखिक सर्वांगसम जनक 1958 में डब्ल्यू. ई. थॉमसन और ए. रोटेनबर्ग द्वारा प्रकाशित किया गया था।<ref>{{Cite journal|last=Thomson|first=W. E.|date=1958|title=छद्म-यादृच्छिक संख्याएँ उत्पन्न करने की एक संशोधित सर्वांगसमता विधि|journal=The Computer Journal|volume=1|issue=2|pages=83|doi=10.1093/comjnl/1.2.83|doi-access=free}}</ref><ref>{{Cite journal|last=Rotenberg|first=A.|date=1960|title=एक नया छद्म-यादृच्छिक संख्या जेनरेटर|journal=Journal of the ACM|volume=7|issue=1|pages=75–77|doi=10.1145/321008.321019|s2cid=16770825}}</ref> | ||
== अवधि | == अवधि == | ||
एलसीजी का एक लाभ यह है कि मापदंडों के उचित चयन से एक ऐसी अवधि प्राप्त होती है जो ज्ञात और | एलसीजी का एक लाभ यह है कि मापदंडों के उचित चयन से एक ऐसी अवधि प्राप्त होती है जो ज्ञात और दीर्घ दोनों होती है। हालांकि यह एकमात्र मानदंड नहीं है, बहुत छोटी अवधि कूट-यादृच्छिक संख्या जनक में एक घातक दोष है।<ref name=History>{{cite conference | ||
|title=History of Uniform Random Number Generation | |title=History of Uniform Random Number Generation | ||
|first=Pierre |last=L'Ecuyer | |first=Pierre |last=L'Ecuyer | ||
Line 37: | Line 37: | ||
|id=[https://hal.inria.fr/hal-01561551 hal-01561551] | |id=[https://hal.inria.fr/hal-01561551 hal-01561551] | ||
}}</ref> | }}</ref> | ||
ऐतिहासिक रूप से, खराब विकल्पों के कारण एलसीजी का कार्यान्वयन अप्रभावी हो गया है। इसका एक विशेष उदाहरण [[RANDU]] है, जिसका 1970 के दशक | जबकि एलसीजी कूट-यादृच्छिक संख्याएं उत्पन्न करने में सक्षम हैं जो यादृच्छिकता के लिए औपचारिक परीक्षण पारित कर सकते हैं, आउटपुट की गुणवत्ता मापदण्ड m और a के चयन के प्रति अत्यधिक संवेदनशील है।{{r|Marsaglia68|KnuthV2|Park88|Hörmann92|LEcuyer99|Steele20}} उदाहरण के लिए, a = 1 और c = 1 एक साधारण मापांक-m गुणक का निर्माण करता है, जिसकी दीर्घ अवधि होती है, परन्तु यह स्पष्ट रूप से गैर-यादृच्छिक है। | ||
ऐतिहासिक रूप से, खराब विकल्पों के कारण एलसीजी का कार्यान्वयन अप्रभावी हो गया है। इसका एक विशेष उदाहरण [[RANDU|आरएएनडीयू]] है, जिसका 1970 के दशक के प्रारंभ में व्यापक रूप से उपयोग किया गया था और इसके कई परिणाम सामने आए थे, जिन पर वर्तमान में इस खराब एलसीजी के उपयोग के कारण प्रश्न उठाए जा रहे हैं।<ref name="Press">{{cite book |last=Press | | |||
first=William H. |year=1992 |title=Numerical Recipes in Fortran 77: The Art of Scientific Computing |edition=2nd |isbn=978-0-521-43064-7 |display-authors=etal |title-link=Numerical Recipes }}</ref> | first=William H. |year=1992 |title=Numerical Recipes in Fortran 77: The Art of Scientific Computing |edition=2nd |isbn=978-0-521-43064-7 |display-authors=etal |title-link=Numerical Recipes }}</ref> | ||
मापदण्ड चयन के तीन सामान्य वर्ग हैं: | |||
=== m अभाज्य, c = 0 === | |||
{{main|लेहमर यादृच्छिक संख्या जनित्र}} | |||
यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है | यह मूल लेहमर आरएनजी निर्माण है। यदि गुणक a को पूर्णांक गुणांक m का एक [[आदिम तत्व (परिमित क्षेत्र)|पूर्वग अवयव]] चुना जाता है, तो अवधि m−1 है। प्रारंभिक अवस्था को 1 और m−1 के मध्य चुना जाना चाहिए। | ||
अभाज्य गुणांक की एक हानि यह है कि प्रमापीय कमी के लिए दोगुनी-चौड़ाई वाले उत्पाद और एक स्पष्ट न्यूनीकरण चरण की आवश्यकता होती है। प्रायः 2 की घात से कम अभाज्य का उपयोग किया जाता है (मेरसेन अभाज्य 2<sup>31</sup>−1 और 2<sup>61</sup>−1 लोकप्रिय हैं), ताकि न्यूनीकरण मापांक m = 2<sup>e</sup> − d की गणना (ax मॉड 2) + ''d'' ⌊''ax''/2<sup>''e''</sup>⌋ के रूप में की जा सके। यदि परिणाम बहुत बड़ा है तो इसके बाद m का सशर्त घटाव होना चाहिए, परन्तु घटाव की संख्या ad/m तक सीमित है, जिसे d छोटा होने पर सरलता से एक तक सीमित किया जा सकता है। | |||
यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है और गुणक को सावधानी से चुना गया है, तो श्रेज की विधि<ref>{{cite web | |||
|title=Computer Systems Performance Analysis Chapter 26: Random-Number Generation | |title=Computer Systems Performance Analysis Chapter 26: Random-Number Generation | ||
|first=Raj |last=Jain |date=9 July 2010 | |first=Raj |last=Jain |date=9 July 2010 | ||
Line 55: | Line 58: | ||
|url=http://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf#page=19 | |url=http://www.cse.wustl.edu/~jain/iucee/ftp/k_26rng.pdf#page=19 | ||
|access-date=2017-10-31 | |access-date=2017-10-31 | ||
}}</ref> उपयोग किया जा सकता है। ऐसा करने के लिए, कारक m = qa+r, | }}</ref> का उपयोग किया जा सकता है। ऐसा करने के लिए, कारक m = qa+r, अर्थात {{nobr|1=''q'' = {{floor|''m''/''a''}}}} और r = m मॉड a है। फिर ax मॉड m = {{nobr|''a''(''x'' mod ''q'') − ''r''{{floor|''x''/''q''}}}} की गणना करें। चूँकि x मॉड q < q ≤ m/a, पहला पद am/a = m से बिल्कुल कम है। यदि a को इस प्रकार चुना जाता है कि r ≤ q (और इस प्रकार r/q ≤ 1), तो दूसरा पद भी m से कम r{{floor|''x''/''q''}} ≤ rx/q = x(r/q) ≤ x < m है। इस प्रकार, दोनों उत्पादों की गणना एक एकल-चौड़ाई वाले उत्पाद के साथ की जा सकती है और उनके मध्य का अंतर [1−m, m−1] की सीमा में है, इसलिए एकल सशर्त जोड़ के साथ इसे [0, m−1] तक कम किया जा सकता है।<ref>{{cite web | ||
|title=Schrage's Method | |title=Schrage's Method | ||
|url=http://home.earthlink.net/~pfenerty/pi/schrages_method.html | |url=http://home.earthlink.net/~pfenerty/pi/schrages_method.html | ||
Line 61: | Line 64: | ||
|access-date=2017-10-31 | |access-date=2017-10-31 | ||
}}</ref> | }}</ref> | ||
दूसरी हानि यह है कि मान 1 ≤ x < m को समान यादृच्छिक बिट्स में परिवर्तित करना अनुपयुक्त है। यदि 2 की घात से कम अभाज्य का उपयोग किया जाता है, तो कभी-कभी लुप्त मानों को सरलता से उपेक्षित कर दिया जाता है। | |||
=== m 2 की घात, c = 0 === | |||
m को 2 की घात के रूप में चुनना, प्रायः m = 2<sup>32</sup> या m = 2<sup>64</sup>, एक विशेष रूप से कुशल एलसीजी उत्पन्न करता है, क्योंकि यह केवल द्विचर प्रतिनिधित्व को छोटा करके मापांक संचालन की गणना करने की अनुमति देता है। वास्तव में, सबसे महत्वपूर्ण बिट्स की सामान्यतः गणना ही नहीं की जाती है। हालाँकि, इसकी हानि भी हैं। | |||
इस विधि में अधिकतम अवधि m/4 है, जो a ≡ 3 या a ≡ 5 (मॉड 8) होने पर प्राप्त होती है। प्रारंभिक अवस्था X<sub>0</sub> विषम होना चाहिए और X के निम्न तीन बिट दो स्थितियों के मध्य वैकल्पिक होते हैं और उपयोगी नहीं होते हैं। यह दर्शाया जा सकता है कि यह विधि एक जनक के बराबर है जिसका मापांक एक चौथाई आकार और c ≠ 0 है।{{r|KnuthV2}} | |||
=== | 2 की घात के मापांक के उपयोग के साथ एक अधिक जटिल विवाद यह है कि कम बिट्स की अवधि उच्च बिट्स की तुलना में कम होती है। X का निम्नतम क्रम वाला बिट कभी परिवर्तित नहीं होता है (X सदैव विषम होता है) और अगले दो बिट दो स्थितियों के मध्य वैकल्पिक होते हैं। यदि a≡5 (मॉड 8) है, तो बिट 1 कभी परिवर्तित नहीं होता है और बिट 2 परिवर्तित होता है। यदि a≡3 (मॉड 8) है, तो बिट 2 कभी परिवर्तित नहीं होता है और बिट 1 परिवर्तित होता है। बिट 3, 4 की अवधि के साथ दोहराता है, बिट 4 का आवर्त 8 है, इत्यादि। केवल X का सबसे महत्वपूर्ण बिट ही पूर्ण अवधि प्राप्त करता है। | ||
जब c ≠ 0, सही ढंग से चुने गए | |||
=== c ≠ 0 === | |||
जब c ≠ 0, सही ढंग से चुने गए मापदण्ड सभी मूल मानों के लिए m के बराबर अवधि की अनुमति देते हैं। यह तब घटित होगा जब और केवल यदि:{{r|KnuthV2|p=17—19}} | |||
# <math>m</math> और <math>c</math> [[सहअभाज्य पूर्णांक]] हैं, | # <math>m</math> और <math>c</math> [[सहअभाज्य पूर्णांक]] हैं, | ||
# <math>a - 1</math> के सभी अभाज्य गुणनखंडों से विभाज्य | # <math>a - 1</math> के सभी अभाज्य गुणनखंडों से विभाज्य <math>m</math> है, | ||
# <math>a - 1</math> | # <math>a - 1</math> 4 से विभाज्य है यदि <math>m</math>, 4 से विभाज्य है। | ||
इन तीन आवश्यकताओं को हल-डोबेल प्रमेय के रूप में जाना जाता है।<ref>{{Cite journal | इन तीन आवश्यकताओं को हल-डोबेल प्रमेय के रूप में जाना जाता है।<ref>{{Cite journal | ||
Line 89: | Line 93: | ||
|isbn=978-0-471-49694-6 | |isbn=978-0-471-49694-6 | ||
}}</ref> | }}</ref> | ||
यद्यपि हल-डोबेल प्रमेय अधिकतम अवधि प्रदान करता है, यह एक अच्छे | इस विधि का उपयोग किसी भी m के साथ किया जा सकता है, परन्तु यह केवल m के लिए कई दोहराए गए अभाज्य कारकों के साथ ही अच्छा कार्य करता है, जैसे कि 2 की घात; परिकलक के शब्द आकार का उपयोग करना सबसे सामान्य विकल्प है। यदि m एक [[वर्ग-मुक्त पूर्णांक]] होता, तो यह केवल ≡ 1 (मॉड m) की अनुमति देता, जो बहुत खराब पीआरएनजी बनाता है; संभावित पूर्ण-अवधि गुणकों का चयन केवल तभी उपलब्ध होता है जब m में अभाज्य गुणनखंड दोहराए जाते हैं। | ||
यद्यपि हल-डोबेल प्रमेय अधिकतम अवधि प्रदान करता है, यह एक अच्छे जनक की प्रत्याभूति देने के लिए पर्याप्त नहीं है। उदाहरण के लिए, यह वांछनीय है कि a − 1, m के अभाज्य गुणनखंडों द्वारा आवश्यकता से अधिक विभाज्य न हो। इस प्रकार, यदि m, 2 की घात है, तो a − 1 को 4 से विभाज्य होना चाहिए, परन्तु 8 से विभाज्य नहीं होना चाहिए, अर्थात a ≡ 5 (मॉड 8)।{{r|KnuthV2|p=§3.2.1.3}} | |||
वास्तव में, अधिकांश गुणक एक अनुक्रम उत्पन्न करते हैं जो गैर-यादृच्छिकता या किसी अन्य के लिए एक परीक्षण में विफल रहता है, और एक ऐसा गुणक ढूंढता है जो सभी अनुप्रयुक्त मानदंडों के लिए संतोषजनक हो,{{r|KnuthV2|p=§3.3.3}} काफी चुनौतीपूर्ण है। [[वर्णक्रमीय परीक्षण]] सबसे महत्वपूर्ण परीक्षणों में से एक है।<ref name="Austin2008">{{cite web |first=David |last=Austin |title=Random Numbers: Nothing Left to Chance |date=March 2008 |publisher=American Mathematical Society |url=https://www.ams.org/publicoutreach/feature-column/fcarc-random}}</ref> | |||
ध्यान दें कि 2 की घात के मापांक c = 0 के लिए ऊपर वर्णित समस्या को साझा करता है: निम्न k बिट्स मापांक 2<sup>k</sup> के साथ एक जनक बनाते हैं और इस प्रकार 2<sup>k</sup> की अवधि के साथ दोहराते हैं; केवल सबसे महत्वपूर्ण बिट ही पूर्ण अवधि को प्राप्त करता है। यदि r से कम कूट-यादृच्छिक संख्या वांछित है, {{floor|''rX''/''m''}} X मॉड r की तुलना में बहुत उच्च गुणवत्ता वाला परिणाम है। दुर्भाग्य से, अधिकांश क्रमादेश भाषाएँ बाद वाले (<code>X % r</code>) को लिखना बहुत सरल बना देती हैं, इसलिए यह अधिक सामान्यतः उपयोग की जाने वाली विधि है। | |||
ध्यान दें कि | |||
जनक c के चयन के प्रति संवेदनशील नहीं है, जब तक कि यह मापांक के लिए अपेक्षाकृत प्रमुख है (उदाहरण के लिए यदि m 2 की घात है, तो c विषम होना चाहिए), इसलिए मान c=1 सामान्यतः चुना जाता है। | |||
C के अन्य विकल्पों द्वारा निर्मित श्रृंखला को श्रृंखला के एक | C के अन्य विकल्पों द्वारा निर्मित श्रृंखला को श्रृंखला के एक सामान्य फलन के रूप में लिखा जा सकता है जब c=1 है।{{r|KnuthV2|p=11}} विशेष रूप से, यदि Y, Y<sub>0</sub> = 0 और Y<sub>''n''+1</sub> = aY<sub>n</sub>+1 मॉड m द्वारा परिभाषित प्रोटोटाइप श्रृंखला है, तो एक सामान्य श्रृंखला X<sub>''n''+1</sub> = X<sub>n</sub>+c मॉड m को Y के एफ़िन फलन के रूप में लिखा जा सकता है: | ||
:<math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m | :<math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m</math> | ||
अधिक सामान्यतः, समान गुणक और मापांक वाली किन्हीं दो श्रृंखलाओं X और Z से संबंधित | अधिक सामान्यतः, समान गुणक और मापांक वाली किन्हीं दो श्रृंखलाओं X और Z से संबंधित हैं। | ||
:<math>{ X_n - X_0 \over X_1 - X_0 } = Y_n = {a^n - 1 \over a - 1} = { Z_n - Z_0 \over Z_1 - Z_0 } \pmod m | :<math>{ X_n - X_0 \over X_1 - X_0 } = Y_n = {a^n - 1 \over a - 1} = { Z_n - Z_0 \over Z_1 - Z_0 } \pmod m</math> | ||
== सामान्य उपयोग में | == सामान्य उपयोग में मापदण्ड == | ||
निम्न तालिका सामान्य उपयोग में एलसीजी के मापदंडों को सूचीबद्ध करती है, जिसमें विभिन्न [[ संकलक ]] | निम्न तालिका सामान्य उपयोग में एलसीजी के मापदंडों को सूचीबद्ध करती है, जिसमें विभिन्न [[ संकलक |संकलकों]] के [[ क्रम पुस्तकालय |कार्यावधि पुस्तकालयों]] में अंतर्निहित रैंड () फलन सम्मिलित हैं। यह तालिका लोकप्रियता दर्शाने के लिए है, अनुकरण करने के लिए उदाहरण नहीं; इनमें से कई मापदण्ड ख़राब हैं। अच्छे मापदंडों की तालिकाएँ उपलब्ध हैं।{{r|LEcuyer99|Steele20}} | ||
{|class="wikitable" | {|class="wikitable" | ||
! | ! स्रोत || गुणांक<br/>''m'' || गुणक<br/>''a'' || वृद्धि<br/>''c'' || रैंड () या रैंडम (L) में मूल के आउटपुट बिट्स | ||
|- | |- | ||
| ''[[ZX81]]'' || 2<sup>16</sup> + 1 || 75 || 74 || | | ''[[ZX81|जेडएक्स81]]'' || 2<sup>16</sup> + 1 || 75 || 74 || | ||
|- | |- | ||
| ''[[Numerical Recipes]]'' | | "त्वरित और ख़राब जनक" सूची से ''[[Numerical Recipes|संख्यात्मक व्यंजन]]'' , | ||
अध्याय 7.1, समीकरण- 7.1.6<br /> नुथ और एच. डब्ल्यू. लुईस से मापदण्ड | |||
| 2<sup>32</sup> || 1664525 || 1013904223 || | |||
|- | |- | ||
| [[Borland]] | | [[Borland|बोरलैंड]] सी/सी++ || 2<sup>32</sup> || 22695477 || 1 || रैंड() में बिट्स 30..16, लैरैंड() में 30..0 | ||
|- | |- | ||
| [[glibc]] ( | | [[glibc|ग्लिबीसी]] ([[GNU Compiler Collection|जीसीसी]] द्वारा प्रयुक्त)<ref>[https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.26#l362 Implementation in glibc-2.26 release.] See the code after the test for "TYPE_0"; the GNU C library's ''rand()'' in [[stdlib.h]] uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator ([https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.26#l187 initialized using ''minstd_rand0'']) and the period increases. See the [http://www.mscs.dal.ca/~selinger/random/ simplified code] that reproduces the random sequence from this library.</ref> | ||
| 2<sup>31</sup> || 1103515245 || 12345 || | | 2<sup>31</sup> || 1103515245 || 12345 || बिट्स 30..0 | ||
|- | |- | ||
| [[ANSI C]]: [[Watcom C compiler| | | [[ANSI C|एएनएसआई सी]]: [[Watcom C compiler|वाटकॉम]], [[Digital Mars|डिजिटल मार्स]], [[CodeWarrior|कोडवॉरियर]], [[IBM VisualAge|आईबीएम विजुअलएज]] सी/सी++<ref>{{cite book|title=A collection of selected pseudorandom number generators with linear structures |author=K. Entacher |date=21 August 1997 |url=http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.53.3686&rep=rep1&type=pdf |access-date=16 June 2012 |citeseerx=10.1.1.53.3686}}</ref><br/>[[C90 (C version)|सी90]], [[C99|सी99]], [[C11 (C standard revision)|सी11]]: आईएसओ/आईईसी 9899 में सुझाव,<ref>{{cite web|title=Last public Committee Draft from April 12, 2011|page=346f|url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf|access-date=21 Dec 2014}}</ref> [[C17 (C standard revision)|सी]][[C17 (C standard revision)|17]]|| 2<sup>31</sup> || 1103515245 || 12345 || बिट्स 30..16 | ||
|- | |- | ||
| [[Borland Delphi]], [[Virtual Pascal]] || 2<sup>32</sup> || 134775813 || 1 || | | [[Borland Delphi|बोरलैंड डेल्फ़ी]], [[Virtual Pascal|वास्तविक पास्कल]] || 2<sup>32</sup> || 134775813 || 1 || बिट्स 63..32 of ''(मूल × L)'' | ||
|- | |- | ||
| [[Turbo Pascal]] || 2<sup>32</sup> || 134775813 (8088405<sub>16</sub>) || 1 || | | [[Turbo Pascal|टर्बो पास्कल]] || 2<sup>32</sup> || 134775813 (8088405<sub>16</sub>) || 1 || | ||
|- | |- | ||
| [[Visual C++| | | [[Visual C++|माइक्रोसॉफ्ट]] [[Visual Basic|दृश्य]]/क्विक सी/सी++ || 2<sup>32</sup> || 214013 (343एफडी<sub>16</sub>) || 2531011 (269ईसी3<sub>16</sub>) || बिट्स 30..16 | ||
|- | |- | ||
| [[Visual Basic| | | [[Visual Basic|माइक्रोसॉफ्ट मूल दृश्य]] (6 और पूर्व)<ref>{{cite web |title=How Visual Basic Generates Pseudo-Random Numbers for the RND Function |url=http://support.microsoft.com/kb/231847 |publisher=Microsoft |access-date=17 June 2011 |archive-url=https://www.betaarchive.com/wiki/index.php/Microsoft_KB_Archive/231847 |archive-date=21 July 2020 |url-status = dead |date=24 June 2004}}</ref> || {{math|''2''<sup>''24''</sup>}} || 1140671485 (43एफडी43एफडी<sub>16</sub>) || 12820163 (सी39ईसी3<sub>16</sub>) || | ||
|- | |- | ||
| | | [[Native API|नेटिव एपीआई]] से आरटीएलयूनिफ़ॉर्म<ref>In spite of documentation on [http://msdn.microsoft.com/en-us/library/bb432429(VS.85).aspx MSDN], RtlUniform uses LCG, and not Lehmer's algorithm, implementations before [[Windows Vista]] are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied</ref> || 2<sup>31</sup> − 1 | ||
|| 2147483629 ( | || 2147483629 (7एफएफएफएफएफईडी<sub>16</sub>) || 2147483587 (7एफएफएफएफएफसी3<sub>16</sub>) || | ||
|- | |- | ||
| [[CarbonLib| | | [[CarbonLib|एप्पल कार्बनलिब]], [[C++11|सी]][[C++11|++11]] का <code>minstd_rand0</code>,<ref name="cpp11">{{ cite web | title = ISO/IEC 14882:2011 | publisher = ISO | date = 2 September 2011 | url = http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=50372 | access-date =3 September 2011 }}</ref> एमएटीएलएबी का वी4 लीगेसी जनक एमसीजी16807<ref>{{ cite web | title = Creating and Controlling a Random Number Stream | publisher = MathWorks | url = https://www.mathworks.com/help/matlab/math/creating-and-controlling-a-random-number-stream.html | access-date = 7 June 2021 }}</ref> || 2<sup>31</sup> − 1 || 16807 || 0 || [[MINSTD|एमआईएनएसटीडी]] देखें | ||
|- | |- | ||
| [[C++11]] | | [[C++11|सी]][[C++11|++11]] का <code>minstd_rand</code><ref name="cpp11" /> || 2<sup>31</sup> − 1 || 48271 || 0 || [[MINSTD|एमआईएनएसटीडी]] देखें | ||
|- | |- | ||
| [[ | | [[Donald Knuth|डोनाल्ड नुथ]] द्वारा [[MMIX|एमएमआईएक्स]] || 2<sup>64</sup> || 6364136223846793005 || 1442695040888963407 || | ||
|- | |- | ||
| [[Newlib]] || 2<sup>64</sup> || 6364136223846793005 || 1 || | | [[Newlib|न्यूलिब]] || 2<sup>64</sup> || 6364136223846793005 || 1 || बिट्स 62..32 (16-बिट इंट के लिए 46..32) | ||
|- | |- | ||
| [[Musl]] || 2<sup>64</sup> || 6364136223846793005 || 1 || | | [[Musl|मसल]] || 2<sup>64</sup> || 6364136223846793005 || 1 || बिट्स 63..33 | ||
|- | |- | ||
| [[OpenVMS| | | [[OpenVMS|वीएमएस]] का '''एमटीएच$आरएएनडीओएम''',<ref>{{cite web| url = https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html| title = GNU Scientific Library: Other random number generators}}</ref> [[glibc|ग्लिबीसी]] का पुराना संस्करण || 2<sup>32</sup> || 69069 (10डीसीडी<sub>16</sub>) || 1 || | ||
|- | |- | ||
| [[Java (programming language)| | | [[Java (programming language)|जावा]] का जावा.यूटिल{{Not a typo|.}}रैन्डम, [[POSIX|पीओएसआईएक्स]] [ln]रैंड48, [[glibc|ग्लिबीसी]] [ln]रैंड 48[_r]|| 2<sup>48</sup> || 25214903917 (5डीईसीई66डी<sub>16</sub>) || 11 || बिट्स 47..16 | ||
|- | |- | ||
| | | | ||
Line 175: | Line 183: | ||
|| 134456 = 2<sup>3</sup>7<sup>5</sup> || 8121 || 28411 || <math>\frac{ X_n }{ 134456 }</math> | || 134456 = 2<sup>3</sup>7<sup>5</sup> || 8121 || 28411 || <math>\frac{ X_n }{ 134456 }</math> | ||
|- | |- | ||
| [[POSIX]]<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/ The Open Group Base Specifications Issue 7] | | [[POSIX|पीओएसआईएक्स]]<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/ The Open Group Base Specifications Issue 7] | ||
IEEE Std 1003.1, 2013 Edition</ref> [jm] | IEEE Std 1003.1, 2013 Edition</ref> [jm]रैंड48, [[glibc|ग्लिबीसी]] [mj]रैंड48[_r]|| 2<sup>48</sup> || 25214903917 (5डीईसीई66डी<sub>16</sub>) || 11 || बिट्स 47..15 | ||
|- | |- | ||
| [[POSIX]] [de] | | [[POSIX|पीओएसआईएक्स]] [de]रैंड48, [[glibc|ग्लिबीसी]] [de]रैंड48[_r]|| 2<sup>48</sup> || 25214903917 (5डीईसीई66डी<sub>16</sub>) || 11 || बिट्स 47..0 | ||
|- | |- | ||
| [[cc65]]<ref>{{cite web|first=Sidney|last=Cadot|url=https://github.com/cc65/cc65/blob/06bb95d19788e3326738ee968b49dd11d18ca790/libsrc/common/rand.s|title=rand.s|work=cc65|access-date=8 July 2016}}</ref> || 2<sup>23</sup> || 65793 (10101<sub>16</sub>) || 4282663 (415927<sub>16</sub>) || | | [[cc65|सीसी65]]<ref>{{cite web|first=Sidney|last=Cadot|url=https://github.com/cc65/cc65/blob/06bb95d19788e3326738ee968b49dd11d18ca790/libsrc/common/rand.s|title=rand.s|work=cc65|access-date=8 July 2016}}</ref> || 2<sup>23</sup> || 65793 (10101<sub>16</sub>) || 4282663 (415927<sub>16</sub>) || बिट्स 22..8 | ||
|- | |- | ||
| [[cc65]] || 2<sup>32</sup> || 16843009 (1010101<sub>16</sub>) || 826366247 (31415927<sub>16</sub>) || | | [[cc65|सीसी65]] || 2<sup>32</sup> || 16843009 (1010101<sub>16</sub>) || 826366247 (31415927<sub>16</sub>) || बिट्स 31..16 | ||
|- | |- | ||
| [[cc65]] || 2<sup>32</sup> || 16843009 (1010101<sub>16</sub>) || 3014898611 ( | | [[cc65|सीसी65]] || 2<sup>32</sup> || 16843009 (1010101<sub>16</sub>) || 3014898611 (बी3बी3बी3बी3<sub>16</sub>) || पहले के बिट्स 31..16, वर्तमान बिट्स 31..16 एक्सऑर बिट्स 14..0 | ||
|- style="border-top:2px solid;" | |- style="border-top:2px solid;" | ||
| '' | | ''पूर्व में सामान्य:'' {{midsize|[[आरएएनडीयू]]}}<ref name=Press/> || 2<sup>31</sup> || 65539 || 0 || | ||
|} | |} | ||
जैसा कि ऊपर | जैसा कि ऊपर दर्शाया गया है, एलसीजी सदैव अपने द्वारा उत्पादित मानों में सभी बिट्स का उपयोग नहीं करते हैं। उदाहरण के लिए, [[जावा (प्रोग्रामिंग भाषा)|जावा]] कार्यान्वयन प्रत्येक पुनरावृत्ति पर 48-बिट मानों के साथ संचालित होता है, परन्तु केवल उनके 32 सबसे महत्वपूर्ण बिट्स लौटाता है। ऐसा इसलिए है क्योंकि उच्च-क्रम वाले बिट्स की अवधि निचले-क्रम वाले बिट्स की तुलना में लंबी होती है (नीचे देखें)। एलसीजी जो इस खंडन प्रविधि का उपयोग करते हैं, वे उन लोगों की तुलना में सांख्यिकीय रूप से श्रेष्ठतर मान उत्पन्न करते हैं जो ऐसा नहीं करते हैं। यह उन आलेखों में विशेष रूप से ध्यान देने योग्य है जो पंक्ति श्रृंखला को कम करने के लिए मॉड संक्रिया का उपयोग करते हैं; यादृच्छिक संख्या मॉड 2 को संशोधित करने से बिना किसी खंडन के 0 और 1 को वैकल्पिक किया जा सकेगा। | ||
== | ==लाभ और हानि== | ||
{{More sources needed section|date= | {{More sources needed section|date=जुलाई 2021}} | ||
एलसीजी | एलसीजी तीव्र हैं और स्थिति को बनाए रखने के लिए न्यूनतम मेमोरी (एक मापांक-m संख्या, प्रायः 32 या 64 बिट्स) की आवश्यकता होती है। यह उन्हें कई स्वतंत्र धाराओं के अनुकरण के लिए मूल्यवान बनाता है। गूढ़लेखिकी अनुप्रयोगों के लिए एलसीजी का उद्दिष्ट नहीं है और इसका उपयोग नहीं किया जाना चाहिए; ऐसे अनुप्रयोगों के लिए [[क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म यादृच्छिक संख्या जनरेटर|गूढ़लेखिकी रूप से सुरक्षित कूट यादृच्छिक संख्या जनक]] का उपयोग करें। | ||
[[Image:Lcg 3d.gif|thumb|200px|तीन आयामों में एक रैखिक सर्वांगसम | [[Image:Lcg 3d.gif|thumb|200px|तीन आयामों में एक रैखिक सर्वांगसम जनक के [[हाइपरप्लेन|अधिसमतल]] है। वर्णक्रमीय परीक्षण इसी संरचना को मापता है।]]हालाँकि एलसीजी में कुछ विशिष्ट दोष हैं, परन्तु उनकी कई खामियाँ बहुत छोटी स्थिति के कारण आती हैं। तथ्य यह है कि लोगों को इतने सालों से ऐसे छोटे गुणांक के साथ उपयोग करने के लिए प्रेरित किया गया है, इसे प्रविधि के गुण के प्रमाण के रूप में देखा जा सकता है। पर्याप्त बड़े अवस्था वाले एलसीजी कड़े सांख्यिकीय परीक्षणों को भी पारित कर सकता है; एक मापांक-2 एलसीजी जो उच्च 32 बिट्स लौटाता है, परीक्षणयू01 के छोटे क्रश समूह से गुजरता है,{{citation needed|date=November 2017|reason=O'Neill stated this result somewhere, but I'm having a hard time finding it.}} और 96-बिट एलसीजी सबसे कड़े बड़े क्रश समूह से गुजरता है।<ref>{{cite techreport | ||
|title=PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation | |title=PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation | ||
|first=Melissa E. |last=O'Neill | |first=Melissa E. |last=O'Neill | ||
Line 203: | Line 211: | ||
|url=http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf#page=9 | |url=http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf#page=9 | ||
}}</ref> | }}</ref> | ||
एक विशिष्ट उदाहरण के लिए, 32 बिट आउटपुट के साथ एक आदर्श यादृच्छिक संख्या | एक विशिष्ट उदाहरण के लिए, 32 बिट आउटपुट के साथ एक आदर्श यादृच्छिक संख्या जनक से ([[जन्मदिन प्रमेय|बर्थ्डै प्रमेय]] के अनुसार) {{math|{{sqrt|''m''}} ≈ 2<sup>16</sup>}} परिणामों के बाद पहले के आउटपुट को अनुलिपि करना, प्रारंभ करने की आशा की जाती है। कोई भी पीआरएनजी जिसका आउटपुट उसकी पूर्ण, असंतुलित स्थिति है, तब तक अनुलिपि उत्पन्न नहीं करेगा जब तक कि उसकी सम्पूर्ण अवधि समाप्त न हो जाए, यह एक सरलता से पता लगाने योग्य सांख्यिकीय दोष है। संबंधित कारणों से, किसी भी पीआरएनजी की अवधि आवश्यक आउटपुट की संख्या के वर्ग से अधिक होनी चाहिए। आधुनिक परिकलक गति को देखते हुए, इसका अर्थ है कि कम से कम मांग वाले अनुप्रयोगों को छोड़कर सभी के लिए 2<sup>64</sup> की अवधि, और मांग वाले अनुकरण के लिए दीर्घ अवधि है। | ||
एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि | एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि n-आयामी समष्टि में बिंदुओं को चुनने के लिए उपयोग किया जाता है, तो बिंदु अधिक-से-अधिक, {{math|{{radic|''n''!⋅''m''|''n''}} }}[[हाइपरप्लेन|अधिसमतल]] (मार्सग्लिया का प्रमेय, [[जॉर्ज मार्साग्लिया]] द्वारा विकसित) पर स्थित होंगे।<ref name=Marsaglia68>{{cite journal | ||
|title=Random Numbers Fall Mainly in the Planes | |title=Random Numbers Fall Mainly in the Planes | ||
|first=George |last=Marsaglia |author-link=George Marsaglia | |first=George |last=Marsaglia |author-link=George Marsaglia | ||
Line 211: | Line 219: | ||
|doi=10.1073/pnas.61.1.25 |doi-access=free |bibcode=1968PNAS...61...25M |pmc=285899 | |doi=10.1073/pnas.61.1.25 |doi-access=free |bibcode=1968PNAS...61...25M |pmc=285899 | ||
|url=https://www.pnas.org/content/61/1/25.full.pdf |pmid=16591687 | |url=https://www.pnas.org/content/61/1/25.full.pdf |pmid=16591687 | ||
}}</ref> यह अनुक्रम X के क्रमिक मानों के | }}</ref> यह अनुक्रम X<sub>n</sub> के क्रमिक मानों के मध्य क्रमिक सहसंबंध के कारण है। असावधानतः चुने गए गुणकों में सामान्यतः बहुत कम, व्यापक दूरी वाले विमान होंगे, जिससे समस्याएं उत्पन्न हो सकती हैं। वर्णक्रमीय परीक्षण, जो एलसीजी की गुणवत्ता का एक सरल परीक्षण है, इस अंतर को मापता है और एक अच्छे गुणक को चुनने की अनुमति देता है। | ||
समतल अंतर मापांक और गुणक दोनों पर निर्भर करता है। एक बड़ा पर्याप्त मापांक इस दूरी को दोहरे परिशुद्धता संख्याओं के | समतल अंतर मापांक और गुणक दोनों पर निर्भर करता है। एक बड़ा पर्याप्त मापांक इस दूरी को दोहरे परिशुद्धता संख्याओं के खंडन से कम कर सकता है। मापांक बड़ा होने पर गुणक का चुनाव कम महत्वपूर्ण हो जाता है। वर्णक्रमीय सूचकांक की गणना करना और यह सुनिश्चित करना अभी भी आवश्यक है कि गुणक खराब नहीं है, परन्तु विशुद्ध रूप से संभाव्य रूप से जब मापांक लगभग 2<sup>64</sup> से बड़ा होता है तो खराब गुणक का सामना करना अत्यधिक असंभव हो जाता है। | ||
एलसीजी के लिए विशिष्ट एक और दोष निम्न- | एलसीजी के लिए विशिष्ट एक और दोष निम्न-अनुक्रम बिट्स की छोटी अवधि है जब m को 2 की घात के रूप में चुना जाता है। इसे आवश्यक आउटपुट से बड़े मापांक का उपयोग करके और समष्टि के सबसे महत्वपूर्ण बिट्स का उपयोग करके कम किया जा सकता है। | ||
फिर भी, कुछ अनुप्रयोगों के लिए एलसीजी एक अच्छा विकल्प हो सकता है। उदाहरण के लिए, एक | फिर भी, कुछ अनुप्रयोगों के लिए एलसीजी एक अच्छा विकल्प हो सकता है। उदाहरण के लिए, एक सन्निहित प्रणाली में, उपलब्ध मेमोरी की मात्रा प्रायः गंभीर रूप से सीमित होती है। इसी तरह, [[ विडियो गेम कंसोल |विडियो गेम कंसोल]] जैसे वातावरण में एलसीजी की थोड़ी संख्या में उच्च-क्रम बिट्स लेना पर्याप्त हो सकता है। जब m, 2 की घात हो तो एलसीजी के निम्न-क्रम वाले बिट्स पर कभी भी यादृच्छिकता की किसी भी डिग्री के लिए विश्वास नहीं किया जाना चाहिए। निम्न-क्रम वाले बिट्स बहुत छोटे चक्रों से गुजरते हैं। विशेष रूप से, कोई भी पूर्ण-चक्र एलसीजी, जब m, 2 की घात है, विकल्पतः विषम और सम परिणाम देगा। | ||
गैर- | गैर-गूढ़ालेखी अनुप्रयोगों में उपयुक्तता के लिए एलसीजी का बहुत सावधानी से मानांकन किया जाना चाहिए जहां उच्च गुणवत्ता वाली यादृच्छिकता महत्वपूर्ण है। मोंटे कार्लो अनुकरण के लिए, एक एलसीजी को आवश्यक यादृच्छिक प्रतिदर्शों की संख्या के घन से अधिक और अधिमानतः बहुत अधिक मापांक का उपयोग करना चाहिए। इसका अर्थ है, उदाहरण के लिए, कि एक (अच्छा) 32-बिट एलसीजी का उपयोग लगभग एक हजार यादृच्छिक संख्याएँ प्राप्त करने के लिए किया जा सकता है; 64-बिट एलसीजी लगभग 2<sup>21</sup> यादृच्छिक प्रतिदर्शों (दो मिलियन से थोड़ा अधिक) आदि के लिए अच्छा है। इस कारण से, व्यवहार में एलसीजी बड़े पैमाने पर मोंटे कार्लो अनुकरण के लिए उपयुक्त नहीं हैं। | ||
== | == प्रतिदर्श कोड == | ||
===पायथन कोड=== | ===पायथन कोड=== | ||
[[ जेनरेटर (कंप्यूटर प्रोग्रामिंग) ]] के रूप में, [[पायथन (प्रोग्रामिंग भाषा)]] में एलसीजी का कार्यान्वयन निम्नलिखित है: | [[ जेनरेटर (कंप्यूटर प्रोग्रामिंग) | जनक]] के रूप में, [[पायथन (प्रोग्रामिंग भाषा)|पायथन]] में एलसीजी का कार्यान्वयन निम्नलिखित है: | ||
<syntaxhighlight lang="python"> | <syntaxhighlight lang="python"> | ||
Line 237: | Line 245: | ||
=== | ===मुक्त पास्कल=== | ||
[[ मुफ़्त पास्कल ]] अपने | [[ मुफ़्त पास्कल | मुक्त पास्कल]] अपने व्यतिक्रम कूट यादृच्छिक संख्या जनक के रूप में [[मेरसेन ट्विस्टर]] का उपयोग करता है जबकि डेल्फ़ी एलसीजी का उपयोग करता है। उपरोक्त तालिका में दी गई सूचना के आधार पर यहां मुक्त पास्कल में डेल्फ़ी संगत उदाहरण दिया गया है। समान रैंडसीड मान को देखते हुए यह डेल्फ़ी के समान यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है। | ||
<syntaxhighlight lang="pascal"> | <syntaxhighlight lang="pascal"> | ||
Line 264: | Line 272: | ||
Result := IM * range shr 32; | Result := IM * range shr 32; | ||
end;</syntaxhighlight> | end;</syntaxhighlight> | ||
सभी | सभी कूट-यादृच्छिक संख्या जनकों की तरह, एक एलसीजी को प्रत्येक बार एक नयी संख्या उत्पन्न करने पर स्थिति को संग्रहीत करने और इसे परिवर्तित करने की आवश्यकता होती है। एकाधिक क्रम एक साथ इस स्थिति तक पहुंच सकते हैं, जिससे रेस की स्थिति उत्पन्न हो सकती है। कार्यान्वयन को एक साथ निष्पादित क्रम पर यादृच्छिक संख्याओं के समान अनुक्रम से बचने के लिए अलग-अलग क्रम के लिए अद्वितीय आरंभीकरण के साथ अलग-अलग स्थिति का उपयोग करना चाहिए। | ||
==एलसीजी | ==एलसीजी व्युत्पन्न == | ||
ऐसे कई | ऐसे कई जनक हैं जो एक अलग रूप में रैखिक सर्वांगसम जनक हैं और इस प्रकार एलसीजी का विश्लेषण करने के लिए उपयोग की जाने वाली प्रविधियों को उन पर अनुप्रयुक्त किया जा सकता है। | ||
दीर्घ अवधि के उत्पादन की एक विधि विभिन्न अवधियों के कई एलसीजी के आउटपुट को योग करना है जिसमें एक बड़ा कम-से-कम सामान्य गुणक होता है; विचमैन-हिल जनक इस रूप का एक उदाहरण है। हम चाहेंगे कि वे पूर्णतया से सहअभाज्य हों, परन्तु एक अभाज्य मापांक एक सम अवधि को दर्शाता है, इसलिए कम-से-कम 2 का एक सामान्य गुणनखंड होना चाहिए। इसे मापांक के बराबर एकल एलसीजी के बराबर दर्शाया जा सकता है घटक एलसीजी मॉड्यूलि का उत्पाद है। | |||
जॉर्ज मार्साग्लिया | जॉर्ज मार्साग्लिया की ऋणी के साथ जोड़ें और घटाव के साथ पश्चांक पीआरएनजी, शब्द आकार ''b''=2<sup>''w''</sup> और पश्चता r और s (r > s) के साथ ''b<sup>r</sup>'' ± ''b<sup>s</sup>'' ± 1 के मापांक के साथ एलसीजी के बराबर हैं।<ref>{{cite conference | ||
|title=On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators | |title=On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators | ||
|first1=Shu |last1=Tezuka |first2=Pierre |last2=L'Ecuyer | |first1=Shu |last1=Tezuka |first2=Pierre |last2=L'Ecuyer | ||
Line 285: | Line 293: | ||
|date=December 1992 |pages=443–447 | |date=December 1992 |pages=443–447 | ||
}}</ref> | }}</ref> | ||
एक [[क्रमपरिवर्तित सर्वांगसम जनरेटर]] 2- | a के गुणक के साथ [[गुणन-के-साथ-ले जाना|गुणन]] के साथ ऋणी पीआरएनजी, ''ab<sup>r</sup>''−1 के बड़े अभाज्य मापांक और 2 की घात, गुणक b के साथ एलसीजी के बराबर हैं। | ||
एक [[क्रमपरिवर्तित सर्वांगसम जनरेटर|क्रमपरिवर्तित सर्वांगसम जनक]] 2-मापांक एलसीजी की घात से प्रारंभ होता है और कम-अनुक्रम बिट्स में छोटी अवधि की समस्या को दूर करने के लिए आउटपुट परिवर्तन अनुप्रयुक्त करता है। | |||
==अन्य पीआरएनजी के साथ तुलना== | ==अन्य पीआरएनजी के साथ तुलना== | ||
दीर्घ अवधि के कूट यादृच्छिक अनुक्रम प्राप्त करने के लिए व्यापक रूप से उपयोग किया जाने वाला अन्य प्राथमिक रैखिक-प्रतिक्रिया विस्थापन पंजी निर्माण है, जो जीएफ (2) [x] में अंकगणित पर आधारित है, जो जीएफ (2) पर बहुपद वलय है। पूर्णांक जोड़ और गुणा के बजाय, मूल संचालन अनन्य-या और कम-ऋणी गुणा होते हैं, जिन्हें सामान्यतः [[तार्किक बदलाव|तार्किक परिवर्तनों]] के अनुक्रम के रूप में कार्यान्वित किया जाता है। इनका लाभ यह है कि उनके सभी बिट पूर्ण-अवधि वाले हैं; वे निम्न-क्रम बिट्स में दुर्बलता से प्रभावित नहीं हैं जो अंकगणित मापांक 2<sup>''k''</sup> को त्रस्त करती है। <ref>{{cite book |first=Neil |last=Gershenfeld |author-link=Neil Gershenfeld |title=गणितीय मॉडलिंग की प्रकृति|url=https://archive.org/details/naturemathematic00gers_334 |url-access=limited |edition=First |publisher=Cambridge University Press |year=1999 |isbn=978-0-521-57095-4 |chapter=Section 5.3.2: Linear Feedback |page=[https://archive.org/details/naturemathematic00gers_334/page/n64 59]}}</ref> | |||
इस वर्ग के उदाहरणों में [[ xorshift |एक्सोरशिफ्ट]] जनक और [[मेरसेन ट्विस्टर]] सम्मिलित हैं। उत्तरार्द्ध एक बहुत दीर्घ अवधि (2<sup>19937</sup>−1) प्रदान करता है और विविधतापूर्ण एकरूपता प्रदान करता है, परन्तु यह कुछ सांख्यिकीय परीक्षणों में विफल रहता है।<ref>{{cite journal |last1=Matsumoto |first1=Makoto |first2=Takuji |last2=Nishimura |date=January 1998 |journal=ACM Transactions on Modeling and Computer Simulation |volume=8 |issue=1 |pages=3–30 |title=Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator |doi=10.1145/272991.272995 |url=https://pdfs.semanticscholar.org/098d/5792ffa43e9885f9fc644ffdd7b6a59b0922.pdf |archive-url=https://web.archive.org/web/20171107004909/https://pdfs.semanticscholar.org/098d/5792ffa43e9885f9fc644ffdd7b6a59b0922.pdf |url-status=dead |archive-date=2017-11-07 |citeseerx=10.1.1.215.1141 |s2cid=3332028 }}</ref> [[विलंबित फाइबोनैचि जनरेटर|विलंबित फाइबोनैचि जनक]] भी इसी श्रेणी में आते हैं; यद्यपि वे अंकगणितीय जोड़ का उपयोग करते हैं, उनकी अवधि सबसे कम महत्वपूर्ण बिट्स में से एक एलएफएसआर द्वारा सुनिश्चित की जाती है। | |||
उचित परीक्षणों के साथ रैखिक-प्रतिक्रिया विस्थापन पंजी की संरचना का पता लगाना सरल है<ref name="rfc4086">{{cite IETF |rfc=4086 |bcp=106 |title=सुरक्षा के लिए यादृच्छिकता आवश्यकताएँ|section=6.1.3 |sectionname=Traditional Pseudo-random Sequences |first1=Donald E. 3rd |last1=Eastlake |first2=Jeffrey I. |last2=Schiller |first3=Steve |last3=Crocker |date=June 2005 |publisher=[[Internet Engineering Task Force|IETF]]}}</ref> जैसे कि परीक्षणयू01 समूह में कार्यान्वित रैखिक जटिलता परीक्षण; एलएफएसआर के लगातार बिट्स से आरंभ किए गए एक बूलियन [[मैट्रिक्स का चक्कर लगाना|परिचालित आव्यूह]] की श्रेणी कभी भी बहुपद की डिग्री से अधिक नहीं होगी। एक गैर-रेखीय आउटपुट मिश्रित फलन (जैसे कि एक्सओशिरो256** और क्रमबद्ध सर्वांगसम जनक निर्माण में) जोड़ने से सांख्यिकीय परीक्षणों पर प्रदर्शन में काफी सुधार हो सकता है। | |||
पीआरएनजी के लिए एक अन्य संरचना एक बहुत ही सरल पुनरावृत्ति फलन है जो एक शक्तिशाली आउटपुट मिश्रित फलन के साथ संयुक्त है। इसमें [[काउंटर मोड|गुणक प्रणाली]] खंड आद्यक्षर और गैर-गूढ़ालेखी जनक जैसे [http://prng.di.unimi.it/splitmix64.c स्प्लिटमिक्स64] सम्मिलित हैं। | |||
उच्च-गुणवत्ता वाली | एलसीजी के समान एक संरचना, परन्तु समतुल्य नहीं, बहु-पुनरावर्ती जनक: ''X<sub>n</sub>'' = (''a''<sub>1</sub>''X<sub>n</sub>''<sub>−1</sub> + ''a''<sub>2</sub>''X<sub>n</sub>''<sub>−2</sub> + ··· + ''a<sub>k</sub>X<sub>n</sub>''<sub>−''k''</sub>), k ≥ 2 के लिए मॉड m है। एक प्रमुख मापांक के साथ, यह हो सकता है, ''m<sup>k</sup>''−1 तक की अवधि उत्पन्न कर सकता है, इसलिए यह बड़ी अवधियों के लिए एलसीजी संरचना का एक उपयोगी विस्तार है। | ||
उच्च-गुणवत्ता वाली कूट यादृच्छिक संख्याएँ उत्पन्न करने की एक शक्तिशाली प्रविधि विभिन्न संरचना के दो या दो से अधिक पीआरएनजी को संयोजित करना है; एक एलएफएसआर और एक एलसीजी का योग (जैसा कि केआईएसएस या एक्सोरवॉव निर्माण में होता है) गति में कुछ लागत पर बहुत अच्छा प्रदर्शन कर सकता है। | |||
==यह भी देखें== | ==यह भी देखें== | ||
* [[यादृच्छिक संख्या जनरेटरों की सूची]] - | * [[यादृच्छिक संख्या जनरेटरों की सूची|यादृच्छिक संख्या जनकों की सूची]] - श्रेष्ठतर सांख्यिकीय गुणवत्ता वाले कुछ सहित अन्य पीआरएनजी | ||
* [[ACORN (PRNG)]] - | * [[ACORN (PRNG)|एसीओआरएन (पीआरएनजी)]] - एसीजी के साथ भ्रमित न हों, ऐसा प्रतीत होता है कि यह शब्द एलसीजी और एलएफएसआर जनक के भिन्नरूप के लिए उपयोग किया गया है। | ||
* क्रमपरिवर्तित सर्वांगसम | * क्रमपरिवर्तित सर्वांगसम जनक | ||
* [[पूरा चक्र]] | * [[पूरा चक्र|सम्पूर्ण चक्र]] | ||
* [[व्युत्क्रम सर्वांगसम जनरेटर]] | * [[व्युत्क्रम सर्वांगसम जनरेटर|व्युत्क्रम सर्वांगसम जनक]] | ||
* गुणन-के-साथ- | * गुणन-के-साथ-ऋणी | ||
* लेहमर आरएनजी (कभी-कभी पार्क-मिलर आरएनजी भी कहा जाता है) | * लेहमर आरएनजी (कभी-कभी पार्क-मिलर आरएनजी भी कहा जाता है) | ||
* [[संयुक्त रैखिक सर्वांगसम जनरेटर]] | * [[संयुक्त रैखिक सर्वांगसम जनरेटर|संयुक्त रैखिक सर्वांगसम जनक]] | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
Line 355: | Line 365: | ||
* [https://web.archive.org/web/20150616223328/http://yurichev.com/blog/modulo/ Article about another way of cracking LCG] | * [https://web.archive.org/web/20150616223328/http://yurichev.com/blog/modulo/ Article about another way of cracking LCG] | ||
{{DEFAULTSORT:Linear Congruential Generator}} | {{DEFAULTSORT:Linear Congruential Generator}} | ||
[[Category: | [[Category:All articles needing additional references|Linear Congruential Generator]] | ||
[[Category:Created On 30/06/2023]] | [[Category:All articles with unsourced statements|Linear Congruential Generator]] | ||
[[Category:Articles needing additional references from जुलाई 2021|Linear Congruential Generator]] | |||
[[Category:Articles with hatnote templates targeting a nonexistent page|Linear Congruential Generator]] | |||
[[Category:Articles with invalid date parameter in template|Linear Congruential Generator]] | |||
[[Category:Articles with unsourced statements from November 2017|Linear Congruential Generator]] | |||
[[Category:Created On 30/06/2023|Linear Congruential Generator]] | |||
[[Category:Lua-based templates|Linear Congruential Generator]] | |||
[[Category:Machine Translated Page|Linear Congruential Generator]] | |||
[[Category:Pages with script errors|Linear Congruential Generator]] | |||
[[Category:Templates Vigyan Ready|Linear Congruential Generator]] | |||
[[Category:Templates that add a tracking category|Linear Congruential Generator]] | |||
[[Category:Templates that generate short descriptions|Linear Congruential Generator]] | |||
[[Category:Templates using TemplateData|Linear Congruential Generator]] | |||
[[Category:उदाहरण के लिए पायथन (प्रोग्रामिंग भाषा) कोड वाले लेख|Linear Congruential Generator]] | |||
[[Category:छद्म यादृच्छिक संख्या जनरेटर|Linear Congruential Generator]] | |||
[[Category:मॉड्यूलर अंकगणित|Linear Congruential Generator]] |
Latest revision as of 15:43, 10 November 2023

एक रैखिक सर्वांगसम जनक (LCG) एक कलन विधि है जो एक असंतत खंडशः रैखिक समीकरण के साथ गणना की गई कूट-यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है। यह विधि सबसे पुराने और सबसे प्रसिद्ध कूट यादृच्छिक संख्या जनक कलन विधि में से एक का प्रतिनिधित्व करती है। उनके पीछे के सिद्धांत को समझना अपेक्षाकृत सरल है, और उन्हें सरलता से और तीव्रता से अनुप्रयुक्त किया जाता है, विशेषकर परिकलक हार्डवेयर पर जो भंडारण-बिट खंडन द्वारा प्रमापीय अंकगणित प्रदान कर सकता है।
जनक को पुनरावृत्ति संबंध द्वारा परिभाषित किया गया है:
जहाँ कूट-यादृच्छिक मानों का क्रम है, और
- - "मापांक"
- - "गुणक"
- - "वृद्धि"
- - "मूल" या "प्रारंभ मान"
पूर्णांक स्थिरांक हैं जो जनक को निर्दिष्ट करते हैं। यदि c = 0 है, तो जनक को प्रायः गुणक सर्वांगसम जनक (MCG), या लेहमर आरएनजी कहा जाता है। यदि c ≠ 0 है, तो विधि को मिश्रित सर्वांगसम जनक कहा जाता है।[1]: 4-
जब c ≠ 0, एक गणितज्ञ पुनरावृत्ति को एक रैखिक परिवर्तन नहीं, बल्कि एक सजातीय परिवर्तन कहेगा, परन्तु परिकलक विज्ञान में यह मिथ्या नाम अच्छी तरह से स्थापित है।[2]: 1
इतिहास
लेहमर जनक 1951 में प्रकाशित हुआ था[3] और रैखिक सर्वांगसम जनक 1958 में डब्ल्यू. ई. थॉमसन और ए. रोटेनबर्ग द्वारा प्रकाशित किया गया था।[4][5]
अवधि
एलसीजी का एक लाभ यह है कि मापदंडों के उचित चयन से एक ऐसी अवधि प्राप्त होती है जो ज्ञात और दीर्घ दोनों होती है। हालांकि यह एकमात्र मानदंड नहीं है, बहुत छोटी अवधि कूट-यादृच्छिक संख्या जनक में एक घातक दोष है।[6]
जबकि एलसीजी कूट-यादृच्छिक संख्याएं उत्पन्न करने में सक्षम हैं जो यादृच्छिकता के लिए औपचारिक परीक्षण पारित कर सकते हैं, आउटपुट की गुणवत्ता मापदण्ड m और a के चयन के प्रति अत्यधिक संवेदनशील है।[7][1][8][9][10][2] उदाहरण के लिए, a = 1 और c = 1 एक साधारण मापांक-m गुणक का निर्माण करता है, जिसकी दीर्घ अवधि होती है, परन्तु यह स्पष्ट रूप से गैर-यादृच्छिक है।
ऐतिहासिक रूप से, खराब विकल्पों के कारण एलसीजी का कार्यान्वयन अप्रभावी हो गया है। इसका एक विशेष उदाहरण आरएएनडीयू है, जिसका 1970 के दशक के प्रारंभ में व्यापक रूप से उपयोग किया गया था और इसके कई परिणाम सामने आए थे, जिन पर वर्तमान में इस खराब एलसीजी के उपयोग के कारण प्रश्न उठाए जा रहे हैं।[11]
मापदण्ड चयन के तीन सामान्य वर्ग हैं:
m अभाज्य, c = 0
यह मूल लेहमर आरएनजी निर्माण है। यदि गुणक a को पूर्णांक गुणांक m का एक पूर्वग अवयव चुना जाता है, तो अवधि m−1 है। प्रारंभिक अवस्था को 1 और m−1 के मध्य चुना जाना चाहिए।
अभाज्य गुणांक की एक हानि यह है कि प्रमापीय कमी के लिए दोगुनी-चौड़ाई वाले उत्पाद और एक स्पष्ट न्यूनीकरण चरण की आवश्यकता होती है। प्रायः 2 की घात से कम अभाज्य का उपयोग किया जाता है (मेरसेन अभाज्य 231−1 और 261−1 लोकप्रिय हैं), ताकि न्यूनीकरण मापांक m = 2e − d की गणना (ax मॉड 2) + d ⌊ax/2e⌋ के रूप में की जा सके। यदि परिणाम बहुत बड़ा है तो इसके बाद m का सशर्त घटाव होना चाहिए, परन्तु घटाव की संख्या ad/m तक सीमित है, जिसे d छोटा होने पर सरलता से एक तक सीमित किया जा सकता है।
यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है और गुणक को सावधानी से चुना गया है, तो श्रेज की विधि[12] का उपयोग किया जा सकता है। ऐसा करने के लिए, कारक m = qa+r, अर्थात q = ⌊m/a⌋ और r = m मॉड a है। फिर ax मॉड m = a(x mod q) − r⌊x/q⌋ की गणना करें। चूँकि x मॉड q < q ≤ m/a, पहला पद am/a = m से बिल्कुल कम है। यदि a को इस प्रकार चुना जाता है कि r ≤ q (और इस प्रकार r/q ≤ 1), तो दूसरा पद भी m से कम r⌊x/q⌋ ≤ rx/q = x(r/q) ≤ x < m है। इस प्रकार, दोनों उत्पादों की गणना एक एकल-चौड़ाई वाले उत्पाद के साथ की जा सकती है और उनके मध्य का अंतर [1−m, m−1] की सीमा में है, इसलिए एकल सशर्त जोड़ के साथ इसे [0, m−1] तक कम किया जा सकता है।[13]
दूसरी हानि यह है कि मान 1 ≤ x < m को समान यादृच्छिक बिट्स में परिवर्तित करना अनुपयुक्त है। यदि 2 की घात से कम अभाज्य का उपयोग किया जाता है, तो कभी-कभी लुप्त मानों को सरलता से उपेक्षित कर दिया जाता है।
m 2 की घात, c = 0
m को 2 की घात के रूप में चुनना, प्रायः m = 232 या m = 264, एक विशेष रूप से कुशल एलसीजी उत्पन्न करता है, क्योंकि यह केवल द्विचर प्रतिनिधित्व को छोटा करके मापांक संचालन की गणना करने की अनुमति देता है। वास्तव में, सबसे महत्वपूर्ण बिट्स की सामान्यतः गणना ही नहीं की जाती है। हालाँकि, इसकी हानि भी हैं।
इस विधि में अधिकतम अवधि m/4 है, जो a ≡ 3 या a ≡ 5 (मॉड 8) होने पर प्राप्त होती है। प्रारंभिक अवस्था X0 विषम होना चाहिए और X के निम्न तीन बिट दो स्थितियों के मध्य वैकल्पिक होते हैं और उपयोगी नहीं होते हैं। यह दर्शाया जा सकता है कि यह विधि एक जनक के बराबर है जिसका मापांक एक चौथाई आकार और c ≠ 0 है।[1]
2 की घात के मापांक के उपयोग के साथ एक अधिक जटिल विवाद यह है कि कम बिट्स की अवधि उच्च बिट्स की तुलना में कम होती है। X का निम्नतम क्रम वाला बिट कभी परिवर्तित नहीं होता है (X सदैव विषम होता है) और अगले दो बिट दो स्थितियों के मध्य वैकल्पिक होते हैं। यदि a≡5 (मॉड 8) है, तो बिट 1 कभी परिवर्तित नहीं होता है और बिट 2 परिवर्तित होता है। यदि a≡3 (मॉड 8) है, तो बिट 2 कभी परिवर्तित नहीं होता है और बिट 1 परिवर्तित होता है। बिट 3, 4 की अवधि के साथ दोहराता है, बिट 4 का आवर्त 8 है, इत्यादि। केवल X का सबसे महत्वपूर्ण बिट ही पूर्ण अवधि प्राप्त करता है।
c ≠ 0
जब c ≠ 0, सही ढंग से चुने गए मापदण्ड सभी मूल मानों के लिए m के बराबर अवधि की अनुमति देते हैं। यह तब घटित होगा जब और केवल यदि:[1]: 17—19
- और सहअभाज्य पूर्णांक हैं,
- के सभी अभाज्य गुणनखंडों से विभाज्य है,
- 4 से विभाज्य है यदि , 4 से विभाज्य है।
इन तीन आवश्यकताओं को हल-डोबेल प्रमेय के रूप में जाना जाता है।[14][15]
इस विधि का उपयोग किसी भी m के साथ किया जा सकता है, परन्तु यह केवल m के लिए कई दोहराए गए अभाज्य कारकों के साथ ही अच्छा कार्य करता है, जैसे कि 2 की घात; परिकलक के शब्द आकार का उपयोग करना सबसे सामान्य विकल्प है। यदि m एक वर्ग-मुक्त पूर्णांक होता, तो यह केवल ≡ 1 (मॉड m) की अनुमति देता, जो बहुत खराब पीआरएनजी बनाता है; संभावित पूर्ण-अवधि गुणकों का चयन केवल तभी उपलब्ध होता है जब m में अभाज्य गुणनखंड दोहराए जाते हैं।
यद्यपि हल-डोबेल प्रमेय अधिकतम अवधि प्रदान करता है, यह एक अच्छे जनक की प्रत्याभूति देने के लिए पर्याप्त नहीं है। उदाहरण के लिए, यह वांछनीय है कि a − 1, m के अभाज्य गुणनखंडों द्वारा आवश्यकता से अधिक विभाज्य न हो। इस प्रकार, यदि m, 2 की घात है, तो a − 1 को 4 से विभाज्य होना चाहिए, परन्तु 8 से विभाज्य नहीं होना चाहिए, अर्थात a ≡ 5 (मॉड 8)।[1]: §3.2.1.3
वास्तव में, अधिकांश गुणक एक अनुक्रम उत्पन्न करते हैं जो गैर-यादृच्छिकता या किसी अन्य के लिए एक परीक्षण में विफल रहता है, और एक ऐसा गुणक ढूंढता है जो सभी अनुप्रयुक्त मानदंडों के लिए संतोषजनक हो,[1]: §3.3.3 काफी चुनौतीपूर्ण है। वर्णक्रमीय परीक्षण सबसे महत्वपूर्ण परीक्षणों में से एक है।[16]
ध्यान दें कि 2 की घात के मापांक c = 0 के लिए ऊपर वर्णित समस्या को साझा करता है: निम्न k बिट्स मापांक 2k के साथ एक जनक बनाते हैं और इस प्रकार 2k की अवधि के साथ दोहराते हैं; केवल सबसे महत्वपूर्ण बिट ही पूर्ण अवधि को प्राप्त करता है। यदि r से कम कूट-यादृच्छिक संख्या वांछित है, ⌊rX/m⌋ X मॉड r की तुलना में बहुत उच्च गुणवत्ता वाला परिणाम है। दुर्भाग्य से, अधिकांश क्रमादेश भाषाएँ बाद वाले (X % r
) को लिखना बहुत सरल बना देती हैं, इसलिए यह अधिक सामान्यतः उपयोग की जाने वाली विधि है।
जनक c के चयन के प्रति संवेदनशील नहीं है, जब तक कि यह मापांक के लिए अपेक्षाकृत प्रमुख है (उदाहरण के लिए यदि m 2 की घात है, तो c विषम होना चाहिए), इसलिए मान c=1 सामान्यतः चुना जाता है।
C के अन्य विकल्पों द्वारा निर्मित श्रृंखला को श्रृंखला के एक सामान्य फलन के रूप में लिखा जा सकता है जब c=1 है।[1]: 11 विशेष रूप से, यदि Y, Y0 = 0 और Yn+1 = aYn+1 मॉड m द्वारा परिभाषित प्रोटोटाइप श्रृंखला है, तो एक सामान्य श्रृंखला Xn+1 = Xn+c मॉड m को Y के एफ़िन फलन के रूप में लिखा जा सकता है:
अधिक सामान्यतः, समान गुणक और मापांक वाली किन्हीं दो श्रृंखलाओं X और Z से संबंधित हैं।
सामान्य उपयोग में मापदण्ड
निम्न तालिका सामान्य उपयोग में एलसीजी के मापदंडों को सूचीबद्ध करती है, जिसमें विभिन्न संकलकों के कार्यावधि पुस्तकालयों में अंतर्निहित रैंड () फलन सम्मिलित हैं। यह तालिका लोकप्रियता दर्शाने के लिए है, अनुकरण करने के लिए उदाहरण नहीं; इनमें से कई मापदण्ड ख़राब हैं। अच्छे मापदंडों की तालिकाएँ उपलब्ध हैं।[10][2]
स्रोत | गुणांक m |
गुणक a |
वृद्धि c |
रैंड () या रैंडम (L) में मूल के आउटपुट बिट्स |
---|---|---|---|---|
जेडएक्स81 | 216 + 1 | 75 | 74 | |
"त्वरित और ख़राब जनक" सूची से संख्यात्मक व्यंजन ,
अध्याय 7.1, समीकरण- 7.1.6 |
232 | 1664525 | 1013904223 | |
बोरलैंड सी/सी++ | 232 | 22695477 | 1 | रैंड() में बिट्स 30..16, लैरैंड() में 30..0 |
ग्लिबीसी (जीसीसी द्वारा प्रयुक्त)[17] | 231 | 1103515245 | 12345 | बिट्स 30..0 |
एएनएसआई सी: वाटकॉम, डिजिटल मार्स, कोडवॉरियर, आईबीएम विजुअलएज सी/सी++[18] सी90, सी99, सी11: आईएसओ/आईईसी 9899 में सुझाव,[19] सी17 |
231 | 1103515245 | 12345 | बिट्स 30..16 |
बोरलैंड डेल्फ़ी, वास्तविक पास्कल | 232 | 134775813 | 1 | बिट्स 63..32 of (मूल × L) |
टर्बो पास्कल | 232 | 134775813 (808840516) | 1 | |
माइक्रोसॉफ्ट दृश्य/क्विक सी/सी++ | 232 | 214013 (343एफडी16) | 2531011 (269ईसी316) | बिट्स 30..16 |
माइक्रोसॉफ्ट मूल दृश्य (6 और पूर्व)[20] | 224 | 1140671485 (43एफडी43एफडी16) | 12820163 (सी39ईसी316) | |
नेटिव एपीआई से आरटीएलयूनिफ़ॉर्म[21] | 231 − 1 | 2147483629 (7एफएफएफएफएफईडी16) | 2147483587 (7एफएफएफएफएफसी316) | |
एप्पल कार्बनलिब, सी++11 का minstd_rand0 ,[22] एमएटीएलएबी का वी4 लीगेसी जनक एमसीजी16807[23] |
231 − 1 | 16807 | 0 | एमआईएनएसटीडी देखें |
सी++11 का minstd_rand [22] |
231 − 1 | 48271 | 0 | एमआईएनएसटीडी देखें |
डोनाल्ड नुथ द्वारा एमएमआईएक्स | 264 | 6364136223846793005 | 1442695040888963407 | |
न्यूलिब | 264 | 6364136223846793005 | 1 | बिट्स 62..32 (16-बिट इंट के लिए 46..32) |
मसल | 264 | 6364136223846793005 | 1 | बिट्स 63..33 |
वीएमएस का एमटीएच$आरएएनडीओएम,[24] ग्लिबीसी का पुराना संस्करण | 232 | 69069 (10डीसीडी16) | 1 | |
जावा का जावा.यूटिल.रैन्डम, पीओएसआईएक्स [ln]रैंड48, ग्लिबीसी [ln]रैंड 48[_r] | 248 | 25214903917 (5डीईसीई66डी16) | 11 | बिट्स 47..16 |
134456 = 2375 | 8121 | 28411 | ||
पीओएसआईएक्स[30] [jm]रैंड48, ग्लिबीसी [mj]रैंड48[_r] | 248 | 25214903917 (5डीईसीई66डी16) | 11 | बिट्स 47..15 |
पीओएसआईएक्स [de]रैंड48, ग्लिबीसी [de]रैंड48[_r] | 248 | 25214903917 (5डीईसीई66डी16) | 11 | बिट्स 47..0 |
सीसी65[31] | 223 | 65793 (1010116) | 4282663 (41592716) | बिट्स 22..8 |
सीसी65 | 232 | 16843009 (101010116) | 826366247 (3141592716) | बिट्स 31..16 |
सीसी65 | 232 | 16843009 (101010116) | 3014898611 (बी3बी3बी3बी316) | पहले के बिट्स 31..16, वर्तमान बिट्स 31..16 एक्सऑर बिट्स 14..0 |
पूर्व में सामान्य: आरएएनडीयू[11] | 231 | 65539 | 0 |
जैसा कि ऊपर दर्शाया गया है, एलसीजी सदैव अपने द्वारा उत्पादित मानों में सभी बिट्स का उपयोग नहीं करते हैं। उदाहरण के लिए, जावा कार्यान्वयन प्रत्येक पुनरावृत्ति पर 48-बिट मानों के साथ संचालित होता है, परन्तु केवल उनके 32 सबसे महत्वपूर्ण बिट्स लौटाता है। ऐसा इसलिए है क्योंकि उच्च-क्रम वाले बिट्स की अवधि निचले-क्रम वाले बिट्स की तुलना में लंबी होती है (नीचे देखें)। एलसीजी जो इस खंडन प्रविधि का उपयोग करते हैं, वे उन लोगों की तुलना में सांख्यिकीय रूप से श्रेष्ठतर मान उत्पन्न करते हैं जो ऐसा नहीं करते हैं। यह उन आलेखों में विशेष रूप से ध्यान देने योग्य है जो पंक्ति श्रृंखला को कम करने के लिए मॉड संक्रिया का उपयोग करते हैं; यादृच्छिक संख्या मॉड 2 को संशोधित करने से बिना किसी खंडन के 0 और 1 को वैकल्पिक किया जा सकेगा।
लाभ और हानि
This section needs additional citations for verification. (जुलाई 2021) (Learn how and when to remove this template message) |
एलसीजी तीव्र हैं और स्थिति को बनाए रखने के लिए न्यूनतम मेमोरी (एक मापांक-m संख्या, प्रायः 32 या 64 बिट्स) की आवश्यकता होती है। यह उन्हें कई स्वतंत्र धाराओं के अनुकरण के लिए मूल्यवान बनाता है। गूढ़लेखिकी अनुप्रयोगों के लिए एलसीजी का उद्दिष्ट नहीं है और इसका उपयोग नहीं किया जाना चाहिए; ऐसे अनुप्रयोगों के लिए गूढ़लेखिकी रूप से सुरक्षित कूट यादृच्छिक संख्या जनक का उपयोग करें।

हालाँकि एलसीजी में कुछ विशिष्ट दोष हैं, परन्तु उनकी कई खामियाँ बहुत छोटी स्थिति के कारण आती हैं। तथ्य यह है कि लोगों को इतने सालों से ऐसे छोटे गुणांक के साथ उपयोग करने के लिए प्रेरित किया गया है, इसे प्रविधि के गुण के प्रमाण के रूप में देखा जा सकता है। पर्याप्त बड़े अवस्था वाले एलसीजी कड़े सांख्यिकीय परीक्षणों को भी पारित कर सकता है; एक मापांक-2 एलसीजी जो उच्च 32 बिट्स लौटाता है, परीक्षणयू01 के छोटे क्रश समूह से गुजरता है,[citation needed] और 96-बिट एलसीजी सबसे कड़े बड़े क्रश समूह से गुजरता है।[32]
एक विशिष्ट उदाहरण के लिए, 32 बिट आउटपुट के साथ एक आदर्श यादृच्छिक संख्या जनक से (बर्थ्डै प्रमेय के अनुसार) √m ≈ 216 परिणामों के बाद पहले के आउटपुट को अनुलिपि करना, प्रारंभ करने की आशा की जाती है। कोई भी पीआरएनजी जिसका आउटपुट उसकी पूर्ण, असंतुलित स्थिति है, तब तक अनुलिपि उत्पन्न नहीं करेगा जब तक कि उसकी सम्पूर्ण अवधि समाप्त न हो जाए, यह एक सरलता से पता लगाने योग्य सांख्यिकीय दोष है। संबंधित कारणों से, किसी भी पीआरएनजी की अवधि आवश्यक आउटपुट की संख्या के वर्ग से अधिक होनी चाहिए। आधुनिक परिकलक गति को देखते हुए, इसका अर्थ है कि कम से कम मांग वाले अनुप्रयोगों को छोड़कर सभी के लिए 264 की अवधि, और मांग वाले अनुकरण के लिए दीर्घ अवधि है।
एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि n-आयामी समष्टि में बिंदुओं को चुनने के लिए उपयोग किया जाता है, तो बिंदु अधिक-से-अधिक, n√n!⋅m अधिसमतल (मार्सग्लिया का प्रमेय, जॉर्ज मार्साग्लिया द्वारा विकसित) पर स्थित होंगे।[7] यह अनुक्रम Xn के क्रमिक मानों के मध्य क्रमिक सहसंबंध के कारण है। असावधानतः चुने गए गुणकों में सामान्यतः बहुत कम, व्यापक दूरी वाले विमान होंगे, जिससे समस्याएं उत्पन्न हो सकती हैं। वर्णक्रमीय परीक्षण, जो एलसीजी की गुणवत्ता का एक सरल परीक्षण है, इस अंतर को मापता है और एक अच्छे गुणक को चुनने की अनुमति देता है।
समतल अंतर मापांक और गुणक दोनों पर निर्भर करता है। एक बड़ा पर्याप्त मापांक इस दूरी को दोहरे परिशुद्धता संख्याओं के खंडन से कम कर सकता है। मापांक बड़ा होने पर गुणक का चुनाव कम महत्वपूर्ण हो जाता है। वर्णक्रमीय सूचकांक की गणना करना और यह सुनिश्चित करना अभी भी आवश्यक है कि गुणक खराब नहीं है, परन्तु विशुद्ध रूप से संभाव्य रूप से जब मापांक लगभग 264 से बड़ा होता है तो खराब गुणक का सामना करना अत्यधिक असंभव हो जाता है।
एलसीजी के लिए विशिष्ट एक और दोष निम्न-अनुक्रम बिट्स की छोटी अवधि है जब m को 2 की घात के रूप में चुना जाता है। इसे आवश्यक आउटपुट से बड़े मापांक का उपयोग करके और समष्टि के सबसे महत्वपूर्ण बिट्स का उपयोग करके कम किया जा सकता है।
फिर भी, कुछ अनुप्रयोगों के लिए एलसीजी एक अच्छा विकल्प हो सकता है। उदाहरण के लिए, एक सन्निहित प्रणाली में, उपलब्ध मेमोरी की मात्रा प्रायः गंभीर रूप से सीमित होती है। इसी तरह, विडियो गेम कंसोल जैसे वातावरण में एलसीजी की थोड़ी संख्या में उच्च-क्रम बिट्स लेना पर्याप्त हो सकता है। जब m, 2 की घात हो तो एलसीजी के निम्न-क्रम वाले बिट्स पर कभी भी यादृच्छिकता की किसी भी डिग्री के लिए विश्वास नहीं किया जाना चाहिए। निम्न-क्रम वाले बिट्स बहुत छोटे चक्रों से गुजरते हैं। विशेष रूप से, कोई भी पूर्ण-चक्र एलसीजी, जब m, 2 की घात है, विकल्पतः विषम और सम परिणाम देगा।
गैर-गूढ़ालेखी अनुप्रयोगों में उपयुक्तता के लिए एलसीजी का बहुत सावधानी से मानांकन किया जाना चाहिए जहां उच्च गुणवत्ता वाली यादृच्छिकता महत्वपूर्ण है। मोंटे कार्लो अनुकरण के लिए, एक एलसीजी को आवश्यक यादृच्छिक प्रतिदर्शों की संख्या के घन से अधिक और अधिमानतः बहुत अधिक मापांक का उपयोग करना चाहिए। इसका अर्थ है, उदाहरण के लिए, कि एक (अच्छा) 32-बिट एलसीजी का उपयोग लगभग एक हजार यादृच्छिक संख्याएँ प्राप्त करने के लिए किया जा सकता है; 64-बिट एलसीजी लगभग 221 यादृच्छिक प्रतिदर्शों (दो मिलियन से थोड़ा अधिक) आदि के लिए अच्छा है। इस कारण से, व्यवहार में एलसीजी बड़े पैमाने पर मोंटे कार्लो अनुकरण के लिए उपयुक्त नहीं हैं।
प्रतिदर्श कोड
पायथन कोड
जनक के रूप में, पायथन में एलसीजी का कार्यान्वयन निम्नलिखित है:
from collections.abc import Generator
def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]:
"""Linear congruential generator."""
while True:
seed = (a * seed + c) % modulus
yield seed
मुक्त पास्कल
मुक्त पास्कल अपने व्यतिक्रम कूट यादृच्छिक संख्या जनक के रूप में मेरसेन ट्विस्टर का उपयोग करता है जबकि डेल्फ़ी एलसीजी का उपयोग करता है। उपरोक्त तालिका में दी गई सूचना के आधार पर यहां मुक्त पास्कल में डेल्फ़ी संगत उदाहरण दिया गया है। समान रैंडसीड मान को देखते हुए यह डेल्फ़ी के समान यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है।
unit lcg_random;
{$ifdef fpc}{$mode delphi}{$endif}
interface
function LCGRandom: extended; overload; inline;
function LCGRandom(const range:longint): longint; overload; inline;
implementation
function IM: cardinal; inline;
begin
RandSeed := RandSeed * 134775813 + 1;
Result := RandSeed;
end;
function LCGRandom: extended; overload; inline;
begin
Result := IM * 2.32830643653870e-10;
end;
function LCGRandom(const range: longint): longint; overload; inline;
begin
Result := IM * range shr 32;
end;
सभी कूट-यादृच्छिक संख्या जनकों की तरह, एक एलसीजी को प्रत्येक बार एक नयी संख्या उत्पन्न करने पर स्थिति को संग्रहीत करने और इसे परिवर्तित करने की आवश्यकता होती है। एकाधिक क्रम एक साथ इस स्थिति तक पहुंच सकते हैं, जिससे रेस की स्थिति उत्पन्न हो सकती है। कार्यान्वयन को एक साथ निष्पादित क्रम पर यादृच्छिक संख्याओं के समान अनुक्रम से बचने के लिए अलग-अलग क्रम के लिए अद्वितीय आरंभीकरण के साथ अलग-अलग स्थिति का उपयोग करना चाहिए।
एलसीजी व्युत्पन्न
ऐसे कई जनक हैं जो एक अलग रूप में रैखिक सर्वांगसम जनक हैं और इस प्रकार एलसीजी का विश्लेषण करने के लिए उपयोग की जाने वाली प्रविधियों को उन पर अनुप्रयुक्त किया जा सकता है।
दीर्घ अवधि के उत्पादन की एक विधि विभिन्न अवधियों के कई एलसीजी के आउटपुट को योग करना है जिसमें एक बड़ा कम-से-कम सामान्य गुणक होता है; विचमैन-हिल जनक इस रूप का एक उदाहरण है। हम चाहेंगे कि वे पूर्णतया से सहअभाज्य हों, परन्तु एक अभाज्य मापांक एक सम अवधि को दर्शाता है, इसलिए कम-से-कम 2 का एक सामान्य गुणनखंड होना चाहिए। इसे मापांक के बराबर एकल एलसीजी के बराबर दर्शाया जा सकता है घटक एलसीजी मॉड्यूलि का उत्पाद है।
जॉर्ज मार्साग्लिया की ऋणी के साथ जोड़ें और घटाव के साथ पश्चांक पीआरएनजी, शब्द आकार b=2w और पश्चता r और s (r > s) के साथ br ± bs ± 1 के मापांक के साथ एलसीजी के बराबर हैं।[33][34]
a के गुणक के साथ गुणन के साथ ऋणी पीआरएनजी, abr−1 के बड़े अभाज्य मापांक और 2 की घात, गुणक b के साथ एलसीजी के बराबर हैं।
एक क्रमपरिवर्तित सर्वांगसम जनक 2-मापांक एलसीजी की घात से प्रारंभ होता है और कम-अनुक्रम बिट्स में छोटी अवधि की समस्या को दूर करने के लिए आउटपुट परिवर्तन अनुप्रयुक्त करता है।
अन्य पीआरएनजी के साथ तुलना
दीर्घ अवधि के कूट यादृच्छिक अनुक्रम प्राप्त करने के लिए व्यापक रूप से उपयोग किया जाने वाला अन्य प्राथमिक रैखिक-प्रतिक्रिया विस्थापन पंजी निर्माण है, जो जीएफ (2) [x] में अंकगणित पर आधारित है, जो जीएफ (2) पर बहुपद वलय है। पूर्णांक जोड़ और गुणा के बजाय, मूल संचालन अनन्य-या और कम-ऋणी गुणा होते हैं, जिन्हें सामान्यतः तार्किक परिवर्तनों के अनुक्रम के रूप में कार्यान्वित किया जाता है। इनका लाभ यह है कि उनके सभी बिट पूर्ण-अवधि वाले हैं; वे निम्न-क्रम बिट्स में दुर्बलता से प्रभावित नहीं हैं जो अंकगणित मापांक 2k को त्रस्त करती है। [35]
इस वर्ग के उदाहरणों में एक्सोरशिफ्ट जनक और मेरसेन ट्विस्टर सम्मिलित हैं। उत्तरार्द्ध एक बहुत दीर्घ अवधि (219937−1) प्रदान करता है और विविधतापूर्ण एकरूपता प्रदान करता है, परन्तु यह कुछ सांख्यिकीय परीक्षणों में विफल रहता है।[36] विलंबित फाइबोनैचि जनक भी इसी श्रेणी में आते हैं; यद्यपि वे अंकगणितीय जोड़ का उपयोग करते हैं, उनकी अवधि सबसे कम महत्वपूर्ण बिट्स में से एक एलएफएसआर द्वारा सुनिश्चित की जाती है।
उचित परीक्षणों के साथ रैखिक-प्रतिक्रिया विस्थापन पंजी की संरचना का पता लगाना सरल है[37] जैसे कि परीक्षणयू01 समूह में कार्यान्वित रैखिक जटिलता परीक्षण; एलएफएसआर के लगातार बिट्स से आरंभ किए गए एक बूलियन परिचालित आव्यूह की श्रेणी कभी भी बहुपद की डिग्री से अधिक नहीं होगी। एक गैर-रेखीय आउटपुट मिश्रित फलन (जैसे कि एक्सओशिरो256** और क्रमबद्ध सर्वांगसम जनक निर्माण में) जोड़ने से सांख्यिकीय परीक्षणों पर प्रदर्शन में काफी सुधार हो सकता है।
पीआरएनजी के लिए एक अन्य संरचना एक बहुत ही सरल पुनरावृत्ति फलन है जो एक शक्तिशाली आउटपुट मिश्रित फलन के साथ संयुक्त है। इसमें गुणक प्रणाली खंड आद्यक्षर और गैर-गूढ़ालेखी जनक जैसे स्प्लिटमिक्स64 सम्मिलित हैं।
एलसीजी के समान एक संरचना, परन्तु समतुल्य नहीं, बहु-पुनरावर्ती जनक: Xn = (a1Xn−1 + a2Xn−2 + ··· + akXn−k), k ≥ 2 के लिए मॉड m है। एक प्रमुख मापांक के साथ, यह हो सकता है, mk−1 तक की अवधि उत्पन्न कर सकता है, इसलिए यह बड़ी अवधियों के लिए एलसीजी संरचना का एक उपयोगी विस्तार है।
उच्च-गुणवत्ता वाली कूट यादृच्छिक संख्याएँ उत्पन्न करने की एक शक्तिशाली प्रविधि विभिन्न संरचना के दो या दो से अधिक पीआरएनजी को संयोजित करना है; एक एलएफएसआर और एक एलसीजी का योग (जैसा कि केआईएसएस या एक्सोरवॉव निर्माण में होता है) गति में कुछ लागत पर बहुत अच्छा प्रदर्शन कर सकता है।
यह भी देखें
- यादृच्छिक संख्या जनकों की सूची - श्रेष्ठतर सांख्यिकीय गुणवत्ता वाले कुछ सहित अन्य पीआरएनजी
- एसीओआरएन (पीआरएनजी) - एसीजी के साथ भ्रमित न हों, ऐसा प्रतीत होता है कि यह शब्द एलसीजी और एलएफएसआर जनक के भिन्नरूप के लिए उपयोग किया गया है।
- क्रमपरिवर्तित सर्वांगसम जनक
- सम्पूर्ण चक्र
- व्युत्क्रम सर्वांगसम जनक
- गुणन-के-साथ-ऋणी
- लेहमर आरएनजी (कभी-कभी पार्क-मिलर आरएनजी भी कहा जाता है)
- संयुक्त रैखिक सर्वांगसम जनक
टिप्पणियाँ
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Knuth, Donald (1997). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Reading, MA: Addison-Wesley Professional. pp. 10–26.
- ↑ 2.0 2.1 2.2 Steele, Guy; Vigna, Sebastiano (15 January 2020). "Computationally easy, spectrally good multipliers for congruential pseudorandom number generators". arXiv:2001.05304 [cs.DS].
At this point it is unlikely that the now-traditional names will be corrected.
Mathematics of Computation (to appear). Associated data at https://github.com/vigna/CPRNG. - ↑ Lehmer, Derrick H. (1951). "बड़े पैमाने की कंप्यूटिंग इकाइयों में गणितीय तरीके". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.
- ↑ Thomson, W. E. (1958). "छद्म-यादृच्छिक संख्याएँ उत्पन्न करने की एक संशोधित सर्वांगसमता विधि". The Computer Journal. 1 (2): 83. doi:10.1093/comjnl/1.2.83.
- ↑ Rotenberg, A. (1960). "एक नया छद्म-यादृच्छिक संख्या जेनरेटर". Journal of the ACM. 7 (1): 75–77. doi:10.1145/321008.321019. S2CID 16770825.
- ↑ L'Ecuyer, Pierre (13 July 2017). Chan, W. K. V.; D'Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (eds.). History of Uniform Random Number Generation (PDF). Proceedings of the 2017 Winter Simulation Conference (to appear). Las Vegas, United States. hal-01561551.
- ↑ 7.0 7.1 Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi:10.1073/pnas.61.1.25. PMC 285899. PMID 16591687.
- ↑ Park, Stephen K.; Miller, Keith W. (October 1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042. S2CID 207575300.
- ↑ Hörmann, Wolfgang; Derflinger, Gerhard (1993). "A Portable Uniform Random Number Generator Well Suited for the Rejection Method" (PDF). ACM Transactions on Mathematical Software. 19 (4): 489–495. CiteSeerX 10.1.1.52.3811. doi:10.1145/168173.168414. S2CID 15238956.
a multiplier about as small as √m, produces random numbers with a bad one-dimensional distribution.
- ↑ 10.0 10.1 L'Ecuyer, Pierre (1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure". Mathematics of Computation. 68 (225): 249–260. Bibcode:1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024. doi:10.1090/S0025-5718-99-00996-5. Be sure to read the Errata as well.
- ↑ 11.0 11.1 Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 978-0-521-43064-7.
- ↑ Jain, Raj (9 July 2010). "Computer Systems Performance Analysis Chapter 26: Random-Number Generation" (PDF). pp. 19–20. Retrieved 2017-10-31.
- ↑ Fenerty, Paul (11 September 2006). "Schrage's Method". Retrieved 2017-10-31.
- ↑ Hull, T. E.; Dobell, A. R. (July 1962). "Random Number Generators" (PDF). SIAM Review. 4 (3): 230–254. Bibcode:1962SIAMR...4..230H. doi:10.1137/1004061. hdl:1828/3142. Retrieved 2016-06-26.
- ↑ Severance, Frank (2001). System Modeling and Simulation. John Wiley & Sons, Ltd. p. 86. ISBN 978-0-471-49694-6.
- ↑ Austin, David (March 2008). "Random Numbers: Nothing Left to Chance". American Mathematical Society.
- ↑ Implementation in glibc-2.26 release. See the code after the test for "TYPE_0"; the GNU C library's rand() in stdlib.h uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator (initialized using minstd_rand0) and the period increases. See the simplified code that reproduces the random sequence from this library.
- ↑ K. Entacher (21 August 1997). A collection of selected pseudorandom number generators with linear structures. CiteSeerX 10.1.1.53.3686. Retrieved 16 June 2012.
- ↑ "Last public Committee Draft from April 12, 2011" (PDF). p. 346f. Retrieved 21 Dec 2014.
- ↑ "How Visual Basic Generates Pseudo-Random Numbers for the RND Function". Microsoft. 24 June 2004. Archived from the original on 21 July 2020. Retrieved 17 June 2011.
- ↑ In spite of documentation on MSDN, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
- ↑ 22.0 22.1 "ISO/IEC 14882:2011". ISO. 2 September 2011. Retrieved 3 September 2011.
- ↑ "Creating and Controlling a Random Number Stream". MathWorks. Retrieved 7 June 2021.
- ↑ "GNU Scientific Library: Other random number generators".
- ↑ Stephen J. Chapman. "Example 6.4 – Random Number Generator". "MATLAB Programming for Engineers". 2015. pp. 253–256.
- ↑ Stephen J. Chapman. "Example 6.4 – Random Number Generator". "MATLAB Programming with Applications for Engineers". 2012. pp. 292–295.
- ↑ S. J. Chapman. random0. 2004.
- ↑ Stephen J. Chapman. "Introduction to Fortran 90/95". 1998. pp. 322–324.
- ↑ Wu-ting Tsai. "'Module': A Major Feature of the Modern Fortran". pp. 6–7.
- ↑ The Open Group Base Specifications Issue 7 IEEE Std 1003.1, 2013 Edition
- ↑ Cadot, Sidney. "rand.s". cc65. Retrieved 8 July 2016.
- ↑ O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. pp. 6–7. HMC-CS-2014-0905.
- ↑ Tezuka, Shu; L'Ecuyer, Pierre (October 1993). On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators (PDF). Workshop on Stochastic Numerics. Kyoto University.
- ↑ Tezuka, Shi; L'Ecuyer, Pierre (December 1992). Analysis of Add-with-Carry and Subtract-with-Borrow Generators (PDF). Proceedings of the 1992 Winter Simulation Conference. pp. 443–447.
- ↑ Gershenfeld, Neil (1999). "Section 5.3.2: Linear Feedback". गणितीय मॉडलिंग की प्रकृति (First ed.). Cambridge University Press. p. 59. ISBN 978-0-521-57095-4.
- ↑ Matsumoto, Makoto; Nishimura, Takuji (January 1998). "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995. S2CID 3332028. Archived from the original (PDF) on 2017-11-07.
- ↑ Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (June 2005). "Traditional Pseudo-random Sequences". सुरक्षा के लिए यादृच्छिकता आवश्यकताएँ. IETF. sec. 6.1.3. doi:10.17487/RFC4086. BCP 106. RFC 4086.
संदर्भ
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 7.1.1. Some History", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
- Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods, 2nd edition, Springer, ISBN 0-387-00178-6.
- Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators" (PDF). Journal of the ACM. 36 (1): 129–141. doi:10.1145/58562.59305. S2CID 3565772. (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).
बाहरी संबंध
- The simulation Linear Congruential Generator visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
- Security of Random Number Generation: An Annotated Bibliography
- Linear Congruential Generators post to sci.math
- The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images
- P. L'Ecuyer and R. Simard, "TestU01: A C Library for Empirical Testing of Random Number Generators", May 2006, revised November 2006, ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.
- Article about another way of cracking LCG