डिवीजन एल्गोरिदम

This article is about algorithms for division of integers. For the pencil-and-paper algorithm, see Long division. For the theorem proving the existence of a unique quotient and remainder, see Euclidean division. For the division algorithm for polynomials, see Polynomial long division.

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

डिवीजन एल्गोरिदम दो मुख्य श्रेणियों में आते हैं: स्लो डिवीजन और फास्ट डिवीजन। धीमा विभाजन एल्गोरिदम प्रति पुनरावृत्ति अंतिम भागफल का एक अंक उत्पन्न करता है। धीमे विभाजन के उदाहरणों में शामिल हैं #पुनर्स्थापना विभाजन, गैर-निष्पादित पुनर्स्थापन, #गैर-पुनर्स्थापना प्रभाग|गैर-पुनर्स्थापना, और #SRT विभाजन विभाजन। तीव्र विभाजन विधियाँ अंतिम भागफल के निकट सन्निकटन के साथ शुरू होती हैं और प्रत्येक पुनरावृत्ति पर अंतिम भागफल के दोगुने अंकों का उत्पादन करती हैं। #न्यूटन-रेफसन डिवीजन|न्यूटन-रफसन और #गोल्डस्चमिट डिवीजन एल्गोरिदम इस श्रेणी में आते हैं।

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

चर्चा फॉर्म को संदर्भित करेगी $N/D=(Q,R)$, कहाँ

• एन = अंश (लाभांश)
• डी = भाजक (भाजक)

इनपुट है, और

• क्यू = भागफल
• आर = शेष

आउटपुट है।

बार-बार घटाव द्वारा विभाजन

यूक्लिड के तत्वों|यूक्लिड के तत्वों, पुस्तक VII, प्रस्ताव 1 में प्रस्तुत एक महानतम सामान्य भाजक एल्गोरिथ्म में ऐतिहासिक रूप से शामिल सबसे सरल विभाजन एल्गोरिथ्म, केवल घटाव और तुलना का उपयोग करके शेष दो सकारात्मक पूर्णांक पाता है:

<वाक्यविन्यास लैंग = लुआ> आर:= एन क्यू := 0 जबकि आर ≥ डी करते हैं

 आर := आर - डी
 क्यू := क्यू + 1

अंत वापसी (क्यू, आर) </वाक्यविन्यास हाइलाइट>

सबूत है कि भागफल और शेष मौजूद हैं और अद्वितीय हैं (यूक्लिडियन डिवीजन में वर्णित) एक पूर्ण विभाजन एल्गोरिदम को जन्म देता है, जो कि नकारात्मक और सकारात्मक दोनों संख्याओं पर लागू होता है, जो कि जोड़, घटाव और तुलना का उपयोग करता है:

<वाक्यविन्यास लैंग = लुआ> फ़ंक्शन डिवाइड (एन, डी)

 यदि D = 0 तो त्रुटि (DivisionByZero) समाप्त हो जाती है
 अगर डी <0 तो (क्यू, आर): = विभाजित (एन, -डी); वापसी (−क्यू, आर) अंत
 अगर एन <0 तो
   (क्यू, आर) := विभाजित (-एन, डी)
   यदि R = 0 तो वापसी (−Q, 0)
   अन्यथा लौटें (−Q − 1, D − R) समाप्त
 अंत
 - इस बिंदु पर, एन ≥ 0 और डी > 0
 डिवाइड_अनसाइनड लौटाएं (एन, डी)

अंत फ़ंक्शन डिवाइड_हस्ताक्षरित (एन, डी)

 क्यू := 0; आर:= एन
 जबकि आर ≥ डी करते हैं
   क्यू := क्यू + 1
   आर := आर - डी
 अंत
 वापसी (क्यू, आर)

अंत </वाक्यविन्यास हाइलाइट>

यह प्रक्रिया हमेशा R ≥ 0 उत्पन्न करती है। हालांकि बहुत सरल है, यह Ω(Q) कदम उठाती है, और इसलिए लंबे विभाजन जैसे धीमे विभाजन एल्गोरिदम की तुलना में घातीय रूप से धीमी है। यह उपयोगी है अगर क्यू को छोटा माना जाता है (आउटपुट-संवेदनशील एल्गोरिदम होने के नाते), और एक निष्पादन योग्य विनिर्देश के रूप में काम कर सकता है।

लंबा विभाजन

Main article: Long division § Algorithm for arbitrary base

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

जब एक बाइनरी रेडिक्स के साथ प्रयोग किया जाता है, तो यह विधि नीचे शेष एल्गोरिथम के साथ (अहस्ताक्षरित) पूर्णांक विभाजन के लिए आधार बनाती है। लघु विभाजन एक अंकीय भाजक के लिए उपयुक्त दीर्घ विभाजन का संक्षिप्त रूप है। चंकिंग (विभाजन) – आंशिक भागफल विधि या जल्लाद विधि के रूप में भी जाना जाता है – लंबे विभाजन का एक कम कुशल रूप है जिसे समझना आसान हो सकता है। किसी को वर्तमान में प्रत्येक चरण में जितने गुणक हैं, उससे अधिक गुणकों को घटाने की अनुमति देकर, लंबे विभाजन का एक अधिक मुक्त रूप संस्करण भी विकसित किया जा सकता है।

पूर्णांक विभाजन (अहस्ताक्षरित) शेष के साथ

Main article: Long division § Binary division

See also: Binary number § Division

निम्नलिखित एल्गोरिदम, प्रसिद्ध लंबे विभाजन का बाइनरी संस्करण, एन को डी से विभाजित करेगा, भागफल को क्यू में और शेष को आर में रखकर। निम्नलिखित छद्म कोड में, सभी मानों को अहस्ताक्षरित पूर्णांक के रूप में माना जाता है।

<वाक्यविन्यास लैंग = लुआ> यदि D = 0 तो त्रुटि (DivisionByZeroException) समाप्त हो जाती है Q := 0 -- प्रारंभिक भागफल और शेषफल शून्य र := 0 for i := n − 1 .. 0 do -- जहां n, N में बिट्स की संख्या है

 R := R << 1 -- बायाँ-पारी R 1 बिट से
 R(0) := N(i) -- अंश के बिट i के बराबर R का न्यूनतम-महत्वपूर्ण बिट सेट करें
 अगर आर ≥ डी तो
   आर := आर - डी
   क्यू (मैं) : = 1
 अंत

अंत </वाक्यविन्यास हाइलाइट>

उदाहरण

अगर हम एन = 1100 लेते हैं₂ (12₁₀) और डी = 100₂ (4₁₀)

चरण 1: R=0 और Q=0
सेट करें चरण 2: i=3 (एन में बिट्स की संख्या से एक कम)
लें चरण 3: R=00 (1 द्वारा बाएं स्थानांतरित)
चरण 4: R=01 (सेटिंग R(0) से N(i))
चरण 5: R <D, इसलिए कथन छोड़ें

चरण 2: i=2
सेट करें चरण 3: आर = 010
चरण 4: आर = 011
चरण 5: R <D, कथन छोड़ा गया

चरण 2: i=1
सेट करें चरण 3: आर = 0110
चरण 4: आर = 0110
चरण 5: R>=D, स्टेटमेंट
दर्ज किया गया चरण 5बी: आर=10 (आर−डी)
चरण 5c: Q=10 (Q(i) को 1 पर सेट करना)

चरण 2: i=0
सेट करें चरण 3: आर = 100
चरण 4: आर = 100
चरण 5: R>=D, स्टेटमेंट
दर्ज किया गया चरण 5बी: आर = 0 (आर-डी)
चरण 5c: Q=11 (Q(i) को 1 पर सेट करना)

'अंत'
क्यू = 11₂ (3₁₀) और आर = 0।

धीमे विभाजन के तरीके

धीमी विभाजन विधियाँ सभी एक मानक पुनरावृत्ति समीकरण पर आधारित हैं

$R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,$

कहाँ:

• आर_j विभाजन का j-वाँ आंशिक शेषफल है
• बी मूलांक है (आधार, आमतौर पर कंप्यूटर और कैलकुलेटर में आंतरिक रूप से 2)
• क्यू _{n − (j + 1)} स्थिति n−(j+1) में भागफल का अंक है, जहां अंकों की स्थिति को सबसे महत्वपूर्ण 0 से सबसे महत्वपूर्ण n−1 तक क्रमांकित किया गया है
• n भागफल में अंकों की संख्या है
• D भाजक है

विभाजन बहाल करना

पुनर्स्थापन विभाजन निश्चित बिंदु अंकगणित | निश्चित-बिंदु भिन्नात्मक संख्याओं पर संचालित होता है और धारणा 0 <D <N पर निर्भर करता है। भागफल अंक q अंक समुच्चय {0,1} से बनते हैं।

बाइनरी (रेडिक्स 2) रीस्टोरिंग डिवीजन के लिए बुनियादी एल्गोरिथम है:

<वाक्यविन्यास लैंग = लुआ> आर:= एन D := D << n -- R और D को N और Q की शब्द चौड़ाई से दोगुनी आवश्यकता है for i := n − 1 .. 0 do -- उदाहरण के लिए 31..0 32 बिट्स के लिए

 R := 2 * R − D -- स्थानांतरित मूल्य से परीक्षण घटाव (2 से गुणा बाइनरी प्रतिनिधित्व में एक बदलाव है)
 अगर आर >= 0 तब
   q(i) := 1 -- परिणाम-बिट 1
 अन्य
   q(i) := 0 -- परिणाम-बिट 0
   आर: = आर + डी - नया आंशिक शेष (पुनर्स्थापना) स्थानांतरित मूल्य है
 अंत

अंत

-- जहाँ: N = अंश, D = हर, n = #bits, R = आंशिक शेषफल, q(i) = भाग #i का भागफल </वाक्यविन्यास हाइलाइट>

नॉन-परफॉर्मिंग रिस्टोरिंग डिवीजन रीस्टोरिंग डिवीजन के समान है सिवाय इसके कि 2R का मान सहेजा जाता है, इसलिए R < 0 के मामले में D को वापस जोड़ने की आवश्यकता नहीं है।

गैर-पुनर्स्थापना विभाजन

गैर-पुनर्स्थापना विभाजन {0, 1} के बजाय भागफल अंकों के लिए अंक सेट {−1, 1} का उपयोग करता है। एल्गोरिथ्म अधिक जटिल है, लेकिन हार्डवेयर में लागू होने पर इसका लाभ होता है कि केवल एक ही निर्णय होता है और प्रति अंश बिट में जोड़/घटाव होता है; घटाव के बाद कोई पुनर्स्थापना कदम नहीं है, जो संभावित रूप से संचालन की संख्या को आधे तक कम कर देता है और इसे तेजी से निष्पादित करने देता है। गैर-नकारात्मक संख्याओं के बाइनरी (मूलांक 2) गैर-पुनर्स्थापना विभाजन के लिए मूल एल्गोरिथ्म है:

<वाक्यविन्यास लैंग = लुआ> आर:= एन D := D << n -- R और D को N और Q की शब्द चौड़ाई से दोगुनी आवश्यकता है for i = n − 1 .. 0 do -- उदाहरण के लिए 31..0 32 बिट के लिए

 अगर आर >= 0 तब
   क्ष(मैं) := +1
   आर := 2 * आर - डी
 अन्य
   क्ष(मैं) := -1
   आर := 2 * आर + डी
 अगर अंत

अंत

-- नोट: N=अंश, D=हर, n=#बिट्स, R=आंशिक शेषफल, q(i)=bit #i भागफल का। </वाक्यविन्यास हाइलाइट>

इस एल्गोरिथम के बाद, भागफल एक गैर-मानक रूप में होता है जिसमें -1 और +1 के अंक होते हैं। अंतिम भागफल बनाने के लिए इस फॉर्म को बाइनरी में बदलने की जरूरत है। उदाहरण:

Convert the following quotient to the digit set {0,1}:
Start:	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1. Form the positive term:	$P=11101010\,$
2. Mask the negative term*:	$M=00010101\,$
3. Subtract: $P-M$:	$Q=11010101\,$
*.( Signed binary notation with one's complement without two's complement)

यदि −1 के अंक $Q$ शून्य (0) के रूप में संग्रहीत किया जाता है जैसा कि आम है $P$ है $Q$ और कंप्यूटिंग $M$ तुच्छ है: मूल पर एक का पूरक (थोड़ा-थोड़ा पूरक) करें $Q$. <वाक्यविन्यास लैंग = लुआ> Q := Q − bit.bnot(Q) -- उपयुक्त है यदि Q में −1 अंकों को शून्य के रूप में दर्शाया जाता है जैसा कि सामान्य है। </वाक्यविन्यास हाइलाइट>

अंत में, इस एल्गोरिथम द्वारा परिकलित भागफल हमेशा विषम होते हैं, और R में शेष −D ≤ R < D की श्रेणी में होता है। उदाहरण के लिए, 5/2 = 3 R −1। धनात्मक शेषफल में बदलने के लिए, Q के गैर-मानक रूप से मानक रूप में परिवर्तित होने के बाद एकल पुनर्स्थापन चरण करें: <वाक्यविन्यास लैंग = लुआ> अगर आर <0 तो

 क्यू: = क्यू - 1
 R := R + D -- केवल तभी आवश्यक है जब शेष ब्याज का हो।

अगर अंत </वाक्यविन्यास हाइलाइट>

वास्तविक शेषफल R >> n है। (रिस्टोरिंग डिवीजन के साथ, आर के निम्न-क्रम बिट्स उसी दर पर उपयोग किए जाते हैं जैसे भागफल क्यू के बिट्स का उत्पादन होता है, और दोनों के लिए एकल शिफ्ट रजिस्टर का उपयोग करना आम है।)

एसआरटी डिवीजन

एसआरटी डिवीजन कई माइक्रोप्रोसेसर कार्यान्वयन में विभाजन के लिए एक लोकप्रिय तरीका है। एल्गोरिदम का नाम डी.डब्ल्यू. आईबीएम के स्वीनी, इलिनोइस विश्वविद्यालय के जेम्स ई। रॉबर्टसन और इंपीरियल कॉलेज लंदन के केडी टॉचर। उन सभी ने लगभग एक ही समय में स्वतंत्र रूप से एल्गोरिदम विकसित किया (क्रमशः फरवरी 1957, सितंबर 1958 और जनवरी 1958 में प्रकाशित)। एसआरटी विभाजन गैर-पुनर्स्थापना विभाजन के समान है, लेकिन यह प्रत्येक भागफल अंक निर्धारित करने के लिए लाभांश और भाजक के आधार पर एक लुकअप तालिका का उपयोग करता है।

सबसे महत्वपूर्ण अंतर यह है कि भागफल के लिए अनावश्यक प्रतिनिधित्व का उपयोग किया जाता है। उदाहरण के लिए, रेडिक्स-4 एसआरटी डिवीजन लागू करते समय, प्रत्येक भागफल अंक को पांच संभावनाओं में से चुना जाता है: {-2, -1, 0, +1, +2}। इस वजह से, एक भागफल अंक का चुनाव सही नहीं होना चाहिए; बाद के भागफल अंक मामूली त्रुटियों के लिए सही हो सकते हैं। (उदाहरण के लिए, भागफल अंक जोड़े (0, +2) और (1, -2) समतुल्य हैं, क्योंकि 0×4+2 = 1×4−2।) यह सहिष्णुता भागफल अंकों को केवल कुछ का उपयोग करके चुनने की अनुमति देती है। पूर्ण-चौड़ाई घटाव की आवश्यकता के बजाय लाभांश और भाजक के सबसे महत्वपूर्ण बिट। बदले में यह सरलीकरण 2 से अधिक मूलांक का उपयोग करने की अनुमति देता है।

गैर-पुनर्स्थापना विभाजन की तरह, अंतिम चरण अंतिम भागफल बिट को हल करने के लिए अंतिम पूर्ण-चौड़ाई घटाव है, और भागफल का मानक बाइनरी रूप में रूपांतरण।

मूल इंटेल पेंटियम (P5 माइक्रोआर्किटेक्चर) प्रोसेसर का पेंटियम FDIV बग | कुख्यात फ़्लोटिंग-पॉइंट डिवीजन बग गलत कोडित तालिका देखो के कारण हुआ था। 1066 प्रविष्टियों में से पांच को गलती से छोड़ दिया गया था।

फास्ट डिवीजन के तरीके

न्यूटन-रैफसन डिवीजन

न्यूटन-रैफसन का गुणक व्युत्क्रम ज्ञात करने के लिए न्यूटन की विधि का उपयोग करता है $D$ और उस व्युत्क्रम को से गुणा करें $N$ खोजने के लिए final quotient $Q$. न्यूटन-रेफसन डिवीजन के चरण हैं:

1. एक अनुमान की गणना करें $X_{0}$ पारस्परिक के लिए $1/D$ भाजक का $D$.
2. क्रमिक रूप से अधिक सटीक अनुमानों की गणना करें $X_{1},X_{2},\ldots ,X_{S}$ पारस्परिक का। यह वह जगह है जहां कोई न्यूटन-रैफसन पद्धति को इस तरह से नियोजित करता है।
3. भाजक के व्युत्क्रम द्वारा लाभांश को गुणा करके भागफल की गणना करें: $Q=NX_{S}$.

के व्युत्क्रम को खोजने के लिए न्यूटन की विधि को लागू करने के लिए $D$, एक फ़ंक्शन खोजना आवश्यक है $f(X)$ जिसमें शून्य है $X=1/D$. स्पष्ट ऐसा कार्य है $f(X)=DX-1$, लेकिन इसके लिए न्यूटन-रैफसन पुनरावृत्ति अनुपयोगी है, क्योंकि इसके व्युत्क्रम को जाने बिना इसकी गणना नहीं की जा सकती $D$ (इसके अलावा यह पुनरावृत्त सुधारों की अनुमति देने के बजाय एक चरण में सटीक पारस्परिक गणना करने का प्रयास करता है)। कार्य करने वाला कार्य है $f(X)=(1/X)-D$, जिसके लिए न्यूटन-रफसन पुनरावृति देता है

$X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),$

जिससे गणना की जा सकती है $X_{i}$ केवल गुणा और घटाव का उपयोग करना, या दो जुड़े हुए गुणा-जोड़ का उपयोग करना।

गणना के दृष्टिकोण से, भाव $X_{i+1}=X_{i}+X_{i}(1-DX_{i})$ और $X_{i+1}=X_{i}(2-DX_{i})$ समकक्ष नहीं हैं। दूसरी अभिव्यक्ति का उपयोग करते समय 2n बिट्स की सटीकता के साथ एक परिणाम प्राप्त करने के लिए, उत्पाद के बीच की गणना करनी चाहिए $X_{i}$ और $(2-DX_{i})$ की दी गई सटीकता से दोगुनी है $X_{i}$(एन बिट्स)। इसके विपरीत, उत्पाद के बीच $X_{i}$ और $(1-DX_{i})$ केवल n बिट्स की सटीकता के साथ गणना करने की आवश्यकता है, क्योंकि अग्रणी n बिट्स (बाइनरी पॉइंट के बाद)। $(1-DX_{i})$ शून्य हैं।

यदि त्रुटि के रूप में परिभाषित किया गया है $\varepsilon _{i}=1-DX_{i}$, तब:

${\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}$

प्रत्येक पुनरावृत्ति चरण में त्रुटि का यह वर्ग – तथाकथित न्यूटन की विधि#न्यूटन-रैफसन की विधि के व्यावहारिक विचार – इसका प्रभाव यह है कि परिणाम में सही अंकों की संख्या लगभग प्रत्येक पुनरावृत्ति के लिए दोगुनी हो जाती है, एक संपत्ति जो अत्यंत मूल्यवान हो जाती है जब शामिल संख्याओं में कई अंक होते हैं (जैसे बड़े पूर्णांक डोमेन में)। लेकिन इसका मतलब यह भी है कि विधि का प्रारंभिक अभिसरण तुलनात्मक रूप से धीमा हो सकता है, खासकर यदि प्रारंभिक अनुमान $X_{0}$ खराब चुना गया है।

प्रारंभिक अनुमान चुनने की उप-समस्या के लिए $X_{0}$, इसे स्केल करने के लिए भाजक D पर बिट-शिफ्ट लागू करना सुविधाजनक है ताकि 0.5 ≤ D ≤ 1; अंश N पर समान बिट-शिफ्ट लगाने से, यह सुनिश्चित होता है कि भागफल नहीं बदलता है। तब कोई रूप में एक रेखीय सन्निकटन का उपयोग कर सकता है

$X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,$

न्यूटन-रैफसन को इनिशियलाइज़ करने के लिए। अंतराल पर इस सन्निकटन की त्रुटि के निरपेक्ष मान के अधिकतम को कम करने के लिए $[0.5,1]$, प्रयोग करना चाहिए

$X_{0}={48 \over 17}-{32 \over 17}D.\,$

रैखिक सन्निकटन के गुणांक निम्नानुसार निर्धारित किए जाते हैं। त्रुटि का निरपेक्ष मान है $|\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|$. त्रुटि के अधिकतम निरपेक्ष मान का न्यूनतम उपयोग किए गए समदोलन प्रमेय द्वारा निर्धारित किया जाता है $F(D)=1-D(T_{1}+T_{2}D)$. स्थानीय न्यूनतम $F(D)$ तब होता है जब $F'(D)=0$, जिसका समाधान है $D=-T_{1}/(2T_{2})$. उस न्यूनतम पर फ़ंक्शन विपरीत चिह्न का होना चाहिए, जैसा कि अंत बिंदु पर फ़ंक्शन, अर्थात्, $F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))$. दो अज्ञात में दो समीकरणों का एक अनूठा समाधान है $T_{1}=48/17$ और $T_{2}=-32/17$, और अधिकतम त्रुटि है $F(1)=1/17$. इस सन्निकटन का उपयोग करते हुए, प्रारंभिक मान की त्रुटि का निरपेक्ष मान से कम है

$\vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,$

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

चूंकि इस विधि के लिए अभिसरण की दर बिल्कुल द्विघात है, यह उसी का अनुसरण करता है

$S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$

तक के मूल्य की गणना करने के लिए चरण पर्याप्त हैं $P\,$ द्विआधारी स्थान। यह आईईईई एकल परिशुद्धता के लिए 3 और दोहरी परिशुद्धता और विस्तारित परिशुद्धता प्रारूप दोनों के लिए 4 का मूल्यांकन करता है।

स्यूडोकोड

निम्नलिखित के भागफल की गणना करता है N और D सटीकता के साथ P द्विआधारी स्थान:

D को M × 2 के रूप में व्यक्त करेंe जहां 1 ≤ M < 2 (मानक फ़्लोटिंग पॉइंट प्रतिनिधित्व)
द' := डी/2e+1 // 0.5 और 1 के बीच का पैमाना, बिट शिफ्ट / एक्सपोनेंट घटाव के साथ किया जा सकता है
न' := न/2ई+1
X := 48/17 − 32/17 × D' // डी के समान सटीकता के साथ पूर्व-गणना स्थिरांक 

repeat $\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$ times // फिक्स्ड पी के आधार पर प्रीकंप्यूटेड किया जा सकता है

    एक्स := एक्स + एक्स × (1 - डी '× एक्स)
'अंत'
'वापसी' एन '× एक्स

उदाहरण के लिए, डबल-परिशुद्धता फ़्लोटिंग-पॉइंट डिवीजन के लिए, यह विधि 10 गुणा, 9 जोड़ और 2 शिफ्ट का उपयोग करती है।

वैरिएंट न्यूटन-रैफसन डिवीजन

न्यूटन-रफसन विभाजन विधि को निम्नानुसार थोड़ा तेज करने के लिए संशोधित किया जा सकता है। एन और डी को स्थानांतरित करने के बाद ताकि डी [0.5, 1.0] में हो, के साथ आरंभ करें

$X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).$

यह 1/डी के लिए सबसे अच्छा द्विघात फिट है और 1/99 से कम या उसके बराबर त्रुटि का पूर्ण मान देता है। इसे पहली तरह के चेबिशेव बहुपद के तीसरे क्रम के पुन: स्केल किए गए त्रुटि के बराबर बनाने के लिए चुना गया है। गुणांक पूर्व-गणना और हार्ड-कोडेड होना चाहिए।

फिर लूप में, एक पुनरावृत्ति का उपयोग करें जो त्रुटि को घनित करता है।

$E:=1-D\cdot X$

$Y:=X\cdot E$

$X:=X+Y+Y\cdot E.$

Y·E पद नया है।

यदि लूप को तब तक निष्पादित किया जाता है जब तक कि एक्स इसके अग्रणी पी बिट्स पर 1/डी से सहमत नहीं हो जाता है, तो पुनरावृत्तियों की संख्या इससे अधिक नहीं होगी

$\left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil$

जो 2 प्राप्त करने के लिए 99 को घन करने की संख्या है^पी+1. तब

$Q:=N\cdot X$

P बिट्स का भागफल है।

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

गोल्डस्मिथ डिवीजन

गोल्डस्मिथ डिवीजन (रॉबर्ट इलियट गोल्डश्मिड्ट के बाद) लाभांश और भाजक दोनों को एक सामान्य कारक F द्वारा बार-बार गुणा करने की पुनरावृत्त प्रक्रिया का उपयोग करता है_i, इस तरह चुना जाता है कि भाजक 1 में परिवर्तित हो जाता है। यह लाभांश को मांगे गए भागफल क्यू में परिवर्तित करने का कारण बनता है:

$Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.$

गोल्डश्मिड्ट डिवीजन के चरण हैं:

1. गुणन कारक F के लिए एक अनुमान उत्पन्न करें_i.
2. लाभांश और भाजक को F से गुणा करें_i.
3. यदि विभाजक पर्याप्त रूप से 1 के करीब है, तो लाभांश वापस करें, अन्यथा चरण 1 पर लूप करें।

मान लें कि N/D को इस तरह बढ़ाया गया है कि 0 < D < 1, प्रत्येक F_iडी पर आधारित है:

$F_{i+1}=2-D_{i}.$

भाज्य और भाजक को गुणनखंड से गुणा करने पर प्राप्त होता है:

${\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.$

पुनरावृत्तियों की पर्याप्त संख्या k के बाद $Q=N_{k}$.

Goldschmidt पद्धति का उपयोग AMD Athlon CPU और बाद के मॉडल में किया जाता है। इसे एंडरसन अर्ल गोल्डश्मिड्ट पॉवर्स (एईजीपी) एल्गोरिथम के रूप में भी जाना जाता है और इसे विभिन्न आईबीएम प्रोसेसर द्वारा कार्यान्वित किया जाता है। यद्यपि यह न्यूटन-रैफसन कार्यान्वयन के समान दर पर अभिसरण करता है, गोल्डस्मिथ पद्धति का एक लाभ यह है कि अंश और भाजक में गुणा समानांतर में किया जा सकता है।

द्विपद प्रमेय

गोल्डश्मिट विधि का उपयोग उन कारकों के साथ किया जा सकता है जो द्विपद प्रमेय द्वारा सरलीकरण की अनुमति देते हैं। मान लें कि एन/डी को दो की शक्ति से बढ़ाया गया है $D\in ({\tfrac {1}{2}},1]$. हम चुनते हैं $D=1-x$ और $F_{i}=1+x^{2^{i}}$. यह प्रदान करता है

${\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}$.

बाद $n$ कदम $(x\in [0,{\tfrac {1}{2}}))$, भाजक $1-x^{2^{n}}$ तक गोल किया जा सकता है $1$ सापेक्ष त्रुटि के साथ

$\varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}$

जो कि अधिकतम है $2^{-2^{n}}$ कब $x={1 \over 2}$, इस प्रकार न्यूनतम सटीकता प्रदान करता है $2^{n}$ बाइनरी अंक।

बड़े-पूर्णांक तरीके

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

एक स्थिर द्वारा विभाजन

एक निरंतर डी द्वारा विभाजन इसके गुणक व्युत्क्रम द्वारा गुणा के बराबर है। चूँकि हर स्थिर है, इसलिए इसका व्युत्क्रम (1/D) है। इस प्रकार संकलन समय पर एक बार (1/D) के मान की गणना करना संभव है, और रन टाइम पर विभाजन N/D के बजाय गुणन N·(1/D) करें। तैरनेवाला स्थल अंकगणित में (1/D) का उपयोग छोटी समस्या प्रस्तुत करता है, लेकिन पूर्णांक (कंप्यूटर विज्ञान) अंकगणित में पारस्परिक हमेशा शून्य का मूल्यांकन करेगा (यह मानते हुए |D| > 1)।

विशेष रूप से (1/D) का उपयोग करना आवश्यक नहीं है; कोई भी मान (X/Y) जो (1/D) तक कम हो जाता है, का उपयोग किया जा सकता है। उदाहरण के लिए, 3 से विभाजन के लिए, कारक 1/3, 2/6, 3/9, या 194/582 का उपयोग किया जा सकता है। नतीजतन, यदि वाई दो की शक्ति होती तो विभाजन चरण तेजी से दाएं बिट शिफ्ट में कम हो जाता। (एन·एक्स)/वाई के रूप में एन/डी की गणना करने का प्रभाव एक विभाजन को एक गुणा और एक बदलाव से बदल देता है। ध्यान दें कि कोष्ठक महत्वपूर्ण हैं, क्योंकि N·(X/Y) का मूल्यांकन शून्य होगा।

हालाँकि, जब तक D स्वयं दो की शक्ति नहीं है, तब तक कोई X और Y नहीं है जो उपरोक्त शर्तों को पूरा करता हो। सौभाग्य से, (N·X)/Y पूर्णांक अंकगणित में N/D के समान परिणाम देता है, भले ही (X/Y) 1/D के बिल्कुल बराबर न हो, लेकिन इतना करीब हो कि सन्निकटन द्वारा प्रस्तुत त्रुटि में हो बिट्स जो शिफ्ट ऑपरेशन द्वारा छोड़े गए हैं। बैरेट रिडक्शन वाई के मान के लिए 2 की शक्तियों का उपयोग करता है ताकि वाई द्वारा विभाजन को एक सरल दायां शिफ्ट बनाया जा सके। एक ठोस निश्चित-बिंदु अंकगणितीय उदाहरण के रूप में, 32-बिट अहस्ताक्षरित पूर्णांकों के लिए, 3 से विभाजन को गुणा द्वारा प्रतिस्थापित किया जा सकता है 2863311531/2³³, 2863311531 (हेक्साडेसिमल 0xAAAAAAAB) द्वारा एक गुणा और उसके बाद 33 दाएँ बिट शिफ़्ट। 2863311531 के मान की गणना इस प्रकार की जाती है 2³³/3, फिर गोल किया। इसी तरह, 10 से विभाजन को 3435973837 (0xCCCCCCCD) के गुणन के बाद 2 से विभाजन के रूप में व्यक्त किया जा सकता है³⁵ (या 35 राइट बिट शिफ्ट)। OEIS गुणन के लिए स्थिरांकों के अनुक्रम प्रदान करता है A346495 और सही बदलाव के लिए A346496.

सामान्य के लिए $x$-बिट अहस्ताक्षरित पूर्णांक विभाजन जहां विभाजक $D$ 2 की शक्ति नहीं है, निम्नलिखित पहचान विभाजन को दो में परिवर्तित करती है $x$-बिट जोड़/घटाव, एक $x$-बिट द्वारा $x$-बिट गुणन (जहां परिणाम के केवल ऊपरी आधे हिस्से का उपयोग किया जाता है) और कई बदलाव, प्रीकंप्यूटिंग के बाद $k=x+\lceil \log _{2}{D}\rceil$ और $a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}$:

$\left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor$ कहाँ $b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor$ कुछ मामलों में, एक स्थिरांक द्वारा विभाजन को और भी कम समय में गुणन को एक गुणन एल्गोरिथम #Shift और add में एक स्थिरांक द्वारा परिवर्तित करके पूरा किया जा सकता है। विशेष रुचि 10 से विभाजन है, जिसके लिए यदि आवश्यक हो तो शेष के साथ, सटीक भागफल प्राप्त किया जाता है।

राउंडिंग एरर

सीमित परिशुद्धता (कंप्यूटर विज्ञान) के कारण डिवीजन संचालन द्वारा राउंड-ऑफ त्रुटि पेश की जा सकती है।

Further information: Floating point

यह भी देखें

• गैली डिवीजन
• गुणन एल्गोरिथ्म
• पेंटियम FDIV बग

अग्रिम पठन

• Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.