कोई भी यादृच्छिक पूर्णांक उत्पन्न करें

Dec 28 2020

मैं अग्रिम में माफी चाहता हूं क्योंकि मैं यादृच्छिकता की किसी भी औपचारिक धारणा के साथ बहुत अनुभवी नहीं हूं।

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

यदि आप किसी भी वास्तविक संख्या को बेतरतीब ढंग से उत्पन्न कर सकते हैं तो आप किसी भी पूर्णांक को उत्पन्न करने के लिए फर्श फ़ंक्शन जैसे कार्यों का उपयोग कर सकते हैं। यदि आप किसी भी अंतराल के बीच किसी भी वास्तविक संख्या को यादृच्छिक रूप से उत्पन्न कर सकते हैं$[a,b]$, तो आप जैसे विषमतावादी कार्यों का उपयोग कर सकते हैं $\tan$ किसी भी वास्तविक संख्या उत्पन्न करने के लिए।

सामान्य तौर पर अगर मेरे पास एक सेट एस है जो पूर्णांकों के लिए एक बड़ा या समान कार्डिनैलिटी है, और मैं यादृच्छिक रूप से एस के भीतर एक तत्व उत्पन्न कर सकता हूं, तो मैं पूर्णांक पर एस के सदस्यों को मैप करके यादृच्छिक रूप से किसी भी पूर्णांक को उत्पन्न कर सकता हूं।

मुझे पता है कि अनुक्रम हैं, जैसे कि प्राइम गैप अनुक्रम, जो यादृच्छिक होते हैं और मनमाने ढंग से बड़े पूर्णांक होते हैं, लेकिन आसानी से गणना करने योग्य नहीं होते हैं।

हालाँकि, इसके बारे में मैं क्या सोच सकता हूँ के बारे में है। मुझे आश्चर्य नहीं होगा यदि समस्या का कोई आसान समाधान नहीं था, लेकिन अगर किसी के पास ऐसा करने का कोई कारण है तो यह संभव नहीं है, मैं भी सुनना चाहूंगा।

जवाब

kelalaka Dec 29 2020 at 04:43

मनमाने आकार का कोई मतलब नहीं है क्योंकि गणना रुक नहीं सकती है!

विचार करें कि आप यादृच्छिक पूर्णांक के हर बिट के लिए एक सिक्का टॉस करते हैं, तो आप देख सकते हैं कि सिक्का उछालना कभी खत्म नहीं होता है।

मनमाने आकार के साथ खेलते समय सावधानी बरतनी चाहिए। गणितीय रूप से आप कह सकते हैं कि चलो$x$ एक यादृच्छिक पूर्णांक हो, यानी $x \stackrel{R}{\leftarrow} \mathbb Z$हालाँकि, जब आप इसका एक मूल्य खोजने की कोशिश करते हैं, तो आप इसका सामना करेंगे। यदि आप एक समान यादृच्छिक पूर्णांक चाहते हैं, तो जाहिर है कि यह विफल हो जाएगा!

अब मान लें कि आपके पास एक सीमा है $0\color{red}{<} x \leq 2^L$तब आप LFSR का उपयोग रेंज में यादृच्छिक संख्या उत्पन्न करने के लिए कर सकते हैं । यदि आकार के साथ एक एलएफएसआर$L$ अधिकतम है तो यह आवधिक है और इसकी अवधि है $2^L-1$। इस अवधि में यह सब संभव है$L$सभी शून्य स्थिति को छोड़कर -बिट संख्या। आप समय से एक बीज प्राप्त कर सकते हैं और इसका उपयोग शुरू कर सकते हैं।

ध्यान दें कि LFSR एक क्रिप्टोग्राफिक रूप से सुरक्षित रैंडम स्यूडो जेनरेटर (CSPRNG) होने से बहुत दूर है। बस होने$2L$ एलएफएसआर से बिट आउटपुट बर्लाकैंप-मैस्स एल्गोरिथ्म के कारण अगले बिट्स को निर्धारित करने के लिए पर्याप्त है - और वास्तव में, गौसियन उन्मूलन पर्याप्त है, हालांकि, बीएम बहुत तेज है-।