रैंडम प्राइम्स और राबिन कार्प प्रतिस्थापन खोज
मैं सेडगेविक से राबिन-कार्ब एल्गोरिथम पढ़ रहा हूं। पुस्तक कहती है:
ओवरफ्लो से बचने के दौरान हम जितना संभव हो उतने बड़े प्राइम क्यू का उपयोग करते हैं
पहली बार पढ़ने पर मुझे यादृच्छिक के महत्व पर ध्यान नहीं गया और जब मैंने देखा कि कोड में long
मेरे पहले विचारों का उपयोग किया गया है:
ए) एराटोस्थीन की छलनी का उपयोग एक बड़ा प्राइम खोजने के लिए किया जाता है जो एक long
या
बी फिट बैठता है । किसी भी बड़े प्राइम को पर्याप्त रूप से प्राइम करता है जो इससे बड़ा है int
और इसे एक स्थिर के रूप में उपयोग करता है।
लेकिन फिर बाकी स्पष्टीकरण कहते हैं:
हम इस संभावना
long
से अधिक मूल्य का उपयोग करेंगे10^20
कि टक्कर कम से कम होती है10^-20
इस भाग ने मुझे उलझन में डाल दिया क्योंकि एक long
फिट 10^20
को उससे अधिक मूल्य के लायक नहीं होने दिया। फिर जब मैंने एक अभ्यास के लिए प्रमुख पुस्तक दोषों के लिए गणना की जाँच की, जिसमें केवल निम्नलिखित संकेत हैं:
एक यादृच्छिक n-अंक संख्या 1 / n के लिए आनुपातिकता के साथ अभाज्य है
इसका क्या मतलब है?
तो मूल रूप से जो मुझे नहीं मिलता है वह है:
ए) एक यादृच्छिक प्रधानमंत्री का उपयोग करने का अर्थ क्या है ? हम इसे पूर्व-गणना क्यों नहीं कर सकते हैं और इसे स्थिर के रूप में उपयोग कर सकते हैं?
ख) इसका 10^20
उल्लेख क्यों है क्योंकि यह सीमा से बाहर है long
?
ग) यह संकेत कैसे सहायक है? इसका सही मतलब क्या है?
जवाब
एक बार फिर , सेडगेविक ने एक एल्गोरिथ्म को सरल बनाने और विवरणों को थोड़ा गलत करने की कोशिश की है। सबसे पहले, जैसा कि आप निरीक्षण करते हैं, 10 20 को 64 बिट्स में प्रतिनिधित्व नहीं किया जा सकता है। यहां तक कि 2 63 - 1 के करीब प्राइम लेते हुए , आप शायद यह चाहते हैं कि थोड़ा-सा कमरा बिना ओवरफ्लो किए सामान्य तरीके से गुणा किया जाए ताकि बाद का मॉडुलो सही हो। उत्तर 31-बिट प्राइम का उपयोग करता है, जो इसे आसान बनाता है लेकिन केवल 10 range9 रेंज में टकराव की संभावनाएं प्रदान करता है ।
मूल संस्करण में राबिन फ़िंगरप्रिंट और [ 2 [x] पर एक यादृच्छिक विडंबनापूर्ण बहुपद का उपयोग किया जाता है , जो बीजीय संख्या सिद्धांत के दृष्टिकोण से पूर्णांकों पर एक यादृच्छिक प्रधानमंत्री की तरह व्यवहार करता है। यदि हम बहुपद को 32 या 64 डिग्री के लिए चुनते हैं, तो उंगलियों के निशान पूरी तरह से उपयुक्त लंबाई के एक कंप्यूटर शब्द में फिट होते हैं, और बहुपद जोड़ और घटाव दोनों बिटवाइड एक्सओआर के लिए काम करते हैं, इसलिए कोई अतिप्रवाह नहीं है।
अब, सेडगेविक संभवतः यह बताना नहीं चाहता है कि बहुपद के छल्ले कैसे काम करते हैं। ठीक। अगर मुझे अभ्यास में इस दृष्टिकोण को लागू करना था, तो मैं अधिकतम के करीब एक प्रधानमंत्री पी चुनूंगा जो सस्ते निर्देशों के साथ मॉड द्वारा आसान था (मैं
2 से 2
31 - 2
27 + 1 पर
आंशिक हूं
; EDIT वास्तव में 2 31 - 1; तब भी बेहतर काम करता है जब हमें यहां एक चिकनी प्राइम की आवश्यकता नहीं होती है) और फिर पॉलिनेम्स का मूल्यांकन करने के लिए [1, p] 1] में एक यादृच्छिक संख्या चुनें (यह है कि विकिपीडिया इसे कैसे समझाता है)। इसका कारण यह है कि हमें कुछ यादृच्छिकता की आवश्यकता होती है, अन्यथा बेखबर विरोधी एक इनपुट का चयन कर सकते हैं जो कि बहुत से हैश टकरावों की गारंटी होगी, जो चल रहे समय को गंभीर रूप से कम कर देगा।
सेडगेविक मूल से थोड़ा अधिक बारीकी से पालन करना चाहता था, हालांकि, जो संक्षेप में एक्स के एक निश्चित मूल्य पर बहुपद का मूल्यांकन करता है (मूल संस्करण में बहुपद का उपयोग करता है जो बहुपद के छल्ले का उपयोग करता है)। उसे एक यादृच्छिक प्रधानमंत्री की आवश्यकता है ताकि विचलित विरोधी इंजीनियर टकराव न कर सके। संख्याओं का बड़ा होना काफी अकुशल है, इसलिए वह प्राइम नंबर प्रमेय (जो उसके संकेत के पीछे का गणित है, लेकिन यह केवल स्पर्शोन्मुख है, जो सैद्धांतिक रूप से एक बड़ा गड़बड़ बनाता है) और एक तेज गति परीक्षण (जो संभाव्य हो सकता है) की ओर मुड़ता है; ऐसे मामले जहां यह विफल होता है, एल्गोरिथ्म की शुद्धता को प्रभावित नहीं करेगा, और वे काफी दुर्लभ हैं कि वे अपेक्षित समय को प्रभावित नहीं करेंगे)।
मुझे यकीन नहीं है कि कैसे वह टक्कर की संभावना पर एक औपचारिक बाध्य साबित होता है। मेरा मोटा विचार मूल रूप से, यह दर्शाता है कि ब्याज की खिड़की में पर्याप्त अपराध हैं, चीनी रेमिनेटर प्रमेय का उपयोग करके यह दिखाएं कि यह असंभव है कि एक ही बार में बहुत सारे अपराधों के लिए टक्कर हो, यह निष्कर्ष निकालना कि टक्कर की संभावना से घिरा हुआ है खराब प्राइम चुनने की संभावना, जो कम है। लेकिन प्राइम नंबर प्रमेय केवल asymptotically रखता है, इसलिए हमें मशीन शब्द श्रेणियों में primes के घनत्व के बारे में कंप्यूटर प्रयोगों पर निर्भर रहना होगा। महान नहीं।