उच्च प्रदर्शन वाले बड़े पूर्णांक विभाजन के लिए मुझे किस एल्गोरिदम का उपयोग करना चाहिए?

Question

मैं size_t की सरणी में बड़े पूर्णांक एन्कोड कर रहा हूं। मेरे पास पहले से ही अन्य ऑपरेशन काम कर रहे हैं (जोड़ें, घटाएं, गुणा करें); साथ ही एक अंक से विभाजन। लेकिन यदि संभव हो तो मैं अपने गुणा एल्गोरिदम की समय जटिलता से मेल खाता हूं (वर्तमान में टूम-कुक)।

मैं अपने लाभांश के गुणात्मक उलटा होने के विभिन्न विचारों को लेने के लिए रैखिक समय एल्गोरिदम एकत्र करता हूं। इसका मतलब है कि मैं सैद्धांतिक रूप से एक ही समय में जटिलता को अपने गुणा के रूप में प्राप्त कर सकता हूं, क्योंकि रैखिक-समय ऑपरेशन वैसे भी तुलनात्मक रूप से "महत्वहीन" है।

मेरा सवाल है, मैं वास्तव में ऐसा कैसे कर सकता हूं? अभ्यास में किस प्रकार का गुणात्मक उलटा सर्वोत्तम है? मॉडुलो 64^digitcount? जब मैं अपने divisor द्वारा गुणात्मक उलटा गुणा करता हूं, तो क्या मैं डेटा के उस हिस्से को कंप्यूटिंग कर सकता हूं जिसे पूर्णांक छंटनी के कारण फेंक दिया जाएगा? क्या कोई सी या सी ++ छद्म कोड प्रदान कर सकता है या यह कैसे किया जाना चाहिए इसके बारे में एक सटीक स्पष्टीकरण दे सकता है?

या क्या एक समर्पित विभाजन एल्गोरिदम है जो व्यस्त-आधारित दृष्टिकोण से भी बेहतर है?

संपादित करें: मैंने खोला जहां मुझे ऊपर उल्लिखित "उलटा" दृष्टिकोण मिल रहा था। "आर्ट ऑफ कंप्यूटर प्रोग्रामिंग, वॉल्यूम 2: सेमिन्यूमेरिकल एल्गोरिदम" के पृष्ठ 312 पर, Knuth "एल्गोरिदम आर" प्रदान करता है जो एक उच्च परिशुद्धता पारस्परिक है। उनका कहना है कि इसकी समय जटिलता गुणा के मुकाबले कम है। हालांकि, यह इसे सी में परिवर्तित करने और इसे जांचने के लिए अनौपचारिक है, और अस्पष्ट है कि कितना ओवरहेड मेमोरी इत्यादि का उपभोग किया जाएगा, जब तक कि मैं इसे कोड नहीं करता, जिसमें कुछ समय लगेगा। अगर मैं इसे किसी को मारता हूं तो मैं इसे पोस्ट करूंगा।

Answer 1

जीएमपी लाइब्रेरी आमतौर पर अच्छे एल्गोरिदम के लिए एक अच्छा संदर्भ है। उनका documented algorithms for division मुख्य रूप से एक बहुत बड़ा आधार चुनने पर निर्भर करता है, ताकि आप 2 अंकों की संख्या से 4 अंकों की संख्या विभाजित कर रहे हों और फिर लंबी विभाजन के माध्यम से आगे बढ़ें।

लांग डिवीजन को 1 अंकों के आंकड़ों से 2 अंकों की गणना करने की आवश्यकता होगी; यह या तो पुनरावर्ती रूप से किया जा सकता है, या एक उलटा प्रीकंप्यूटिंग करके और बैरेट कमी के साथ जैसा कि आप उद्धरण का आकलन कर सकते हैं।

जब एक n -बिट संख्या, पुनरावर्ती संस्करण लागत O(M(n) log(n)), जहां M(n)n -बिट संख्या गुणा की लागत है द्वारा एक 2n -बिट संख्या को विभाजित।

संस्करण बैरेट कमी का उपयोग कर O(M(n)) खर्च करता है, तो आप न्यूटन के एल्गोरिथ्म का उपयोग उलटा गणना करने के लिए होगा, लेकिन जीएमपी के दस्तावेज़ के अनुसार, छिपे हुए लगातार एक बहुत बड़ा है, तो यह विधि बहुत बड़ी डिवीजनों के लिए केवल बेहतर है।

---

और अधिक विस्तार में, सबसे विभाजन एल्गोरिदम के पीछे कोर एल्गोरिथ्म गणना एक "कमी के साथ अनुमान भागफल", कंप्यूटिंग (q,r) ताकि

x = qy + r 

लेकिन प्रतिबंध यह है कि 0 <= r < y के बिना है।ठेठ पाश,

• अनुमान भागफल x/y
• की q कंप्यूट इसी कमी ताकि कमी r कुछ इच्छित अंतराल में
• है r बहुत बड़ा है r = x - qy
• वैकल्पिक रूप से भागफल समायोजित है फिर के स्थान पर r के साथ दोहराएं।

x/y के भागफल सभी q उत्पादित रों का योग होगा, और r के अंतिम मान सत्य शेष हो जाएगा।

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

फूट डालो और दृष्टिकोण को जीत कंप्यूटिंग x'/y' जहां x' और y'x और y की अग्रणी अंक हैं द्वारा x/y के भागफल का अनुमान है। उनके आकार को समायोजित करके अनुकूलन के लिए बहुत सी जगह है, लेकिन आईआईआरसी आपको सर्वोत्तम परिणाम मिलते हैं यदि x'y' के दो अंकों के बराबर है।

गुणा-दर-विपरीत दृष्टिकोण, आईएमओ, सरल है यदि आप अंकगणित पूर्णांक से चिपके रहते हैं। बुनियादी विधि

• अनुमान है q = 2^(i+j-k) floor(floor(x/2^i) m/2^j)

वास्तव में साथ m = floor(2^k/y)

अनुमान x/y साथ y का प्रतिलोम, व्यावहारिक कार्यान्वयन अगर यह मतलब है कि आप एक तेजी से परस्पर उपयोग कर सकते हैं m में अतिरिक्त त्रुटि बर्दाश्त कर सकते हैं कार्यान्वयन।

त्रुटि विश्लेषण करने के लिए एक दर्द है, लेकिन अगर मैं यह करने के लिए जिस तरह से याद करते हैं, तो आप इतना है कि x ~ 2^(i+j) त्रुटियां जमा करने के लिए कारण i और j का चयन करना चाहते हैं, और आप कुल मिलाकर काम कम करने के लिए x/2^i ~ m^2 चुनना चाहते हैं।

आगामी कमी ताकि k को चुनने के लिए एक सामान्य नियम के देता है, r ~ max(x/m, y) होगा: आप m के आकार भागफल के बिट्स की संख्या के बारे में होना चाहते हैं आप प्रति यात्रा — या समतुल्य रूप बिट्स की संख्या आप चाहते हैं की गणना प्रति पुनरावृत्ति x से निकालने के लिए।

Answer 2

मुझे गुणात्मक उलटा एल्गोरिदम नहीं पता है, लेकिन यह Montgomery Reduction या बैरेट की कमी के संशोधन की तरह लगता है।

मैं बिगिन डिवीजन थोड़ा अलग करता हूं।

bignum division देखें। विशेष रूप से सन्निकटन विभक्त और 2 लिंक पर एक नज़र डालें। एक मेरा निश्चित बिंदु विभाजक है और अन्य माप के साथ तेजी से गुणा एल्गोस (जैसे करात्सुबा, शॉनहेज-स्ट्रैसेन एनटीटी पर) हैं, और 32 बिट बेस के लिए मेरे बहुत तेज़ एनटीटी कार्यान्वयन का एक लिंक है।

मुझे यकीन नहीं है कि उलटा गुणात्मक तरीका है या नहीं।

यह ज्यादातर मॉड्यूलो ऑपरेशन के लिए उपयोग किया जाता है जहां विभाजक स्थिर होता है। मुझे डर है कि मनमाने ढंग से डिवीजनों के लिए बिगिन इनवर्क्स हासिल करने के लिए आवश्यक समय और संचालन मानक मानक स्वयं ही बड़े हो सकते हैं, लेकिन जैसा कि मैं इससे परिचित नहीं हूं मैं गलत हो सकता है।

उपयोग में सबसे आम विभाजक मैंने अपूर्णताओं में देखा न्यूटन-रैफसन डिवीजन जो उपरोक्त लिंक में अनुमानित विभक्त के समान है।

अनुमान/पुनरावर्तक डिवाइडर आम तौर पर गुणा का उपयोग करते हैं जो उनकी गति को परिभाषित करता है।

छोटे पर्याप्त संख्या के लिए आमतौर पर लंबे समय द्विआधारी विभाजन और 32/64 बिट अंकों आधार विभाजन काफी तेजी से नहीं सबसे तेजी से करता है, तो यह है: आम तौर पर वे छोटे भूमि के ऊपर है, और n अधिकतम मान संसाधित हो

(अंकों की संख्या नहीं है!)

द्विआधारी विभाजन उदाहरण:

O(log32(n).log2(n)) = O(log^2(n)) है।
यह सभी महत्वपूर्ण बिट्स के माध्यम से loops। प्रत्येक पुनरावृत्ति में आपको compare, sub, add, bitshift की आवश्यकता होती है। उनमें से प्रत्येक ऑपरेशन log32(n) में किया जा सकता है, और log2(n) बिट्स की संख्या है।

यहाँ मेरी bigint टेम्पलेट्स में से एक (C++) से द्विआधारी विभाजन के उदाहरण:

template <DWORD N> void uint<N>::div(uint &c,uint &d,uint a,uint b) 
    { 
    int i,j,sh; 
    sh=0; c=DWORD(0); d=1; 
    sh=a.bits()-b.bits(); 
    if (sh<0) sh=0; else { b<<=sh; d<<=sh; } 
    for (;;) 
     { 
     j=geq(a,b); 
     if (j) 
      { 
      c+=d; 
      sub(a,a,b); 
      if (j==2) break; 
      } 
     if (!sh) break; 
     b>>=1; d>>=1; sh--; 
     } 
    d=a; 
    } 

N 32 बिट DWORD एक bigint संख्या स्टोर करने के लिए इस्तेमाल किया रों की संख्या है।

• c = a/b
• d = a % b
• qeq(a,b) एक तुलना है: a >= b अधिक या बराबर (log32(n)=N में किया)
  यह a < b के लिए 0 देता है, a > b के लिए 1, 2a == b
• sub(c,a,b) के लिए c = a - b
है

गति को बढ़ावा देने से कि इस गुणा का उपयोग नहीं करता है (यदि आप थोड़ा बदलाव गिनती नहीं है)

आप 2^32 (ALU ब्लॉक) की तरह एक बड़ा आधार के साथ अंकों का उपयोग करते हैं प्राप्त की है, तो आप कर सकते हैं एएलयू संचालन में 32 बिट बिल्ड का उपयोग करके पूरी तरह से बहुपद जैसी शैली को फिर से लिखें।
यह आमतौर पर बाइनरी लंबे विभाजन के बाद भी तेज होता है, विचार प्रत्येक डीडब्ल्यूओआर को एक अंक के रूप में संसाधित करना है, या सीपीयू क्षमताओं को हिट करने तक आधे से उपयोग किए गए अंकगणित को विभाजित करना है।
bignums

साथ कंप्यूटिंग, जबकि आप बुनियादी आपरेशन अनुकूलित किया है, तो आगे भी जटिलता को कम के रूप में उप परिणाम पुनरावृत्तियों के साथ छोटे मिल (बुनियादी आपरेशन की जटिलता को बदलने कर सकते हैं देखें division by half-bitwidth arithmetics

सब उस के शीर्ष पर) इसका एक अच्छा उदाहरण एनटीटी आधारित गुणाएं हैं।

ओवरहेड गड़बड़ कर सकता है।

इस वजह से रनटाइम कभी-कभी बड़ी ओ जटिलता की प्रतिलिपि नहीं लेता है, इसलिए आपको हमेशा प्रदर्शनों को मापना चाहिए और अधिकतम प्रदर्शन प्राप्त करने और अनुकूलित करने के लिए अनुकूलित बिट-गिनती के लिए तेज़ दृष्टिकोण का उपयोग करना चाहिए।