कुशलता से पता चलता है कि तर्कसंगत संख्या बराबर

Question

मेरे पास कई तर्कसंगत संख्याओं का संग्रह है, जिसमें प्रत्येक के बड़े और सैकड़ों (सैकड़ों या हजारों बिट्स) के रूप में संग्रहीत प्रत्येक के अंक और संश्लेषक हैं। मैं कुशलतापूर्वक परीक्षण करने में सक्षम होना चाहता हूं कि सेट में दिए गए तर्कसंगत संख्या a/b सेट में किसी अन्य तर्कसंगत संख्या c/d के बराबर है या नहीं।

सबसे सरल तरीका यह जांचना होगा कि a*d == b*c, निश्चित रूप से, लेकिन मुझे पूर्ण उत्पादों की गणना करने से कुछ और अधिक कुशल चाहिए।

मेरी विशेष यूज-केस पर कुछ नोट:

• जोड़े मैं परीक्षण हो जाएगा वास्तव में बराबर होने के (क्योंकि मैं पहले से ही precomputing रहा हूँ और पहली बार अपने चल बिन्दु अनुमानों से उनकी तुलना की पूरी संभावना है), अगर वे असमान हैं तो जल्दी से बाहर निकलना मुझे ज्यादा समय नहीं बचाएगा।
• मैं प्रत्येक संख्या के लिए अतिरिक्त डेटा प्रीकंप्यूटिंग के साथ ठीक हूं, लेकिन प्रत्येक नंबर का उपयोग केवल कुछ हद तक तुलना में किया जाएगा, इसलिए महंगा प्रीकंप्यूशन (जैसे प्राइम फैक्टरेशन) शायद सार्थक नहीं होगा।
• कभी-कभी झूठे नकारात्मक ठीक होंगे, लेकिन झूठी सकारात्मक नहीं हैं।

मैं इस सैद्धांतिक रूप से असंभव हो सकता है लगता है, लेकिन छत्ता मन में इसे बाहर फेंक सिर्फ मामले में।

Answer 1

आप बिट-लंबाई की तुलना करके कई बराबर जोड़ों को फ़िल्टर नहीं कर सकते हैं। एल (एक) = मंजिल (log2 (एक)) + 1 एक बिट लंबाई करते हैं। यदि एक/ख = ग/घ से एल (एक) + एल (घ) = एल (ग) + एल (ख)।

जब आप पहली बार लंबाई की तुलना कर रहे हैं और उत्पादों की तुलना कर रहे हैं, तो केवल एक लम्बाई के बराबर होने पर आप इसका उपयोग कर सकते हैं।

Answer 2

दूसरा प्रयास;) यदि आपको सेट रोकथाम के लिए बार-बार नई संख्याएं जांचनी होंगी, तो आपको अपेक्षाकृत प्रमुख अंशों को क्रमबद्ध सेट में स्टोर करना चाहिए। सेट के तुलनात्मक कार्य को पहले काउंटरों की तुलना करना चाहिए, और काउंटर बराबर होने पर denominators की तुलना में चाहिए। तुलना रैखिक समय में किया जा सकता, और इस प्रकार में एम आइटम के साथ सेट का आदेश दिया एक तत्व खोजने की जरूरत है हे (एन लॉग एम) चरणों। एक अंश लागत को कम करना ओ (एन ²)। इस प्रकार, रोकथाम के लिए एक नंबर का परीक्षण हे (एन ² + एन लॉग एम) कदम, और कंप्यूटिंग सेट की आवश्यकता है हे (एम.एन. ²)।

संपादित करें: इसके बजाय किसी क्रमित या एक पेड़ सेट का उपयोग करने का, आप एक हैश सेट जो हे (एन ² + एन) के लिए खोज के लिए चरणों की अपेक्षित संख्या को कम कर देता उपयोग कर सकते हैं = हे (एन ²)।

Answer 3

यह आपके मामले में बहुत उपयोगी नहीं होगा, अगर आप पहले से ही फ़्लोटिंग पॉइंट सन्निकटन का प्रीकंप्यूट करते हैं; यह अभी भी पाइपलाइन (या कुछ अनुमान) में कुछ समय बचा सकता है।

आप ए, बी, सी और डी के पूर्णांक मानों की जांच करते हैं।

तर्कसंगत संख्याएं का अर्थ है कि वे मूल के माध्यम से एक ही पंक्ति का वर्णन करते हैं।

यदि सी> ए, तो यह भी डी> बी होना चाहिए, अन्यथा हम नीचे दाईं ओर भूरे रंग के क्षेत्र में होंगे; यदि सी < ए, इसके विपरीत, यह डी < बी होना चाहिए, या हम ऊपरी बाएं ग्रे कोने में होंगे। भूरे रंग के क्षेत्रों में समानता की कोई संभावना नहीं होती है, और यदि संख्या यादृच्छिक थी (यानी फ्लोट-सन्निकटन-फ़िल्टर नहीं), तो हम उनमें से एन/2 को एन बिगिन तुलना के साथ बाहर कर देते।

शेष 50% में, हम आधे से बाहर निकल सकते हैं कि अगर ए> बी, तो काला रेखा पहले और तीसरे चतुर्भुज के द्विभाजक से नीचे है, और यह सी> डी होना चाहिए, अन्यथा सी/डी द्विभाजक के दूसरी तरफ होगा; हम शीर्ष नारंगी क्षेत्र में होंगे, बिना समानता संभव है। वही या < बी केस। तो अन्य दो बड़ी तुलना मूल की एक चौथाई तक की संख्या को कम करने के लिए कम करती है; उनको फ़्लोटिंग पॉइंट में अनुमानित किया जा सकता है, और यदि वे "लगभग बराबर" हैं, तो हम छोटे लाल क्षेत्र में हैं जहां अन्य तकनीकों की आवश्यकता होती है।

तुम भी अवलोकन है कि किसी भी कश्मीर के लिए द्वारा इस विधि का विस्तार कर सकते हैं, के संबंध के k के ख ग के बीच एक के रूप में एक ही हो सकता है और के लिए एक/बी और सी/डी बराबर हो घ k चाहिए; और यदि के 2 की पूर्णांक शक्ति है, जो कई संभावित अनुकूलन की अनुमति देती है।

(निश्चित रूप से, इसकी लागत a*d==b*c परीक्षण से अधिक हो जाएगी)।