👨🏿‍🎤 📊 🦐 हाई बिट रैंडम नंबर जनरेशन 🏡 🙎🏼 🛀🏿

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

इस पोस्ट में, हम ऑपरेशन के सिद्धांत और मापदंडों के चयन की व्याख्या के साथ 64 और 128 बिट्स के बिट्स के छद्म-यादृच्छिक संख्या प्राप्त करने के लिए रैखिक बधाई विधि के आवेदन पर ध्यान केंद्रित करेंगे।

यदि आप मानक पुस्तकालय से आरएनजी का उपयोग करने के लिए एक बोझ हैं, तो आपके पास इसके लिए गैर-मानक आवश्यकताएं हैं या बस अपने आवेदन में यादृच्छिक संख्या उत्पन्न करने की पूरी प्रक्रिया को नियंत्रित करना चाहते हैं, बिल्ली का स्वागत है।

मानक जनरेटर के साथ नीचे!

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

सभी काफी सामान्य प्रोग्रामिंग भाषाओं में यादृच्छिक (या, अत्यंत सटीक, छद्म आयामी) संख्या उत्पन्न करने के लिए कार्य हैं। हालांकि, कभी-कभी अपने स्वयं के यादृच्छिक संख्या जनरेटर (आरएनजी) को लागू करना आवश्यक हो जाता है। यद्यपि RNG "बॉक्स से बाहर" आमतौर पर ज्यादातर मामलों में उपयोग के लिए पर्याप्त होता है, यह भी होता है कि एक जनरेटर जो बहुत ठंडा होता है, उसकी आवश्यकता नहीं लगती है, लेकिन अंतर्निहित RNG अभी भी सुखद नहीं है।

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

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

एक कार्य उत्पन्न हो सकता है जिसमें विभिन्न आरएनजी का एक साथ संचालन आवश्यक है। यह अलग है, और अंतर्निहित जनरेटर आमतौर पर एक है। आप निश्चित रूप से विभिन्न प्रारंभिक अनाज के साथ कई प्रतियां चला सकते हैं, लेकिन इस मामले में, जनरेटर एक ही अनुक्रम के तत्वों का उत्पादन करेंगे (जो कि चक्रीय रूप से दोहराता है) बस विभिन्न स्थानों से शुरू होता है। चक्र की लंबाई बड़ी है, लेकिन सैद्धांतिक रूप से यह समस्याएं पैदा कर सकता है।

मेरे मामले में, 128-बिट संख्या उत्पन्न करना आवश्यक था। C ++ में, कोई फ़ंक्शन नहीं है जो कम से कम 64-बिट लौटाता है। एक लंबी गुगली के बाद, मुझे विभिन्न कंपाइलरों में रैंड () और RAND_MAX में भ्रम मिला, 64 बिट्स उत्पन्न करने के लिए बैसाखी का एक सेट, और अंतर्निहित आरएनजी को छोड़ने का फैसला किया। मेरे जनरेटर को लिखना मुझे एक प्राथमिक कार्य लगता था - एक रैखिक संयोजक जनरेटर के पुनरावृत्तियों के एक जोड़े के लिए दो 64-बिट संख्या प्राप्त करने के लिए, और फिर उन्हें गोंद। यह इतना सरल नहीं था। लेकिन सबसे पहली बात।

कारण के लिए!

तो, चलिए RNG बनाना शुरू करते हैं। आधार के रूप में, आइए एक सरल और लोकप्रिय रैखिक सर्वांगी विधि लें जो सूत्र के अनुसार काम करती है:

जहां x _i , x _{i + 1} - वर्तमान और अगला यादृच्छिक संख्या; a , c और m कुछ स्थिरांक हैं; mod - शेष भाग को खोजने के लिए ऑपरेटर।

सॉफ़्टवेयर कार्यान्वयन में विभाजन से बचने के लिए निरंतर मी को अक्सर 2 ³² या 2 ^{64 के} बराबर लिया जाता है। परिणामस्वरूप 64-बिट अवशेष प्राप्त करने के लिए, मैंने m = 2 ^{64 का} उपयोग किया। लेकिन कॉन्स्टेंट को ए और सी कहां मिलेगा? निम्नलिखित युग्म विकिपीडिया पर पाया गया: a = 6364136223846793005 और c = 1442695040888963407। दो बार सोचने के बिना, मैंने इन मापदंडों का उपयोग करके एक जनरेटर लिखा, और अपने आनुवंशिक एल्गोरिथ्म का परीक्षण करना शुरू किया। हालांकि, वह जल्दी से साइकिल में चला गया। आरजीजी पर संदेह गिर गया। यह पता चला है कि 64-बिट "यादृच्छिक" संख्याओं के परिणामस्वरूप अनुक्रम के कुछ कम महत्वपूर्ण बिट्स बिना किसी यादृच्छिक व्यवहार के दिखाए गए हैं। मोनोक्रोम चित्रों के रूप में लगातार संख्याओं के कुछ बाइनरी अंकों के मूल्यों को दिखाया गया है:

निचले 5 वें, 15 वें और 20 वें अंकों के मान (खरोंच से क्रमांकन)

लगभग 20-24 लो-ऑर्डर बाइनरी बिट्स उपयोग के लिए उपयुक्त नहीं हैं। जैसे-जैसे डिस्चार्ज की संख्या बढ़ती है, इसकी यादृच्छिकता बढ़ती जाती है। इस प्रकार, एक 64-बिट यादृच्छिक संख्या प्राप्त करने के लिए, एक रैखिक बधाई जनरेटर के दो पुनरावृत्तियों आवश्यक हैं। परिणाम दो 32-बिट अंशों का संघटन है:

उदाहरण के लिए, java.util.Random एक ही सिद्धांत का उपयोग करता है, हालाँकि इस तथ्य के कारण कि m = 2 ⁴⁸ , केवल 16 लो-ऑर्डर बिट्स को int और long बनाते समय छोड़ दिया जाता है। यह, ज़ाहिर है, यादृच्छिक संख्याओं की गुणवत्ता को नकारात्मक रूप से प्रभावित करता है।

यहाँ 64-बिट संख्याओं के अनुक्रम का एक उदाहरण दिया गया है, जो कि = 6364136223846793005, c = 1442695040888963407, m = 2 ⁶⁴ , x ₀ = 0 के साथ प्राप्त किया गया है, जो चित्र में वर्णित है:

1442695037175000593
11166244415259155177
7076646891078057782
1459328390042580878
8905969149530007863
11682375496967736740
897247724006084730

ये संख्या कितनी यादृच्छिक है? मानक जावा लाइब्रेरी से आरएनजी स्तर के बारे में, शायद थोड़ा बेहतर भी हो। प्रत्येक संख्या की गणना के लिए गुणन के केवल दो संचालन की आवश्यकता होती है।

यदि आपको कई अलग-अलग जनरेटर की आवश्यकता है, तो आपको m = 2 ⁶⁴ पर गणना की गई स्थिरांक के अन्य मानों को चुनना चाहिए। यहाँ लेख "अच्छे गुणों" के साथ तीन स्थिरांक के उदाहरण प्रदान करता है:

a = 2862933555777941757	सी - विषम, एम = 2 ⁶⁴
a = 3202034522624059733
a = 3935559000370003845

128 बिट यादृच्छिक संख्या

दो 64-बिट संख्याओं को एक में मिलाने में कुछ भी जटिल नहीं है, हालांकि, एक दिलचस्प बिंदु है: 64 बिट्स की दो संख्याओं की एक साथ पीढ़ी क्रमिक की तुलना में 25% तेज हो सकती है, उनके "यादृच्छिकता" के लिए थोड़ा नुकसान नहीं है। "।

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

यदि आपको अचानक आश्चर्य होता है कि यह कोड में कैसा दिखता है।

class RandomGenerator { public: RandomGenerator(unsigned long long int seed = 0); void next(unsigned long long int *hi, unsigned long long int * lo); private: unsigned long long int currentSeed; }; RandomGenerator::RandomGenerator(unsigned long long int seed) : currentSeed(seed) {} void RandomGenerator::next(unsigned long long int *hi, unsigned long long int *lo) { const unsigned long long int a = 6364136223846793005; const unsigned long long int c = 1442695040888963407; const unsigned long long int x = a * this->currentSeed + c; const unsigned long long int y = a * x + c; const unsigned long long int z = a * y + c; *hi = (x & 0xfffffffffff00000) | (z >> 44); *lo = (y & 0xfffffffffff00000) | ((z >> 24) & 0xfffff); this->currentSeed = z; }

एक ही पैरामीटर का उपयोग करते हुए, c , m और x ₀ , निम्न संख्याएँ प्राप्त की हैं:

26613026195691280501944396807868523054
136526799440480448897747671965175330512
26919857327062567305005081067174740455
151962490054994640693408155996993201355
16551299175504952598134597160493279376
67275013191410065527820230898073478166
72445587156806476974393951227561270647

यादृच्छिक संख्या निकालने की यह विधि मेरे आवेदन के काम करने के लिए पर्याप्त थी। यह जल्दी और व्यावहारिक निकला। निश्चित रूप से लेख की जानकारी किसी के लिए उपयोगी होगी। यह सब, आपके ध्यान के लिए धन्यवाद। ( कवर पर क्यूब्स के साथ तस्वीर यहां से ली गई है । )

सभी को नया साल मुबारक हो!

हाई बिट रैंडम नंबर जनरेशन

मानक जनरेटर के साथ नीचे!

कारण के लिए!

128 बिट यादृच्छिक संख्या

More articles: