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

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

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

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

$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), या लेहमर RNG कहा जाता है। यदि c ≠ 0 है, तो विधि को 'मिश्रित सर्वांगसम जनक' कहा जाता है।

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

इतिहास

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

अवधि की लंबाई

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

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

एम अभाज्य, सी = 0

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

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

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

यदि दोगुनी-चौड़ाई वाला उत्पाद उपलब्ध नहीं है, और गुणक सावधानी से चुना गया है, तो 'श्रेज विधि' उपयोग किया जा सकता है। ऐसा करने के लिए, कारक m = qa+r, यानी। q = ⌊m/a⌋ और r = m mod a. फिर ax mod m = की गणना करें a(x mod q) − r⌊x/q⌋. चूँकि x mod 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 को दो की घात के रूप में चुनने पर, प्रायः m = 2 होता है³²या एम = 2⁶⁴, एक विशेष रूप से कुशल एलसीजी का उत्पादन करता है, क्योंकि यह केवल द्विचर प्रतिनिधित्व को छोटा करके गुणांकस संक्रिया की गणना करने की अनुमति देता है। वास्तव में, सबसे महत्वपूर्ण बिट्स की सामान्यतः गणना ही नहीं की जाती है। हालाँकि, इसके हानि भी हैं।

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

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

सी ≠ 0

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

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

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

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

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

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

C के अन्य विकल्पों द्वारा निर्मित श्रृंखला को श्रृंखला के एक सरल कार्य के रूप में लिखा जा सकता है जब c=1। विशेष रूप से, यदि Y, Y द्वारा परिभाषित प्रोटोटाइप श्रृंखला है₀ = 0 और Y_n+1 = एवाई_n+1 मॉड मी, फिर एक सामान्य श्रृंखला एक्स_n+1 = एक्स_n+c mod 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
Formerly common: RANDU	231	65539	0

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

फायदे और हानि

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

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

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

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

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

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

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

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

निःशुल्क पास्कल

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

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 है^{डब्ल्यू} और लैग्स आर और एस (आर > एस) बी के मापांक के साथ एलसीजी के बराबर हैं^आर±बी^स±1. ए के गुणक के साथ गुणन-के-साथ-ले जाना पीआरएनजी, एब के बड़े प्राइम मापांक के साथ एलसीजी के बराबर हैं^r−1 और एक पावर-ऑफ-2 गुणक बी।

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

• 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