संख्यात्मक अनुक्रमों का विश्लेषण करें

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

• मान लीजिए कि हमारे पास पूर्णांकों का एक जनरेटर है जो उनमें से बहुत से उत्पादन कर सकता है (हमारे मामले में 10,000,000)।
• प्रिंट का आकार चुनें, जिसे अब हम "रोल" करेंगे, Sz = 1024
• हम आकार के पूर्णांक दो-आयामी वर्ग मैट्रिक्स के लिए मेमोरी का चयन और शून्य शून्य करते हैं: Hists [Sz] [Sz]
• जनरेटर से संख्याओं को घटाएं और उनमें से प्रत्येक (वैल) के लिए हम एक चक्र का आयोजन करते हैं
  

  for (size_t ix = 1; ix <= Sz; ix++) { size_t histix = Val % ix; Hists[ix-1][histix] ++; } 

  यानी हम चयनित फ़िंगरप्रिंट आकार Sz के भीतर सभी नंबरों द्वारा इनपुट मानों को विभाजित करने से अवशिष्टों के हिस्टोग्राम्स को प्लॉट करते हैं।
  
• पर्याप्त संख्या में उत्पन्न मान चलाने के बाद, हमारे पास चयनित सीमा में सभी संख्याओं को विभाजित करने से अवशेषों का एक दो आयामी हिस्टोग्राम है। ध्यान दें कि यह हिस्टोग्राम उस क्रम पर निर्भर नहीं करता है जिसमें जनरेटर द्वारा मान उत्पन्न किए जाते हैं। दूसरी ओर, हम हिस्टोग्राम को स्वयं मूल्यों को नहीं खिला सकते हैं, लेकिन पिछले एक से उनके मतभेद, उदाहरण के लिए, तब आदेश को आंशिक रूप से ध्यान में रखा जाएगा।
  
• इसके बाद, हम परिणामस्वरूप हिस्टोग्राम को एक आसान-से-देखने के रूप में प्रदर्शित करते हैं ( gnuplot का उपयोग यहां ' pm3d मैप ' मोड में किया गया है) और उस चित्र का आनंद लें जो खुल गया है। यह ध्यान देने योग्य है कि आउटपुट को हिस्ट [ix] [[iy] से मूल्य नहीं मिलता है, लेकिन मारने की संभावना के लिए समायोजित किया जाता है (हिस्ट [ix] [iy] * (ix + १) / एसजे)
  

तो चलिए शुरू करते हैं। और हम मानक C- शनी रैंड जनरेटर के साथ शुरू करेंगे:


यह उम्मीद की जाती है कि हिस्टोग्राम त्रिकोणीय और सपाट हो, लेकिन ... और ये अजीब धारियां क्या हैं?
आइए अधिक विस्तार से विचार करें।



ऐसा लगता है कि यह जनरेटर बहुत यादृच्छिक संख्या नहीं पैदा करता है। खैर, मुझे हमेशा संदेह था कि रैंड () को एक यादृच्छिक संख्या जनरेटर के रूप में उपयोग करना "एक बुरे व्यक्ति का एक निश्चित संकेत था" (सी)।

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



पहली नज़र में यह अच्छा लग रहा है। आइए इस हिस्टोग्राम को देखें।



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



कुछ भी नहीं बदला है, लेकिन यह वही है जो हम देखना चाहते थे। एक और प्रयोग, इस बार हम अपने अद्भुत जनरेटर द्वारा जारी किए गए दो लगातार संख्याओं के 24 बिट्स के टुकड़ों को गोंद करेंगे।



और फिर, कोई मतभेद नहीं! बस महान!
आखिरी प्रयास, इस बार हम 24-बिट टुकड़ों को गोंद नहीं करेंगे, लेकिन उन्हें गुणा करेंगे।



बैम! और ऐसा लगता है कि उसका छद्म आंत हमारे यादृच्छिक संख्या जनरेटर से बाहर निकल गया।
वही, लेकिन एक अलग पैमाने पर:



ओह, "हमने पीटर इवानोविच के साथ कहा" (सी)।
साँस लेने के लिए और समझने के लिए कुछ समय प्राप्त करें कि क्या हुआ, आइए देखें कि एक अलग तरह का डेटा कैसा दिखता है:



ये डेटाबेस छवि फ़ाइल से घटाए गए पहले 10 मिलियन 64-बिट पूर्णांक हैं।



और यहां डेटा उसी तरह से प्राप्त होता है, जिसका स्रोत ज़िप फ़ाइल था।
यह यादृच्छिक डेटा की तरह होगा, लेकिन ऊर्ध्वाधर पट्टियां सब कुछ खराब कर देती हैं।

इसलिए, जबकि चौकस पाठक फाइलों से डेटा पढ़कर चकित था, लेखक ने यह देखने का फैसला किया कि बहुत यादृच्छिक क्रम कैसे व्यवहार करते हैं। हम F (n) = F (n-1) + 1 से शुरू करते हैं 0, 1, 2, 3 ...

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



बहुत परिचित तस्वीर है, है ना। वास्तव में, हम दो संख्याओं के उत्पाद का एक संदर्भ हिस्टोग्राम नमूना देखते हैं।
एक स्थान पर उत्पाद एक साथ आया और शेष भाग ।
बल्कि स्पष्ट तरीके से, हमने फर्श के नीचे से संख्याओं का जादू निकाला।



और यह है कि अनुक्रम F (n) = n * n व्यवहार करता है अर्थात्। 0, 1, 4, 9 ...



और यहाँ F (n) = 2 * n * (2 * n + 1) अर्थात। 0 * 1, 2 * 3, 4 * 5 ...
और अंत में, लेखक पहले 10 मिलियन अपराधों के वितरण को दिखाने का विरोध नहीं कर सका।


और उनके "कास्ट" - पहले 10 मिलियन कठिन संख्या (बस सुंदर)।



खैर, सतर्क रहें और "हमेशा, नहीं, कभी नहीं" (सी) अनुक्रमों को गुणा न करें :)।

पुनश्च। लेखिका ने सबज की सक्रिय चर्चा के लिए अलेक्जेंडर अर्टुशिन का विशेष आभार व्यक्त किया।