रैखिक सर्वांगसम जनक

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

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

जनक को पुनरावृत्ति संबंध द्वारा परिभाषित किया गया है:

$X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}$

जहाँ $X$ कूट-यादृच्छिक मानों का क्रम है, और

$m,\,0<m$ - "मापांक"

$a,\,0<a<m$ - "गुणक"

$c,\,0\leq c<m$ - "वृद्धि"

$X_{0},\,0\leq X_{0}<m$ - "मूल" या "प्रारंभ मान"

पूर्णांक स्थिरांक हैं जो जनक को निर्दिष्ट करते हैं। यदि c = 0 है, तो जनक को प्रायः गुणक सर्वांगसम जनक (MCG), या लेहमर आरएनजी कहा जाता है। यदि c ≠ 0 है, तो विधि को मिश्रित सर्वांगसम जनक कहा जाता है।

जब c ≠ 0, एक गणितज्ञ पुनरावृत्ति को एक रैखिक परिवर्तन नहीं, बल्कि एक सजातीय परिवर्तन कहेगा, परन्तु परिकलक विज्ञान में यह मिथ्या नाम अच्छी तरह से स्थापित है।

इतिहास

लेहमर जनक 1951 में प्रकाशित हुआ था और रैखिक सर्वांगसम जनक 1958 में डब्ल्यू. ई. थॉमसन और ए. रोटेनबर्ग द्वारा प्रकाशित किया गया था।

अवधि

एलसीजी का एक लाभ यह है कि मापदंडों के उचित चयन से एक ऐसी अवधि प्राप्त होती है जो ज्ञात और दीर्घ दोनों होती है। हालांकि यह एकमात्र मानदंड नहीं है, बहुत छोटी अवधि कूट-यादृच्छिक संख्या जनक में एक घातक दोष है।

जबकि एलसीजी कूट-यादृच्छिक संख्याएं उत्पन्न करने में सक्षम हैं जो यादृच्छिकता के लिए औपचारिक परीक्षण पारित कर सकते हैं, आउटपुट की गुणवत्ता मापदण्ड m और a के चयन के प्रति अत्यधिक संवेदनशील है। उदाहरण के लिए, a = 1 और c = 1 एक साधारण मापांक-m गुणक का निर्माण करता है, जिसकी दीर्घ अवधि होती है, परन्तु यह स्पष्ट रूप से गैर-यादृच्छिक है।

ऐतिहासिक रूप से, खराब विकल्पों के कारण एलसीजी का कार्यान्वयन अप्रभावी हो गया है। इसका एक विशेष उदाहरण आरएएनडीयू है, जिसका 1970 के दशक के प्रारंभ में व्यापक रूप से उपयोग किया गया था और इसके कई परिणाम सामने आए थे, जिन पर वर्तमान में इस खराब एलसीजी के उपयोग के कारण प्रश्न उठाए जा रहे हैं।

मापदण्ड चयन के तीन सामान्य वर्ग हैं:

m अभाज्य, c = 0

Main article: लेहमर यादृच्छिक संख्या जनित्र

यह मूल लेहमर आरएनजी निर्माण है। यदि गुणक a को पूर्णांक गुणांक m का एक पूर्वग अवयव चुना जाता है, तो अवधि m−1 है। प्रारंभिक अवस्था को 1 और m−1 के मध्य चुना जाना चाहिए।

अभाज्य गुणांक की एक हानि यह है कि प्रमापीय कमी के लिए दोगुनी-चौड़ाई वाले उत्पाद और एक स्पष्ट न्यूनीकरण चरण की आवश्यकता होती है। प्रायः 2 की घात से कम अभाज्य का उपयोग किया जाता है (मेरसेन अभाज्य 2³¹−1 और 2⁶¹−1 लोकप्रिय हैं), ताकि न्यूनीकरण मापांक m = 2^e − d की गणना (ax मॉड 2) + d ⌊ax/2^e⌋ के रूप में की जा सके। यदि परिणाम बहुत बड़ा है तो इसके बाद m का सशर्त घटाव होना चाहिए, परन्तु घटाव की संख्या ad/m तक सीमित है, जिसे d छोटा होने पर सरलता से एक तक सीमित किया जा सकता है।

यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है और गुणक को सावधानी से चुना गया है, तो श्रेज की विधि का उपयोग किया जा सकता है। ऐसा करने के लिए, कारक 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] तक कम किया जा सकता है।

दूसरी हानि यह है कि मान 1 ≤ x < m को समान यादृच्छिक बिट्स में परिवर्तित करना अनुपयुक्त है। यदि 2 की घात से कम अभाज्य का उपयोग किया जाता है, तो कभी-कभी लुप्त मानों को सरलता से उपेक्षित कर दिया जाता है।

m 2 की घात, c = 0

m को 2 की घात के रूप में चुनना, प्रायः m = 2³² या m = 2⁶⁴, एक विशेष रूप से कुशल एलसीजी उत्पन्न करता है, क्योंकि यह केवल द्विचर प्रतिनिधित्व को छोटा करके मापांक संचालन की गणना करने की अनुमति देता है। वास्तव में, सबसे महत्वपूर्ण बिट्स की सामान्यतः गणना ही नहीं की जाती है। हालाँकि, इसकी हानि भी हैं।

इस विधि में अधिकतम अवधि m/4 है, जो a ≡ 3 या a ≡ 5 (मॉड 8) होने पर प्राप्त होती है। प्रारंभिक अवस्था X₀ विषम होना चाहिए और X के निम्न तीन बिट दो स्थितियों के मध्य वैकल्पिक होते हैं और उपयोगी नहीं होते हैं। यह दर्शाया जा सकता है कि यह विधि एक जनक के बराबर है जिसका मापांक एक चौथाई आकार और c ≠ 0 है।

2 की घात के मापांक के उपयोग के साथ एक अधिक जटिल विवाद यह है कि कम बिट्स की अवधि उच्च बिट्स की तुलना में कम होती है। X का निम्नतम क्रम वाला बिट कभी परिवर्तित नहीं होता है (X सदैव विषम होता है) और अगले दो बिट दो स्थितियों के मध्य वैकल्पिक होते हैं। यदि a≡5 (मॉड 8) है, तो बिट 1 कभी परिवर्तित नहीं होता है और बिट 2 परिवर्तित होता है। यदि a≡3 (मॉड 8) है, तो बिट 2 कभी परिवर्तित नहीं होता है और बिट 1 परिवर्तित होता है। बिट 3, 4 की अवधि के साथ दोहराता है, बिट 4 का आवर्त 8 है, इत्यादि। केवल X का सबसे महत्वपूर्ण बिट ही पूर्ण अवधि प्राप्त करता है।

c ≠ 0

जब c ≠ 0, सही ढंग से चुने गए मापदण्ड सभी मूल मानों के लिए m के बराबर अवधि की अनुमति देते हैं। यह तब घटित होगा जब और केवल यदि:

1. $m$ और $c$ सहअभाज्य पूर्णांक हैं,
2. $a-1$ के सभी अभाज्य गुणनखंडों से विभाज्य $m$ है,
3. $a-1$ 4 से विभाज्य है यदि $m$, 4 से विभाज्य है।

इन तीन आवश्यकताओं को हल-डोबेल प्रमेय के रूप में जाना जाता है।

इस विधि का उपयोग किसी भी m के साथ किया जा सकता है, परन्तु यह केवल m के लिए कई दोहराए गए अभाज्य कारकों के साथ ही अच्छा कार्य करता है, जैसे कि 2 की घात; परिकलक के शब्द आकार का उपयोग करना सबसे सामान्य विकल्प है। यदि m एक वर्ग-मुक्त पूर्णांक होता, तो यह केवल ≡ 1 (मॉड m) की अनुमति देता, जो बहुत खराब पीआरएनजी बनाता है; संभावित पूर्ण-अवधि गुणकों का चयन केवल तभी उपलब्ध होता है जब m में अभाज्य गुणनखंड दोहराए जाते हैं।

यद्यपि हल-डोबेल प्रमेय अधिकतम अवधि प्रदान करता है, यह एक अच्छे जनक की प्रत्याभूति देने के लिए पर्याप्त नहीं है। उदाहरण के लिए, यह वांछनीय है कि a − 1, m के अभाज्य गुणनखंडों द्वारा आवश्यकता से अधिक विभाज्य न हो। इस प्रकार, यदि m, 2 की घात है, तो a − 1 को 4 से विभाज्य होना चाहिए, परन्तु 8 से विभाज्य नहीं होना चाहिए, अर्थात a ≡ 5 (मॉड 8)।

वास्तव में, अधिकांश गुणक एक अनुक्रम उत्पन्न करते हैं जो गैर-यादृच्छिकता या किसी अन्य के लिए एक परीक्षण में विफल रहता है, और एक ऐसा गुणक ढूंढता है जो सभी अनुप्रयुक्त मानदंडों के लिए संतोषजनक हो, काफी चुनौतीपूर्ण है। वर्णक्रमीय परीक्षण सबसे महत्वपूर्ण परीक्षणों में से एक है।

ध्यान दें कि 2 की घात के मापांक c = 0 के लिए ऊपर वर्णित समस्या को साझा करता है: निम्न k बिट्स मापांक 2^k के साथ एक जनक बनाते हैं और इस प्रकार 2^k की अवधि के साथ दोहराते हैं; केवल सबसे महत्वपूर्ण बिट ही पूर्ण अवधि को प्राप्त करता है। यदि r से कम कूट-यादृच्छिक संख्या वांछित है, ⌊rX/m⌋ X मॉड r की तुलना में बहुत उच्च गुणवत्ता वाला परिणाम है। दुर्भाग्य से, अधिकांश क्रमादेश भाषाएँ बाद वाले (X % r) को लिखना बहुत सरल बना देती हैं, इसलिए यह अधिक सामान्यतः उपयोग की जाने वाली विधि है।

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

C के अन्य विकल्पों द्वारा निर्मित श्रृंखला को श्रृंखला के एक सामान्य फलन के रूप में लिखा जा सकता है जब c=1 है। विशेष रूप से, यदि Y, Y₀ = 0 और Y_n+1 = aY_n+1 मॉड m द्वारा परिभाषित प्रोटोटाइप श्रृंखला है, तो एक सामान्य श्रृंखला X_n+1 = X_n+c मॉड m को Y के एफ़िन फलन के रूप में लिखा जा सकता है:

$X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}$

अधिक सामान्यतः, समान गुणक और मापांक वाली किन्हीं दो श्रृंखलाओं X और Z से संबंधित हैं।

${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}}$

सामान्य उपयोग में मापदण्ड

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

स्रोत	गुणांक m	गुणक a	वृद्धि c	रैंड () या रैंडम (L) में मूल के आउटपुट बिट्स
जेडएक्स81	216 + 1	75	74
"त्वरित और ख़राब जनक" सूची से संख्यात्मक व्यंजन , अध्याय 7.1, समीकरण- 7.1.6 नुथ और एच. डब्ल्यू. लुईस से मापदण्ड	232	1664525	1013904223
बोरलैंड सी/सी++	232	22695477	1	रैंड() में बिट्स 30..16, लैरैंड() में 30..0
ग्लिबीसी (जीसीसी द्वारा प्रयुक्त)	231	1103515245	12345	बिट्स 30..0
एएनएसआई सी: वाटकॉम, डिजिटल मार्स, कोडवॉरियर, आईबीएम विजुअलएज सी/सी++ सी90, सी99, सी11: आईएसओ/आईईसी 9899 में सुझाव, सी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 और पूर्व)	224	1140671485 (43एफडी43एफडी16)	12820163 (सी39ईसी316)
नेटिव एपीआई से आरटीएलयूनिफ़ॉर्म	231 − 1	2147483629 (7एफएफएफएफएफईडी16)	2147483587 (7एफएफएफएफएफसी316)
एप्पल कार्बनलिब, सी++11 का minstd_rand0, एमएटीएलएबी का वी4 लीगेसी जनक एमसीजी16807	231 − 1	16807	0	एमआईएनएसटीडी देखें
सी++11 का minstd_rand	231 − 1	48271	0	एमआईएनएसटीडी देखें
डोनाल्ड नुथ द्वारा एमएमआईएक्स	264	6364136223846793005	1442695040888963407
न्यूलिब	264	6364136223846793005	1	बिट्स 62..32 (16-बिट इंट के लिए 46..32)
मसल	264	6364136223846793005	1	बिट्स 63..33
वीएमएस का एमटीएच$आरएएनडीओएम, ग्लिबीसी का पुराना संस्करण	232	69069 (10डीसीडी16)	1
जावा का जावा.यूटिल.रैन्डम, पीओएसआईएक्स [ln]रैंड48, ग्लिबीसी [ln]रैंड 48[_r]	248	25214903917 (5डीईसीई66डी16)	11	बिट्स 47..16
random0	134456 = 2375	8121	28411	${\frac {X_{n}}{134456}}$
पीओएसआईएक्स [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	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
पूर्व में सामान्य: आरएएनडीयू	231	65539	0

जैसा कि ऊपर दर्शाया गया है, एलसीजी सदैव अपने द्वारा उत्पादित मानों में सभी बिट्स का उपयोग नहीं करते हैं। उदाहरण के लिए, जावा कार्यान्वयन प्रत्येक पुनरावृत्ति पर 48-बिट मानों के साथ संचालित होता है, परन्तु केवल उनके 32 सबसे महत्वपूर्ण बिट्स लौटाता है। ऐसा इसलिए है क्योंकि उच्च-क्रम वाले बिट्स की अवधि निचले-क्रम वाले बिट्स की तुलना में लंबी होती है (नीचे देखें)। एलसीजी जो इस खंडन प्रविधि का उपयोग करते हैं, वे उन लोगों की तुलना में सांख्यिकीय रूप से श्रेष्ठतर मान उत्पन्न करते हैं जो ऐसा नहीं करते हैं। यह उन आलेखों में विशेष रूप से ध्यान देने योग्य है जो पंक्ति श्रृंखला को कम करने के लिए मॉड संक्रिया का उपयोग करते हैं; यादृच्छिक संख्या मॉड 2 को संशोधित करने से बिना किसी खंडन के 0 और 1 को वैकल्पिक किया जा सकेगा।

लाभ और हानि

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

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

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

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

एलसीजी के लिए विशिष्ट एक दोष यह है कि, यदि n-आयामी समष्टि में बिंदुओं को चुनने के लिए उपयोग किया जाता है, तो बिंदु अधिक-से-अधिक, ⁿ√n!⋅m अधिसमतल (मार्सग्लिया का प्रमेय, जॉर्ज मार्साग्लिया द्वारा विकसित) पर स्थित होंगे। यह अनुक्रम X_n के क्रमिक मानों के मध्य क्रमिक सहसंबंध के कारण है। असावधानतः चुने गए गुणकों में सामान्यतः बहुत कम, व्यापक दूरी वाले विमान होंगे, जिससे समस्याएं उत्पन्न हो सकती हैं। वर्णक्रमीय परीक्षण, जो एलसीजी की गुणवत्ता का एक सरल परीक्षण है, इस अंतर को मापता है और एक अच्छे गुणक को चुनने की अनुमति देता है।

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

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

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

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

प्रतिदर्श कोड

पायथन कोड

जनक के रूप में, पायथन में एलसीजी का कार्यान्वयन निम्नलिखित है:

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=2^w और पश्चता r और s (r > s) के साथ b^r ± b^s ± 1 के मापांक के साथ एलसीजी के बराबर हैं।

a के गुणक के साथ गुणन के साथ ऋणी पीआरएनजी, ab^r−1 के बड़े अभाज्य मापांक और 2 की घात, गुणक b के साथ एलसीजी के बराबर हैं।

एक क्रमपरिवर्तित सर्वांगसम जनक 2-मापांक एलसीजी की घात से प्रारंभ होता है और कम-अनुक्रम बिट्स में छोटी अवधि की समस्या को दूर करने के लिए आउटपुट परिवर्तन अनुप्रयुक्त करता है।

अन्य पीआरएनजी के साथ तुलना

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

इस वर्ग के उदाहरणों में एक्सोरशिफ्ट जनक और मेरसेन ट्विस्टर सम्मिलित हैं। उत्तरार्द्ध एक बहुत दीर्घ अवधि (2¹⁹⁹³⁷−1) प्रदान करता है और विविधतापूर्ण एकरूपता प्रदान करता है, परन्तु यह कुछ सांख्यिकीय परीक्षणों में विफल रहता है। विलंबित फाइबोनैचि जनक भी इसी श्रेणी में आते हैं; यद्यपि वे अंकगणितीय जोड़ का उपयोग करते हैं, उनकी अवधि सबसे कम महत्वपूर्ण बिट्स में से एक एलएफएसआर द्वारा सुनिश्चित की जाती है।

उचित परीक्षणों के साथ रैखिक-प्रतिक्रिया विस्थापन पंजी की संरचना का पता लगाना सरल है जैसे कि परीक्षणयू01 समूह में कार्यान्वित रैखिक जटिलता परीक्षण; एलएफएसआर के लगातार बिट्स से आरंभ किए गए एक बूलियन परिचालित आव्यूह की श्रेणी कभी भी बहुपद की डिग्री से अधिक नहीं होगी। एक गैर-रेखीय आउटपुट मिश्रित फलन (जैसे कि एक्सओशिरो256** और क्रमबद्ध सर्वांगसम जनक निर्माण में) जोड़ने से सांख्यिकीय परीक्षणों पर प्रदर्शन में काफी सुधार हो सकता है।

पीआरएनजी के लिए एक अन्य संरचना एक बहुत ही सरल पुनरावृत्ति फलन है जो एक शक्तिशाली आउटपुट मिश्रित फलन के साथ संयुक्त है। इसमें गुणक प्रणाली खंड आद्यक्षर और गैर-गूढ़ालेखी जनक जैसे स्प्लिटमिक्स64 सम्मिलित हैं।

एलसीजी के समान एक संरचना, परन्तु समतुल्य नहीं, बहु-पुनरावर्ती जनक: X_n = (a₁X_n−1 + a₂X_n−2 + ··· + a_kX_n−k), k ≥ 2 के लिए मॉड m है। एक प्रमुख मापांक के साथ, यह हो सकता है, m^k−1 तक की अवधि उत्पन्न कर सकता है, इसलिए यह बड़ी अवधियों के लिए एलसीजी संरचना का एक उपयोगी विस्तार है।

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

यह भी देखें

• यादृच्छिक संख्या जनकों की सूची - श्रेष्ठतर सांख्यिकीय गुणवत्ता वाले कुछ सहित अन्य पीआरएनजी
• एसीओआरएन (पीआरएनजी) - एसीजी के साथ भ्रमित न हों, ऐसा प्रतीत होता है कि यह शब्द एलसीजी और एलएफएसआर जनक के भिन्नरूप के लिए उपयोग किया गया है।
• क्रमपरिवर्तित सर्वांगसम जनक
• सम्पूर्ण चक्र
• व्युत्क्रम सर्वांगसम जनक
• गुणन-के-साथ-ऋणी
• लेहमर आरएनजी (कभी-कभी पार्क-मिलर आरएनजी भी कहा जाता है)
• संयुक्त रैखिक सर्वांगसम जनक

संदर्भ

• 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