8 बिट्स पर रॉबर्ट मॉरिस के रूप में, 10,000 तक गिने गए

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






इस लेख में हम देखेंगे कि तथाकथित संभाव्य काउंटर कैसे काम करता है।
यह पहली बार रॉबर्ट मॉरिस द्वारा 1977 में पेश किया गया था, जो बेल्लाब्स में काम करने वाले एक क्रिप्टोग्राफर थे, जो अपने वाक्यांश के लिए जाने जाते थे

"कंप्यूटर सुरक्षा के लिए तीन स्वर्ण नियम: एक कंप्यूटर का मालिक नहीं है, इसे चालू न करें, और इसका उपयोग न करें।"

मीटर विवरण

हम अपने निपटान में टी बिट्स है।
हम कुछ गैर-नकारात्मक बढ़ते अनुक्रम n _i चुनते हैं (i 0 से 2 ^t - 1 की सीमा में है), थोड़ा आगे जाकर मैं कहूंगा कि n _{i के} मान हमारे काउंटर मान होंगे।
अब सबसे दिलचस्प बात यह है कि 1 में एक काउंटर जोड़ने पर 1 / (n _{i + 1} - n _i ) की संभावना के साथ होता है



उदाहरण के लिए, हमारा अनुक्रम n _i = i ^{2 है} , फिर 8 से काउंटर बढ़ाने पर 1 / (16-8) = 0.125 की संभावना के साथ सच हो जाएगा, परिणामस्वरूप, n _i से n _{i + 1} तक का काउंटर n _{i + 1} से औसतन बढ़ जाएगा - n _i संचालन

एक संभाव्य काउंटर का एक विशेष मामला n _i = i है, यह स्पष्ट है कि इस तरह के अनुक्रम के साथ काउंटर सामान्य होगा और इसे जोड़ने की संभावना 1 होगी

कार्यान्वयन

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

हमारे दो मुख्य कार्य होंगे। पहला काउंटर बढ़ाएगा, दूसरा अनुक्रम का i-th नंबर लौटाएगा।

private byte counter = 0; public void increase(){ Random rand = new Random(); int randNumber = rand.nextInt(getElementSequence(counter + 1) - getElementSequence(counter)); if(randNumber == 0) counter++; } 

यहां संभावना के आधार पर काउंटर बढ़ाया जाता है। काउंटर अनुक्रम के बारे में कुछ भी नहीं जानता है और केवल ई-वें तत्व को लौटाता है, जो घटना की सफलता या विफलता पर निर्भर करता है।

यहाँ स्क्वेर्ड संख्याओं का क्रम दिया गया है

 private int getElementSequence(int number){ return (int) Math.pow(number, 2); } 

लेकिन फाइबोनैचि संख्याओं से

  private int getElementSequence(int number){ int sumFib = 1; int previousElement = 0; int temp; for(int i = 0; i < number + 1; i++){ temp = sumFib; sumFib = sumFib + previousElement; previousElement = temp; } return sumFib; } 

हम एक सामान्य चक्र में काउंटर वृद्धि का अनुकरण करते हैं, मान लीजिए कि 10,000 पुनरावृत्तियों में।

 public static void main(String[] args) { TestApproximateCounting test = new TestApproximateCounting(); for(int i=0; i<10000; i++){ test.increase(); }; } 

संक्षेप में देना

प्रत्येक क्रम के लिए मैंने 10,000 पुनरावृत्तियों के काउंटर के 10 रन खर्च किए

नंबर चलाएं	चुकता संख्या के लिए काउंटर मूल्य	वर्गों की संख्या	फिबोनाची संख्या के लिए काउंटर मूल्य	फाइबोनैचि संख्या
1	93	8 649 है	20	6 765
2	111	12 321	20	6 765
3	105	११ ०२५	20	6 765
4	103	१० ६० ९	21	१० ९ ४६
5	96	9216	21	१० ९ ४६
6	94	8 836	22	17 711
7	93	६३ ९	19	4 181
8	106	11236	19	4 181
9	104	१० 10१६	21	१० ९ ४६
10	94	8 836	20	6 765

जैसा कि आप देख सकते हैं, त्रुटियां बहुत ध्यान देने योग्य हैं, लेकिन यदि आपको 8 बिट्स पर 10,000 से अधिक की गणना करने की आवश्यकता है, तो संभावित काउंटर एक अच्छा विकल्प है।

संदर्भ:
कोरमेन टी।, लिसेर्सन सी।, रिवेस्ट आर।, स्टीन के। - एल्गोरिदम। निर्माण और विश्लेषण - 2005
मॉरिस, आर। छोटे रजिस्टरों में बड़ी संख्या में घटनाओं की गिनती। एसीएम 21, 10 (1977), 840842 का संचार

युपीडी। अनुरोध पर, मैंने प्रत्येक अनुक्रम के लिए काउंटर मान दिखाते हुए तालिका में दो कॉलम जोड़े, लेकिन एक बार फिर मैं कहूंगा कि काउंटर का मूल्य काउंटर से नहीं बल्कि इनपुट काउंटर के साथ getElementSequence फ़ंक्शन से प्राप्त होता है।