रैखिक सर्वांगसम जनक: Difference between revisions

From Vigyanwiki
(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|दो मॉड्यूलो-9 एलसीजी दिखाते हैं कि कैसे अलग-अलग पैरामीटर अलग-अलग चक्र लंबाई की ओर ले जाते हैं। प्रत्येक पंक्ति तब तक विकसित होती स्थिति को दिखाती है जब तक वह दोहराई न जाए। शीर्ष पंक्ति एम = 9, = 2, सी = 0 और 1 के बीज के साथ एक जनरेटर दिखाती है, जो लंबाई 6 का एक चक्र उत्पन्न करती है। दूसरी पंक्ति 3 के बीज के साथ एक ही जनरेटर है, जो एक चक्र का उत्पादन करती है लंबाई 2. a = 4 और c = 1 (नीचे पंक्ति) का उपयोग करने से [0, 8] में किसी भी बीज के साथ 9 की चक्र लंबाई मिलती है।]]एक रैखिक सर्वांगसम जनरेटर (एलसीजी) एक [[कलन विधि]] है जो एक असंतत टुकड़े-टुकड़े रैखिक फ़ंक्शन के साथ गणना की गई छद्म-यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है। यह विधि सबसे पुराने और सबसे प्रसिद्ध [[छद्म यादृच्छिक संख्या जनरेटर]] एल्गोरिदम में से एक का प्रतिनिधित्व करती है। उनके पीछे के सिद्धांत को समझना अपेक्षाकृत आसान है, और उन्हें आसानी से और तेजी से लागू किया जाता है, खासकर कंप्यूटर हार्डवेयर पर जो स्टोरेज-बिट ट्रंकेशन द्वारा [[मॉड्यूलर अंकगणित]] प्रदान कर सकता है।
[[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>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), या लेहमर RNG कहा जाता है। यदि c ≠ 0 है, तो विधि को 'मिश्रित सर्वांगसम जनरेटर' कहा जाता है।{{r|KnuthV2|p=4-}}
[[पूर्णांक]] स्थिरांक हैं जो जनक को निर्दिष्ट करते हैं। यदि c = 0 है, तो जनक को प्रायः गुणक सर्वांगसम जनक (MCG), या लेहमर आरएनजी कहा जाता है। यदि c ≠ 0 है, तो विधि को मिश्रित सर्वांगसम जनक कहा जाता है।{{r|KnuthV2|p=4-}}


जब c ≠ 0, एक गणितज्ञ पुनरावृत्ति को एक [[रैखिक परिवर्तन]] कहेगा, रैखिक ट्रांसफ़ॉर्मेशन नहीं, लेकिन कंप्यूटर विज्ञान में यह मिथ्या नाम अच्छी तरह से स्थापित है।<ref name=Steele20>{{cite arXiv
जब 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>
लेहमर जनक 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
एलसीजी का एक लाभ यह है कि मापदंडों के उचित चयन से एक ऐसी अवधि प्राप्त होती है जो ज्ञात और दीर्घ दोनों होती है। हालांकि यह एकमात्र मानदंड नहीं है, बहुत छोटी अवधि कूट-यादृच्छिक संख्या जनक में एक घातक दोष है।<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>
जबकि एलसीजी छद्म यादृच्छिक संख्याएं उत्पन्न करने में सक्षम हैं जो यादृच्छिकता के लिए औपचारिक परीक्षण पास कर सकते हैं, आउटपुट की गुणवत्ता पैरामीटर एम और ए की पसंद के प्रति बेहद संवेदनशील है।{{r|Marsaglia68|KnuthV2|Park88|Hörmann92|LEcuyer99|Steele20}} उदाहरण के लिए, a = 1 और c = 1 एक साधारण मॉड्यूलो-एम काउंटर का उत्पादन करता है, जिसकी लंबी अवधि होती है, लेकिन यह स्पष्ट रूप से गैर-यादृच्छिक है।


ऐतिहासिक रूप से, खराब विकल्पों के कारण एलसीजी का कार्यान्वयन अप्रभावी हो गया है। इसका एक विशेष उदाहरण [[RANDU]] है, जिसका 1970 के दशक की शुरुआत में व्यापक रूप से उपयोग किया गया था और इसके कई परिणाम सामने आए थे, जिन पर वर्तमान में इस खराब एलसीजी के उपयोग के कारण सवाल उठाए जा रहे हैं।<ref name="Press">{{cite book |last=Press |
जबकि एलसीजी कूट-यादृच्छिक संख्याएं उत्पन्न करने में सक्षम हैं जो यादृच्छिकता के लिए औपचारिक परीक्षण पारित कर सकते हैं, आउटपुट की गुणवत्ता मापदण्ड 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>
पैरामीटर चयन के तीन सामान्य परिवार हैं:


=== एम अभाज्य, सी = 0 ===
मापदण्ड चयन के तीन सामान्य वर्ग हैं:
{{main|Lehmer random number generator}}
यह मूल लेहमर आरएनजी निर्माण है। यदि गुणक 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 mod 2) के रूप में की जा सकती है<sup>ई</sup>) + डी{{floor|''ax''/2<sup>''e''</sup>}}. यदि परिणाम बहुत बड़ा है तो इसके बाद m का सशर्त घटाव होना चाहिए, लेकिन घटाव की संख्या ad/m तक सीमित है, जिसे d छोटा होने पर आसानी से एक तक सीमित किया जा सकता है।
=== m अभाज्य, c = 0 ===
{{main|लेहमर यादृच्छिक संख्या जनित्र}}


यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है, और गुणक सावधानी से चुना गया है, तो 'श्रेज विधि'<ref>{{cite web
यह मूल लेहमर आरएनजी निर्माण है। यदि गुणक 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, यानी। {{nobr|1=''q'' = {{floor|''m''/''a''}}}} और {{nobr|1=''r'' = ''m'' mod ''a''}}. फिर ax mod m = की गणना करें {{nobr|''a''(''x'' mod ''q'') − ''r''{{floor|''x''/''q''}}}}. चूँकि x mod 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
}}</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 ===
दूसरी हानि यह है कि मान 1 ≤ x < m को समान यादृच्छिक बिट्स में परिवर्तित करना अनुपयुक्त है। यदि 2 की घात से कम अभाज्य का उपयोग किया जाता है, तो कभी-कभी लुप्त मानों को सरलता से उपेक्षित कर दिया जाता है।
m को दो की घात के रूप में चुनने पर, प्रायः m = 2 होता है<sup>32</sup>या एम = 2<sup>64</sup>, एक विशेष रूप से कुशल एलसीजी का उत्पादन करता है, क्योंकि यह केवल बाइनरी प्रतिनिधित्व को छोटा करके मॉड्यूलस ऑपरेशन की गणना करने की अनुमति देता है। वास्तव में, सबसे महत्वपूर्ण बिट्स की आमतौर पर गणना ही नहीं की जाती है। हालाँकि, इसके नुकसान भी हैं।


इस फॉर्म में अधिकतम अवधि m/4 है, जो a ≡ 3 या a ≡ 5 (mod 8) होने पर प्राप्त होती है। प्रारंभिक अवस्था X<sub>0</sub> विषम होना चाहिए, और X के निम्न तीन बिट दो स्थितियों के बीच वैकल्पिक होते हैं और उपयोगी नहीं होते हैं। यह दिखाया जा सकता है कि यह फॉर्म एक जनरेटर के बराबर है जिसका मापांक एक चौथाई आकार और c ≠ 0 है।{{r|KnuthV2}}
=== m 2 की घात, c = 0 ===
m को 2 की घात के रूप में चुनना, प्रायः m = 2<sup>32</sup> या m = 2<sup>64</sup>, एक विशेष रूप से कुशल एलसीजी उत्पन्न करता है, क्योंकि यह केवल द्विचर प्रतिनिधित्व को छोटा करके मापांक संचालन की गणना करने की अनुमति देता है। वास्तव में, सबसे महत्वपूर्ण बिट्स की सामान्यतः गणना ही नहीं की जाती है। हालाँकि, इसकी हानि भी हैं।


पावर-टू-टू मॉड्यूलस के उपयोग के साथ एक अधिक गंभीर मुद्दा यह है कि कम बिट्स की अवधि उच्च बिट्स की तुलना में कम होती है। X का निम्नतम क्रम वाला बिट कभी नहीं बदलता (X हमेशा विषम होता है), और अगले दो बिट दो स्थितियों के बीच वैकल्पिक होते हैं। (यदि a≡5 (mod 8) है, तो बिट 1 कभी नहीं बदलता है और बिट 2 बदलता है। यदि a≡3 (mod 8) है, तो बिट 2 कभी नहीं बदलता है और बिट 1 बदलता है।) बिट 3 4 की अवधि के साथ दोहराता है, बिट 4 का आवर्त 8 है, इत्यादि। केवल X का सबसे महत्वपूर्ण बिट ही पूर्ण अवधि प्राप्त करता है।
इस विधि में अधिकतम अवधि m/4 है, जो a ≡ 3 या a ≡ 5 (मॉड 8) होने पर प्राप्त होती है। प्रारंभिक अवस्था X<sub>0</sub> विषम होना चाहिए और X के निम्न तीन बिट दो स्थितियों के मध्य वैकल्पिक होते हैं और उपयोगी नहीं होते हैं। यह दर्शाया जा सकता है कि यह विधि एक जनक के बराबर है जिसका मापांक एक चौथाई आकार और c ≠ 0 है।{{r|KnuthV2}}


=== सी ≠ 0 ===
2 की घात के मापांक के उपयोग के साथ एक अधिक जटिल विवाद यह है कि कम बिट्स की अवधि उच्च बिट्स की तुलना में कम होती है। X का निम्नतम क्रम वाला बिट कभी परिवर्तित नहीं होता है (X सदैव विषम होता है) और अगले दो बिट दो स्थितियों के मध्य वैकल्पिक होते हैं। यदि a≡5 (मॉड 8) है, तो बिट 1 कभी परिवर्तित नहीं होता है और बिट 2 परिवर्तित होता है। यदि a≡3 (मॉड 8) है, तो बिट 2 कभी परिवर्तित नहीं होता है और बिट 1 परिवर्तित होता है। बिट 3, 4 की अवधि के साथ दोहराता है, बिट 4 का आवर्त 8 है, इत्यादि। केवल X का सबसे महत्वपूर्ण बिट ही पूर्ण अवधि प्राप्त करता है।
जब c ≠ 0, सही ढंग से चुने गए पैरामीटर सभी बीज मूल्यों के लिए m के बराबर अवधि की अनुमति देते हैं। यह तब घटित होगा जब और केवल यदि:{{r|KnuthV2|p=17—19}}
 
=== 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>m</math>,
# <math>a - 1</math> के सभी अभाज्य गुणनखंडों से विभाज्य <math>m</math> है,
# <math>a - 1</math> यदि 4 से विभाज्य है <math>m</math> 4 से विभाज्य है.
# <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 (mod m) की अनुमति देता, जो बहुत खराब PRNG बनाता है; संभावित पूर्ण-अवधि गुणकों का चयन केवल तभी उपलब्ध होता है जब m में अभाज्य गुणनखंड दोहराए जाते हैं।


यद्यपि हल-डोबेल प्रमेय अधिकतम अवधि प्रदान करता है, यह एक अच्छे जनरेटर की गारंटी देने के लिए पर्याप्त नहीं है। उदाहरण के लिए, यह वांछनीय है कि a − 1, m के अभाज्य गुणनखंडों द्वारा आवश्यकता से अधिक विभाज्य न हो। इस प्रकार, यदि m 2 की घात है, तो a − 1 को 4 से विभाज्य होना चाहिए, लेकिन 8 से विभाज्य नहीं होना चाहिए, अर्थात a ≡ 5 (mod 8)।{{r|KnuthV2|p=§3.2.1.3}}
इस विधि का उपयोग किसी भी 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>


वास्तव में, अधिकांश गुणक एक अनुक्रम उत्पन्न करते हैं जो गैर-यादृच्छिकता या किसी अन्य के लिए एक परीक्षण में विफल रहता है, और एक ऐसा गुणक ढूंढता है जो सभी लागू मानदंडों के लिए संतोषजनक है{{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>) को लिखना बहुत सरल बना देती हैं, इसलिए यह अधिक सामान्यतः उपयोग की जाने वाली विधि है।
ध्यान दें कि पावर-ऑफ़-2 मॉड्यूलस समस्या को साझा करता है जैसा कि c = 0 के लिए ऊपर वर्णित है: निम्न k बिट्स मॉड्यूलस 2 के साथ एक जनरेटर बनाते हैं<sup>k</sup> और इस प्रकार 2 की अवधि के साथ दोहराएँ<sup></sup>; केवल सबसे महत्वपूर्ण बिट ही पूर्ण अवधि को प्राप्त करता है। यदि r से कम छद्म यादृच्छिक संख्या वांछित है, {{floor|''rX''/''m''}} एक्स मॉड आर की तुलना में बहुत उच्च गुणवत्ता वाला परिणाम है। दुर्भाग्य से, अधिकांश प्रोग्रामिंग भाषाएँ बाद वाले को लिखना बहुत आसान बना देती हैं (<code>X % r</code>), इसलिए यह अधिक सामान्यतः उपयोग किया जाने वाला रूप है।


जनरेटर c की पसंद के प्रति संवेदनशील नहीं है, जब तक कि यह मापांक के लिए अपेक्षाकृत प्रमुख है (उदाहरण के लिए यदि m 2 की शक्ति है, तो c विषम होना चाहिए), इसलिए मान c=1 आमतौर पर चुना जाता है।
जनक c के चयन के प्रति संवेदनशील नहीं है, जब तक कि यह मापांक के लिए अपेक्षाकृत प्रमुख है (उदाहरण के लिए यदि m 2 की घात है, तो c विषम होना चाहिए), इसलिए मान c=1 सामान्यतः चुना जाता है।


C के अन्य विकल्पों द्वारा निर्मित श्रृंखला को श्रृंखला के एक सरल कार्य के रूप में लिखा जा सकता है जब c=1।{{r|KnuthV2|p=11}} विशेष रूप से, यदि Y, Y द्वारा परिभाषित प्रोटोटाइप श्रृंखला है<sub>0</sub> = 0 और Y<sub>''n''+1</sub> = एवाई<sub>n</sub>+1 मॉड मी, फिर एक सामान्य श्रृंखला एक्स<sub>''n''+1</sub> = एक्स<sub>n</sub>+c mod m को Y के एफ़िन फ़ंक्शन के रूप में लिखा जा सकता है:
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>
:<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>
:<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}}
निम्न तालिका सामान्य उपयोग में एलसीजी के मापदंडों को सूचीबद्ध करती है, जिसमें विभिन्न [[ संकलक |संकलकों]] के [[ क्रम पुस्तकालय |कार्यावधि पुस्तकालयों]] में अंतर्निहित रैंड () फलन सम्मिलित हैं। यह तालिका लोकप्रियता दर्शाने के लिए है, अनुकरण करने के लिए उदाहरण नहीं; इनमें से कई मापदण्ड ख़राब हैं। अच्छे मापदंडों की तालिकाएँ उपलब्ध हैं।{{r|LEcuyer99|Steele20}}


{|class="wikitable"
{|class="wikitable"
! Source || modulus<br/>''m'' || multiplier<br/>''a'' || increment<br/>''c'' || output bits of seed in ''rand()'' or ''Random(L)''
! स्रोत || गुणांक<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]]'' from the "quick and dirty generators" list, Chapter 7.1, Eq. 7.1.6 <br /> parameters from Knuth and H. W. Lewis || 2<sup>32</sup> || 1664525 || 1013904223 ||  
| "त्वरित और ख़राब जनक" सूची से ''[[Numerical Recipes|संख्यात्मक व्यंजन]]'' ,  
अध्याय 7.1, समीकरण- 7.1.6<br /> नुथ और एच. डब्ल्यू. लुईस से मापदण्ड
| 2<sup>32</sup> || 1664525 || 1013904223 ||  
|-
|-
| [[Borland]] C/C++ || 2<sup>32</sup> || 22695477 || 1 || bits 30..16 in ''rand()'', 30..0 in ''lrand()''
| [[Borland|बोरलैंड]] सी/सी++ || 2<sup>32</sup> || 22695477 || 1 || रैंड() में बिट्स 30..16, लैरैंड() में 30..0
|-
|-
| [[glibc]] (used by [[GNU Compiler Collection|GCC]])<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>
| [[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 || bits 30..0
| 2<sup>31</sup> || 1103515245 || 12345 || बिट्स 30..0
|-
|-
| [[ANSI C]]: [[Watcom C compiler|Watcom]], [[Digital Mars]], [[CodeWarrior]], [[IBM VisualAge]] C/C++<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)|C90]], [[C99]], [[C11 (C standard revision)|C11]]: Suggestion in the ISO/IEC 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]] || 2<sup>31</sup> || 1103515245 || 12345 || bits 30..16
| [[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 || bits 63..32 of ''(seed × L)''
| [[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++|Microsoft Visual/Quick C/C++]] || 2<sup>32</sup> || 214013 (343FD<sub>16</sub>) || 2531011 (269EC3<sub>16</sub>) || bits 30..16
| [[Visual C++|माइक्रोसॉफ्ट]] [[Visual Basic|दृश्य]]/क्विक सी/सी++ || 2<sup>32</sup> || 214013 (343एफडी<sub>16</sub>) || 2531011 (269ईसी3<sub>16</sub>) || बिट्स 30..16
|-
|-
| [[Visual Basic|Microsoft Visual Basic]] (6 and earlier)<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 (43FD43FD<sub>16</sub>) || 12820163 (C39EC3<sub>16</sub>) ||
| [[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>) ||
|-
|-
| RtlUniform from [[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
| [[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 (7FFFFFED<sub>16</sub>) || 2147483587 (7FFFFFC3<sub>16</sub>) ||
|| 2147483629 (7एफएफएफएफएफईडी<sub>16</sub>) || 2147483587 (7एफएफएफएफएफसी3<sub>16</sub>) ||
|-
|-
| [[CarbonLib|Apple CarbonLib]], [[C++11]]'s <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> MATLAB's v4 legacy generator mcg16807<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 || see [[MINSTD]]
| [[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]]'s <code>minstd_rand</code><ref name="cpp11" /> || 2<sup>31</sup> − 1 || 48271 || 0 || see [[MINSTD]]
| [[C++11|सी]][[C++11|++11]] का <code>minstd_rand</code><ref name="cpp11" /> || 2<sup>31</sup> − 1 || 48271 || 0 || [[MINSTD|एमआईएनएसटीडी]] देखें
|-
|-
| [[MMIX]] by [[Donald Knuth]] || 2<sup>64</sup> || 6364136223846793005 || 1442695040888963407 ||
| [[Donald Knuth|डोनाल्ड नुथ]] द्वारा [[MMIX|एमएमआईएक्स]] || 2<sup>64</sup> || 6364136223846793005 || 1442695040888963407 ||
|-
|-
| [[Newlib]] || 2<sup>64</sup> || 6364136223846793005 || 1 || bits 62..32 (46..32 for 16-bit int)
| [[Newlib|न्यूलिब]] || 2<sup>64</sup> || 6364136223846793005 || 1 || बिट्स 62..32 (16-बिट इंट के लिए 46..32)
|-
|-
| [[Musl]] || 2<sup>64</sup> || 6364136223846793005 || 1 || bits 63..33
| [[Musl|मसल]] || 2<sup>64</sup> || 6364136223846793005 || 1 || बिट्स 63..33
|-
|-
| [[OpenVMS|VMS]]'s '''MTH$RANDOM''',<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> old versions of [[glibc]] || 2<sup>32</sup> || 69069 (10DCD<sub>16</sub>) || 1 ||
| [[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]]'s java.util{{Not a typo|.}}Random, [[POSIX]] [ln]rand48, [[glibc]] [ln]rand48[_r]|| 2<sup>48</sup> || 25214903917 (5DEECE66D<sub>16</sub>) || 11 || bits 47..16
| [[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]rand48, [[glibc]] [mj]rand48[_r]|| 2<sup>48</sup> || 25214903917 (5DEECE66D<sub>16</sub>) || 11 || bits 47..15
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]rand48, [[glibc]] [de]rand48[_r]|| 2<sup>48</sup> || 25214903917 (5DEECE66D<sub>16</sub>) || 11 || bits 47..0
| [[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>) || bits 22..8
| [[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>) || bits 31..16
| [[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 (B3B3B3B3<sub>16</sub>) || previously bits 31..16, current bits 31..16 xor bits 14..0
| [[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;"
| ''Formerly common:'' {{midsize|[[RANDU]]}}<ref name=Press/> || 2<sup>31</sup> || 65539 || 0 ||
| ''पूर्व में सामान्य:'' {{midsize|[[आरएएनडीयू]]}}<ref name=Press/> || 2<sup>31</sup> || 65539 || 0 ||
|}
|}
जैसा कि ऊपर दिखाया गया है, एलसीजी हमेशा अपने द्वारा उत्पादित मूल्यों में सभी बिट्स का उपयोग नहीं करते हैं। उदाहरण के लिए, [[जावा (प्रोग्रामिंग भाषा)]] कार्यान्वयन प्रत्येक पुनरावृत्ति पर 48-बिट मानों के साथ संचालित होता है, लेकिन केवल उनके 32 सबसे महत्वपूर्ण बिट्स लौटाता है। ऐसा इसलिए है क्योंकि उच्च-क्रम वाले बिट्स की अवधि निचले-क्रम वाले बिट्स की तुलना में लंबी होती है (नीचे देखें)। एलसीजी जो इस ट्रंकेशन तकनीक का उपयोग करते हैं, वे उन लोगों की तुलना में सांख्यिकीय रूप से बेहतर मूल्य उत्पन्न करते हैं जो ऐसा नहीं करते हैं। यह उन स्क्रिप्ट्स में विशेष रूप से ध्यान देने योग्य है जो रेंज को कम करने के लिए मॉड ऑपरेशन का उपयोग करते हैं; यादृच्छिक संख्या मॉड 2 को संशोधित करने से बिना किसी काट-छाँट के 0 और 1 को वैकल्पिक किया जा सकेगा।
जैसा कि ऊपर दर्शाया गया है, एलसीजी सदैव अपने द्वारा उत्पादित मानों में सभी बिट्स का उपयोग नहीं करते हैं। उदाहरण के लिए, [[जावा (प्रोग्रामिंग भाषा)|जावा]] कार्यान्वयन प्रत्येक पुनरावृत्ति पर 48-बिट मानों के साथ संचालित होता है, परन्तु केवल उनके 32 सबसे महत्वपूर्ण बिट्स लौटाता है। ऐसा इसलिए है क्योंकि उच्च-क्रम वाले बिट्स की अवधि निचले-क्रम वाले बिट्स की तुलना में लंबी होती है (नीचे देखें)। एलसीजी जो इस खंडन प्रविधि का उपयोग करते हैं, वे उन लोगों की तुलना में सांख्यिकीय रूप से श्रेष्ठतर मान उत्पन्न करते हैं जो ऐसा नहीं करते हैं। यह उन आलेखों में विशेष रूप से ध्यान देने योग्य है जो पंक्ति श्रृंखला को कम करने के लिए मॉड संक्रिया का उपयोग करते हैं; यादृच्छिक संख्या मॉड 2 को संशोधित करने से बिना किसी खंडन के 0 और 1 को वैकल्पिक किया जा सकेगा।


==फायदे और नुकसान==
==लाभ और हानि==
{{More sources needed section|date=July 2021}}
{{More sources needed section|date=जुलाई 2021}}
एलसीजी तेज़ हैं और स्थिति को बनाए रखने के लिए न्यूनतम मेमोरी (एक मॉड्यूलो-एम नंबर, अक्सर 32 या 64 बिट्स) की आवश्यकता होती है। यह उन्हें कई स्वतंत्र धाराओं के अनुकरण के लिए मूल्यवान बनाता है। क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए एलसीजी का इरादा नहीं है, और इसका उपयोग नहीं किया जाना चाहिए; ऐसे अनुप्रयोगों के लिए [[क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म यादृच्छिक संख्या जनरेटर]] का उपयोग करें।
एलसीजी तीव्र हैं और स्थिति को बनाए रखने के लिए न्यूनतम मेमोरी (एक मापांक-m संख्या, प्रायः 32 या 64 बिट्स) की आवश्यकता होती है। यह उन्हें कई स्वतंत्र धाराओं के अनुकरण के लिए मूल्यवान बनाता है। गूढ़लेखिकी अनुप्रयोगों के लिए एलसीजी का उद्दिष्ट नहीं है और इसका उपयोग नहीं किया जाना चाहिए; ऐसे अनुप्रयोगों के लिए [[क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म यादृच्छिक संख्या जनरेटर|गूढ़लेखिकी रूप से सुरक्षित कूट यादृच्छिक संख्या जनक]] का उपयोग करें।


[[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
[[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 बिट आउटपुट के साथ एक आदर्श यादृच्छिक संख्या जनरेटर से यह अपेक्षा की जाती है कि ([[जन्मदिन प्रमेय]] के अनुसार) पहले के आउटपुट को डुप्लिकेट करना शुरू कर देगा। {{math|{{sqrt|''m''}} ≈ 2<sup>16</sup>}} परिणाम। कोई भी पीआरएनजी जिसका आउटपुट उसकी पूर्ण, असंतुलित स्थिति है, तब तक डुप्लिकेट उत्पन्न नहीं करेगा जब तक कि उसकी पूरी अवधि समाप्त न हो जाए, यह एक आसानी से पता लगाने योग्य सांख्यिकीय दोष है। संबंधित कारणों से, किसी भी पीआरएनजी की अवधि आवश्यक आउटपुट की संख्या के वर्ग से अधिक होनी चाहिए। आधुनिक कंप्यूटर गति को देखते हुए, इसका मतलब 2 की अवधि है<sup>64</sup>सबसे कम मांग वाले अनुप्रयोगों को छोड़कर सभी के लिए, और अधिक मांग वाले सिमुलेशन के लिए।
एक विशिष्ट उदाहरण के लिए, 32 बिट आउटपुट के साथ एक आदर्श यादृच्छिक संख्या जनक से ([[जन्मदिन प्रमेय|बर्थ्डै प्रमेय]] के अनुसार) {{math|{{sqrt|''m''}} ≈ 2<sup>16</sup>}} परिणामों के बाद पहले के आउटपुट को अनुलिपि करना, प्रारंभ करने की आशा की जाती है। कोई भी पीआरएनजी जिसका आउटपुट उसकी पूर्ण, असंतुलित स्थिति है, तब तक अनुलिपि उत्पन्न नहीं करेगा जब तक कि उसकी सम्पूर्ण अवधि समाप्त न हो जाए, यह एक सरलता से पता लगाने योग्य सांख्यिकीय दोष है। संबंधित कारणों से, किसी भी पीआरएनजी की अवधि आवश्यक आउटपुट की संख्या के वर्ग से अधिक होनी चाहिए। आधुनिक परिकलक गति को देखते हुए, इसका अर्थ है कि कम से कम मांग वाले अनुप्रयोगों को छोड़कर सभी के लिए 2<sup>64</sup> की अवधि, और मांग वाले अनुकरण के लिए दीर्घ अवधि है।


एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि इसका उपयोग एन-आयामी स्थान में बिंदुओं को चुनने के लिए किया जाता है, तो बिंदु अधिक से अधिक, पर स्थित होंगे। {{math|{{radic|''n''!⋅''m''|''n''}} }}[[हाइपरप्लेन]] (मार्सग्लिया का प्रमेय, [[जॉर्ज मार्साग्लिया]] द्वारा विकसित)<ref name=Marsaglia68>{{cite journal
एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि 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 के क्रमिक मानों के बीच क्रमिक सहसंबंध के कारण है<sub>n</sub>. लापरवाही से चुने गए मल्टीप्लायरों में आमतौर पर बहुत कम, व्यापक दूरी वाले विमान होंगे, जिससे समस्याएं पैदा हो सकती हैं। वर्णक्रमीय परीक्षण, जो एलसीजी की गुणवत्ता का एक सरल परीक्षण है, इस अंतर को मापता है और एक अच्छे गुणक को चुनने की अनुमति देता है।
  }}</ref> यह अनुक्रम X<sub>n</sub> के क्रमिक मानों के मध्य क्रमिक सहसंबंध के कारण है। असावधानतः चुने गए गुणकों में सामान्यतः बहुत कम, व्यापक दूरी वाले विमान होंगे, जिससे समस्याएं उत्पन्न हो सकती हैं। वर्णक्रमीय परीक्षण, जो एलसीजी की गुणवत्ता का एक सरल परीक्षण है, इस अंतर को मापता है और एक अच्छे गुणक को चुनने की अनुमति देता है।


समतल अंतर मापांक और गुणक दोनों पर निर्भर करता है। एक बड़ा पर्याप्त मापांक इस दूरी को दोहरे परिशुद्धता संख्याओं के रिज़ॉल्यूशन से कम कर सकता है। मापांक बड़ा होने पर गुणक का चुनाव कम महत्वपूर्ण हो जाता है। वर्णक्रमीय सूचकांक की गणना करना और यह सुनिश्चित करना अभी भी आवश्यक है कि गुणक खराब नहीं है, लेकिन विशुद्ध रूप से संभाव्य रूप से जब मापांक लगभग 2 से बड़ा होता है तो खराब गुणक का सामना करना बेहद असंभव हो जाता है।<sup>64</sup>.
समतल अंतर मापांक और गुणक दोनों पर निर्भर करता है। एक बड़ा पर्याप्त मापांक इस दूरी को दोहरे परिशुद्धता संख्याओं के खंडन से कम कर सकता है। मापांक बड़ा होने पर गुणक का चुनाव कम महत्वपूर्ण हो जाता है। वर्णक्रमीय सूचकांक की गणना करना और यह सुनिश्चित करना अभी भी आवश्यक है कि गुणक खराब नहीं है, परन्तु विशुद्ध रूप से संभाव्य रूप से जब मापांक लगभग 2<sup>64</sup> से बड़ा होता है तो खराब गुणक का सामना करना अत्यधिक असंभव हो जाता है।


एलसीजी के लिए विशिष्ट एक और दोष निम्न-ऑर्डर बिट्स की छोटी अवधि है जब एम को 2 की शक्ति के रूप में चुना जाता है। इसे आवश्यक आउटपुट से बड़े मॉड्यूल का उपयोग करके और राज्य के सबसे महत्वपूर्ण बिट्स का उपयोग करके कम किया जा सकता है।
एलसीजी के लिए विशिष्ट एक और दोष निम्न-अनुक्रम बिट्स की छोटी अवधि है जब m को 2 की घात के रूप में चुना जाता है। इसे आवश्यक आउटपुट से बड़े मापांक का उपयोग करके और समष्टि के सबसे महत्वपूर्ण बिट्स का उपयोग करके कम किया जा सकता है।


फिर भी, कुछ अनुप्रयोगों के लिए एलसीजी एक अच्छा विकल्प हो सकता है। उदाहरण के लिए, एक एम्बेडेड सिस्टम में, उपलब्ध मेमोरी की मात्रा अक्सर गंभीर रूप से सीमित होती है। इसी तरह, [[ विडियो गेम कंसोल ]] जैसे वातावरण में एलसीजी की थोड़ी संख्या में उच्च-क्रम बिट्स लेना पर्याप्त हो सकता है। (जब एम 2 की शक्ति हो तो एलसीजी के निम्न-क्रम वाले बिट्स पर कभी भी यादृच्छिकता की किसी भी डिग्री के लिए भरोसा नहीं किया जाना चाहिए।) निम्न-क्रम वाले बिट्स बहुत छोटे चक्रों से गुजरते हैं। विशेष रूप से, कोई भी पूर्ण-चक्र एलसीजी, जब एम 2 की शक्ति है, बारी-बारी से विषम और सम परिणाम देगा।
फिर भी, कुछ अनुप्रयोगों के लिए एलसीजी एक अच्छा विकल्प हो सकता है। उदाहरण के लिए, एक सन्निहित प्रणाली में, उपलब्ध मेमोरी की मात्रा प्रायः गंभीर रूप से सीमित होती है। इसी तरह, [[ विडियो गेम कंसोल |विडियो गेम कंसोल]] जैसे वातावरण में एलसीजी की थोड़ी संख्या में उच्च-क्रम बिट्स लेना पर्याप्त हो सकता है। जब m, 2 की घात हो तो एलसीजी के निम्न-क्रम वाले बिट्स पर कभी भी यादृच्छिकता की किसी भी डिग्री के लिए विश्वास नहीं किया जाना चाहिए। निम्न-क्रम वाले बिट्स बहुत छोटे चक्रों से गुजरते हैं। विशेष रूप से, कोई भी पूर्ण-चक्र एलसीजी, जब m, 2 की घात है, विकल्पतः विषम और सम परिणाम देगा।


गैर-क्रिप्टोग्राफ़िक अनुप्रयोगों में उपयुक्तता के लिए एलसीजी का बहुत सावधानी से मूल्यांकन किया जाना चाहिए जहां उच्च गुणवत्ता वाली यादृच्छिकता महत्वपूर्ण है। मोंटे कार्लो सिमुलेशन के लिए, एक एलसीजी को आवश्यक यादृच्छिक नमूनों की संख्या के घन से अधिक और अधिमानतः बहुत अधिक मापांक का उपयोग करना चाहिए। इसका मतलब है, उदाहरण के लिए, कि एक (अच्छा) 32-बिट एलसीजी का उपयोग लगभग एक हजार यादृच्छिक संख्याएँ प्राप्त करने के लिए किया जा सकता है; 64-बिट एलसीजी लगभग 2 लोगों के लिए अच्छा है<sup>21</sup> यादृच्छिक नमूने (दो मिलियन से थोड़ा अधिक), आदि। इस कारण से, व्यवहार में एलसीजी बड़े पैमाने पर मोंटे कार्लो सिमुलेशन के लिए उपयुक्त नहीं हैं।
गैर-गूढ़ालेखी अनुप्रयोगों में उपयुक्तता के लिए एलसीजी का बहुत सावधानी से मानांकन किया जाना चाहिए जहां उच्च गुणवत्ता वाली यादृच्छिकता महत्वपूर्ण है। मोंटे कार्लो अनुकरण के लिए, एक एलसीजी को आवश्यक यादृच्छिक प्रतिदर्शों की संख्या के घन से अधिक और अधिमानतः बहुत अधिक मापांक का उपयोग करना चाहिए। इसका अर्थ है, उदाहरण के लिए, कि एक (अच्छा) 32-बिट एलसीजी का उपयोग लगभग एक हजार यादृच्छिक संख्याएँ प्राप्त करने के लिए किया जा सकता है; 64-बिट एलसीजी लगभग 2<sup>21</sup> यादृच्छिक प्रतिदर्शों (दो मिलियन से थोड़ा अधिक) आदि के लिए अच्छा है। इस कारण से, व्यवहार में एलसीजी बड़े पैमाने पर मोंटे कार्लो अनुकरण के लिए उपयुक्त नहीं हैं।


== नमूना कोड ==
== प्रतिदर्श कोड ==


===पायथन कोड===
===पायथन कोड===
[[ जेनरेटर (कंप्यूटर प्रोग्रामिंग) ]] के रूप में, [[पायथन (प्रोग्रामिंग भाषा)]] में एलसीजी का कार्यान्वयन निम्नलिखित है:
[[ जेनरेटर (कंप्यूटर प्रोग्रामिंग) | जनक]] के रूप में, [[पायथन (प्रोग्रामिंग भाषा)|पायथन]] में एलसीजी का कार्यान्वयन निम्नलिखित है:


<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
Line 237: Line 245:




===निःशुल्क पास्कल===
===मुक्त पास्कल===
[[ मुफ़्त पास्कल ]] अपने डिफ़ॉल्ट छद्म यादृच्छिक संख्या जनरेटर के रूप में [[मेरसेन ट्विस्टर]] का उपयोग करता है जबकि डेल्फ़ी एलसीजी का उपयोग करता है। उपरोक्त तालिका में दी गई जानकारी के आधार पर यहां फ्री पास्कल में डेल्फ़ी संगत उदाहरण दिया गया है। समान RandSeed मान को देखते हुए यह डेल्फ़ी के समान यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है।
[[ मुफ़्त पास्कल | मुक्त पास्कल]] अपने व्यतिक्रम कूट यादृच्छिक संख्या जनक के रूप में [[मेरसेन ट्विस्टर]] का उपयोग करता है जबकि डेल्फ़ी एलसीजी का उपयोग करता है। उपरोक्त तालिका में दी गई सूचना के आधार पर यहां मुक्त पास्कल में डेल्फ़ी संगत उदाहरण दिया गया है। समान रैंडसीड मान को देखते हुए यह डेल्फ़ी के समान यादृच्छिक संख्याओं का अनुक्रम उत्पन्न करता है।


<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 का एक सामान्य गुणनखंड होना चाहिए।) इसे मापांक के बराबर एकल एलसीजी के बराबर दिखाया जा सकता है घटक एलसीजी मॉड्यूलि का उत्पाद।
दीर्घ अवधि के उत्पादन की एक विधि विभिन्न अवधियों के कई एलसीजी के आउटपुट को योग करना है जिसमें एक बड़ा कम-से-कम सामान्य गुणक होता है; विचमैन-हिल जनक इस रूप का एक उदाहरण है। हम चाहेंगे कि वे पूर्णतया से सहअभाज्य हों, परन्तु एक अभाज्य मापांक एक सम अवधि को दर्शाता है, इसलिए कम-से-कम 2 का एक सामान्य गुणनखंड होना चाहिए। इसे मापांक के बराबर एकल एलसीजी के बराबर दर्शाया जा सकता है घटक एलसीजी मॉड्यूलि का उत्पाद है।


जॉर्ज मार्साग्लिया का ऐड-विथ-कैरी और [[कैरी से घटाएं]]|सबट्रेक्ट-विद-उधार पीआरएनजी, जिसका शब्द आकार b=2 है<sup>डब्ल्यू</sup> और लैग्स आर और एस (आर > एस) बी के मापांक के साथ एलसीजी के बराबर हैं<sup>आर</sup>±बी<sup></sup>±1.<ref>{{cite conference
जॉर्ज मार्साग्लिया की ऋणी के साथ जोड़ें और घटाव के साथ पश्चांक पीआरएनजी, शब्द आकार ''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>
ए के गुणक के साथ [[गुणन-के-साथ-ले जाना]] पीआरएनजी, एब के बड़े प्राइम मापांक के साथ एलसीजी के बराबर हैं<sup>r</sup>−1 और एक पावर-ऑफ-2 गुणक बी।


एक [[क्रमपरिवर्तित सर्वांगसम जनरेटर]] 2-मॉड्यूल एलसीजी की शक्ति से शुरू होता है और कम-ऑर्डर बिट्स में छोटी अवधि की समस्या को खत्म करने के लिए आउटपुट परिवर्तन लागू करता है।
a के गुणक के साथ [[गुणन-के-साथ-ले जाना|गुणन]] के साथ ऋणी पीआरएनजी, ''ab<sup>r</sup>''−1 के बड़े अभाज्य मापांक और 2 की घात, गुणक b के साथ एलसीजी के बराबर हैं।
 
एक [[क्रमपरिवर्तित सर्वांगसम जनरेटर|क्रमपरिवर्तित सर्वांगसम जनक]] 2-मापांक एलसीजी की घात से प्रारंभ होता है और कम-अनुक्रम बिट्स में छोटी अवधि की समस्या को दूर करने के लिए आउटपुट परिवर्तन अनुप्रयुक्त करता है।


==अन्य पीआरएनजी के साथ तुलना==
==अन्य पीआरएनजी के साथ तुलना==
लंबी अवधि के छद्म यादृच्छिक अनुक्रम प्राप्त करने के लिए व्यापक रूप से उपयोग किया जाने वाला अन्य आदिम रैखिक-प्रतिक्रिया शिफ्ट रजिस्टर निर्माण है, जो जीएफ (2) [x] में अंकगणित पर आधारित है, जो जीएफ (2) पर बहुपद रिंग है। पूर्णांक जोड़ और गुणा के बजाय, मूल संचालन अनन्य-या और कैरी-लेस गुणा होते हैं, जिन्हें आमतौर पर [[तार्किक बदलाव]]ों के अनुक्रम के रूप में कार्यान्वित किया जाता है। इनका लाभ यह है कि उनके सभी बिट पूर्ण-अवधि वाले हैं; वे निम्न-क्रम बिट्स में कमजोरी से पीड़ित नहीं हैं जो अंकगणित मॉड्यूलो 2 को परेशान करती है<sup></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>
दीर्घ अवधि के कूट यादृच्छिक अनुक्रम प्राप्त करने के लिए व्यापक रूप से उपयोग किया जाने वाला अन्य प्राथमिक रैखिक-प्रतिक्रिया विस्थापन पंजी निर्माण है, जो जीएफ (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> जैसे कि TestU01 सुइट में कार्यान्वित रैखिक जटिलता परीक्षण; एलएफएसआर के लगातार बिट्स से आरंभ किए गए एक बूलियन [[मैट्रिक्स का चक्कर लगाना]] में कभी भी बहुपद की डिग्री से अधिक [[रैंक (रैखिक बीजगणित)]] नहीं होगा। एक गैर-रेखीय आउटपुट मिक्सिंग फ़ंक्शन जोड़ने से (जैसे कि Xorshift#xoshiro256**|xoshiro256** और क्रमबद्ध सर्वांगसम जनरेटर निर्माण में) सांख्यिकीय परीक्षणों पर प्रदर्शन में काफी सुधार हो सकता है।
इस वर्ग के उदाहरणों में [[ 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> [[विलंबित फाइबोनैचि जनरेटर|विलंबित फाइबोनैचि जनक]] भी इसी श्रेणी में आते हैं; यद्यपि वे अंकगणितीय जोड़ का उपयोग करते हैं, उनकी अवधि सबसे कम महत्वपूर्ण बिट्स में से एक एलएफएसआर द्वारा सुनिश्चित की जाती है।


पीआरएनजी के लिए एक अन्य संरचना एक बहुत ही सरल पुनरावृत्ति फ़ंक्शन है जो एक शक्तिशाली आउटपुट मिक्सिंग फ़ंक्शन के साथ संयुक्त है। इसमें [[काउंटर मोड]] ब्लॉक सिफर और गैर-क्रिप्टोग्राफ़िक जेनरेटर जैसे [http://prng.di.unimi.it/splitmix64.c SplitMix64] शामिल हैं।
उचित परीक्षणों के साथ रैखिक-प्रतिक्रिया विस्थापन पंजी की संरचना का पता लगाना सरल है<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** और क्रमबद्ध सर्वांगसम जनक निर्माण में) जोड़ने से सांख्यिकीय परीक्षणों पर प्रदर्शन में काफी सुधार हो सकता है।


एलसीजी के समान एक संरचना, लेकिन समतुल्य नहीं, बहु-पुनरावर्ती जनरेटर है: एक्स<sub>n</sub>= (ए<sub>1</sub>X<sub>''n''−1</sub>+ ए<sub>2</sub>X<sub>''n''−2</sub>+····+ ए<sub>k</sub>X<sub>''n''−''k''</sub>) k ≥ 2 के लिए mod m। एक अभाज्य मापांक के साथ, यह m तक की अवधि उत्पन्न कर सकता है<sup>k</sup>−1, इसलिए यह बड़ी अवधियों के लिए LCG संरचना का एक उपयोगी विस्तार है।
पीआरएनजी के लिए एक अन्य संरचना एक बहुत ही सरल पुनरावृत्ति फलन है जो एक शक्तिशाली आउटपुट मिश्रित फलन के साथ संयुक्त है। इसमें [[काउंटर मोड|गुणक प्रणाली]] खंड आद्यक्षर और गैर-गूढ़ालेखी जनक जैसे [http://prng.di.unimi.it/splitmix64.c स्प्लिटमिक्स64] सम्मिलित हैं।


उच्च-गुणवत्ता वाली छद्म यादृच्छिक संख्याएँ उत्पन्न करने की एक शक्तिशाली तकनीक विभिन्न संरचना के दो या दो से अधिक पीआरएनजी को संयोजित करना है; एक एलएफएसआर और एक एलसीजी का योग (जैसा कि केआईएसएस (एल्गोरिदम) या एक्सोरशिफ्ट#xorwow निर्माण में) गति में कुछ लागत पर बहुत अच्छा प्रदर्शन कर सकता है।
एलसीजी के समान एक संरचना, परन्तु समतुल्य नहीं, बहु-पुनरावर्ती जनक: ''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)]] - ACG के साथ भ्रमित न हों, ऐसा प्रतीत होता है कि यह शब्द LCG और LFSR जनरेटर के वेरिएंट के लिए उपयोग किया गया है।
* [[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}}[[Category: छद्म यादृच्छिक संख्या जनरेटर]] [[Category: मॉड्यूलर अंकगणित]] [[Category: उदाहरण के लिए पायथन (प्रोग्रामिंग भाषा) कोड वाले लेख]]
{{DEFAULTSORT:Linear Congruential Generator}}
 
 


[[Category: Machine Translated Page]]
[[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

दो मापांक-9 एलसीजी दर्शाते हैं कि कैसे अलग-अलग मापदण्ड अलग-अलग चक्र लंबाई की ओर ले जाते हैं। प्रत्येक पंक्ति तब तक विकसित होती स्थिति को दर्शाती है जब तक वह दोहराई न जाए। शीर्ष पंक्ति m = 9, a = 2, c = 0 और 1 के मूल के साथ एक जनक दर्शाती है, जो लंबाई 6 का एक चक्र उत्पन्न करती है। दूसरी पंक्ति 3 के मूल के साथ एक ही जनक है, जो एक चक्र का उत्पादन करती है। लंबाई 2. a = 4 और c = 1 (नीचे पंक्ति) का उपयोग करने से [0, 8] में किसी भी मूल के साथ 9 की चक्र लंबाई मिलती है।

एक रैखिक सर्वांगसम जनक (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) + dax/2e⌋ के रूप में की जा सके। यदि परिणाम बहुत बड़ा है तो इसके बाद m का सशर्त घटाव होना चाहिए, परन्तु घटाव की संख्या ad/m तक सीमित है, जिसे d छोटा होने पर सरलता से एक तक सीमित किया जा सकता है।

यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है और गुणक को सावधानी से चुना गया है, तो श्रेज की विधि[12] का उपयोग किया जा सकता है। ऐसा करने के लिए, कारक m = qa+r, अर्थात q = m/a और r = m मॉड a है। फिर ax मॉड m = a(x mod q) − rx/q की गणना करें। चूँकि x मॉड q < q ≤ m/a, पहला पद am/a = m से बिल्कुल कम है। यदि a को इस प्रकार चुना जाता है कि r ≤ q (और इस प्रकार r/q ≤ 1), तो दूसरा पद भी m से कम rx/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 

  1. और सहअभाज्य पूर्णांक हैं,
  2. के सभी अभाज्य गुणनखंडों से विभाज्य है,
  3. 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

random0[25][26][27][28][29]

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 को वैकल्पिक किया जा सकेगा।

लाभ और हानि

एलसीजी तीव्र हैं और स्थिति को बनाए रखने के लिए न्यूनतम मेमोरी (एक मापांक-m संख्या, प्रायः 32 या 64 बिट्स) की आवश्यकता होती है। यह उन्हें कई स्वतंत्र धाराओं के अनुकरण के लिए मूल्यवान बनाता है। गूढ़लेखिकी अनुप्रयोगों के लिए एलसीजी का उद्दिष्ट नहीं है और इसका उपयोग नहीं किया जाना चाहिए; ऐसे अनुप्रयोगों के लिए गूढ़लेखिकी रूप से सुरक्षित कूट यादृच्छिक संख्या जनक का उपयोग करें।

तीन आयामों में एक रैखिक सर्वांगसम जनक के अधिसमतल है। वर्णक्रमीय परीक्षण इसी संरचना को मापता है।

हालाँकि एलसीजी में कुछ विशिष्ट दोष हैं, परन्तु उनकी कई खामियाँ बहुत छोटी स्थिति के कारण आती हैं। तथ्य यह है कि लोगों को इतने सालों से ऐसे छोटे गुणांक के साथ उपयोग करने के लिए प्रेरित किया गया है, इसे प्रविधि के गुण के प्रमाण के रूप में देखा जा सकता है। पर्याप्त बड़े अवस्था वाले एलसीजी कड़े सांख्यिकीय परीक्षणों को भी पारित कर सकता है; एक मापांक-2 एलसीजी जो उच्च 32 बिट्स लौटाता है, परीक्षणयू01 के छोटे क्रश समूह से गुजरता है,[citation needed] और 96-बिट एलसीजी सबसे कड़े बड़े क्रश समूह से गुजरता है।[32]

एक विशिष्ट उदाहरण के लिए, 32 बिट आउटपुट के साथ एक आदर्श यादृच्छिक संख्या जनक से (बर्थ्डै प्रमेय के अनुसार) m ≈ 216 परिणामों के बाद पहले के आउटपुट को अनुलिपि करना, प्रारंभ करने की आशा की जाती है। कोई भी पीआरएनजी जिसका आउटपुट उसकी पूर्ण, असंतुलित स्थिति है, तब तक अनुलिपि उत्पन्न नहीं करेगा जब तक कि उसकी सम्पूर्ण अवधि समाप्त न हो जाए, यह एक सरलता से पता लगाने योग्य सांख्यिकीय दोष है। संबंधित कारणों से, किसी भी पीआरएनजी की अवधि आवश्यक आउटपुट की संख्या के वर्ग से अधिक होनी चाहिए। आधुनिक परिकलक गति को देखते हुए, इसका अर्थ है कि कम से कम मांग वाले अनुप्रयोगों को छोड़कर सभी के लिए 264 की अवधि, और मांग वाले अनुकरण के लिए दीर्घ अवधि है।

एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि n-आयामी समष्टि में बिंदुओं को चुनने के लिए उपयोग किया जाता है, तो बिंदु अधिक-से-अधिक, nn!⋅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 + ··· + akXnk), k ≥ 2 के लिए मॉड m है। एक प्रमुख मापांक के साथ, यह हो सकता है, mk−1 तक की अवधि उत्पन्न कर सकता है, इसलिए यह बड़ी अवधियों के लिए एलसीजी संरचना का एक उपयोगी विस्तार है।

उच्च-गुणवत्ता वाली कूट यादृच्छिक संख्याएँ उत्पन्न करने की एक शक्तिशाली प्रविधि विभिन्न संरचना के दो या दो से अधिक पीआरएनजी को संयोजित करना है; एक एलएफएसआर और एक एलसीजी का योग (जैसा कि केआईएसएस या एक्सोरवॉव निर्माण में होता है) गति में कुछ लागत पर बहुत अच्छा प्रदर्शन कर सकता है।

यह भी देखें

टिप्पणियाँ

  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. 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.
  3. Lehmer, Derrick H. (1951). "बड़े पैमाने की कंप्यूटिंग इकाइयों में गणितीय तरीके". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.
  4. Thomson, W. E. (1958). "छद्म-यादृच्छिक संख्याएँ उत्पन्न करने की एक संशोधित सर्वांगसमता विधि". The Computer Journal. 1 (2): 83. doi:10.1093/comjnl/1.2.83.
  5. Rotenberg, A. (1960). "एक नया छद्म-यादृच्छिक संख्या जेनरेटर". Journal of the ACM. 7 (1): 75–77. doi:10.1145/321008.321019. S2CID 16770825.
  6. 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. 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.
  8. 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.
  9. 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. 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. 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.
  12. Jain, Raj (9 July 2010). "Computer Systems Performance Analysis Chapter 26: Random-Number Generation" (PDF). pp. 19–20. Retrieved 2017-10-31.
  13. Fenerty, Paul (11 September 2006). "Schrage's Method". Retrieved 2017-10-31.
  14. 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.
  15. Severance, Frank (2001). System Modeling and Simulation. John Wiley & Sons, Ltd. p. 86. ISBN 978-0-471-49694-6.
  16. Austin, David (March 2008). "Random Numbers: Nothing Left to Chance". American Mathematical Society.
  17. 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.
  18. 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.
  19. "Last public Committee Draft from April 12, 2011" (PDF). p. 346f. Retrieved 21 Dec 2014.
  20. "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.
  21. 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. 22.0 22.1 "ISO/IEC 14882:2011". ISO. 2 September 2011. Retrieved 3 September 2011.
  23. "Creating and Controlling a Random Number Stream". MathWorks. Retrieved 7 June 2021.
  24. "GNU Scientific Library: Other random number generators".
  25. Stephen J. Chapman. "Example 6.4 – Random Number Generator". "MATLAB Programming for Engineers". 2015. pp. 253–256.
  26. Stephen J. Chapman. "Example 6.4 – Random Number Generator". "MATLAB Programming with Applications for Engineers". 2012. pp. 292–295.
  27. S. J. Chapman. random0. 2004.
  28. Stephen J. Chapman. "Introduction to Fortran 90/95". 1998. pp. 322–324.
  29. Wu-ting Tsai. "'Module': A Major Feature of the Modern Fortran". pp. 6–7.
  30. The Open Group Base Specifications Issue 7 IEEE Std 1003.1, 2013 Edition
  31. Cadot, Sidney. "rand.s". cc65. Retrieved 8 July 2016.
  32. 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.
  33. 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.
  34. 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.
  35. Gershenfeld, Neil (1999). "Section 5.3.2: Linear Feedback". गणितीय मॉडलिंग की प्रकृति (First ed.). Cambridge University Press. p. 59. ISBN 978-0-521-57095-4.
  36. 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.
  37. 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.


संदर्भ


बाहरी संबंध