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

This article is about पूर्णांकों के विभाजन के लिए एल्गोरिदम. For पेंसिल और पेपर एल्गोरिदम, see लम्बा विभाजन. For एक अद्वितीय भागफल और शेष के अस्तित्व को सिद्ध करने वाला प्रमेय, see यूक्लिडियन विभाजन. For बहुपदों के लिए विभाजन एल्गोरिथ्म, see बहुपदीय विभाजन.

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

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

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

$N/D=(Q,R)$ एक उपयुक्त समीकरण को प्रदर्शित करता है -

जहाँ पर

• N = अंश (लाभांश)
• D = हर (भाजक)

• Q = भागफल
• R = शेषफल

पुनरावर्ती घटाव द्वारा विभाजन

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

 R:= N Q:= 0
while R ≥ D do
  R:= R − D
  Q:= Q + 1
end
return (Q,R)

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

 function divide(N, D)  if D = 0 then error(DivisionByZero) end
  if D < 0 then (Q, R):= divide(N, −D); return (−Q, R) end
  if N < 0 then
    (Q,R):= divide(−N, D)
    if R = 0 then return (−Q, 0)
    else return (−Q − 1, D − R) end
  end
  -- At this point, N ≥ 0 and D > 0
  return divide_unsigned(N, D)
end  
function divide_unsigned(N, D)
  Q:= 0; R:= N
  while R ≥ D do
    Q:= Q + 1
    R:= R − D
  end
  return (Q, R)
end

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

विस्तृत विभाजन

Main article: विस्तृत विभाजन §  यादृच्छिक आधार के लिए एल्गोरिथम

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

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

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

Main article: विस्तृत विभाजन §  बाइनरी विभाजन

See also: बाइनरी संख्या § विभाजन

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

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- भागफल और शेष को शून्य पर प्रारंभ करें
R := 0                     
for i := n − 1 .. 0 do  -- जहाँ n, N में बिट्स की संख्या है
  R := R << 1           -- लेफ्ट-शिफ्ट R 1 बिट 
  R(0) := N(i)          -- अंश के i बिट के बराबर R का न्यूनतम-सार्थक बिट समुच्चय
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

उदाहरण

यदि N=11002 (1210) and D=1002 (410) 

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

चरण 2: समुच्चय i=2
चरण 3: R = 010 
चरण 4: R = 011 
चरण 5: R <D इस कथन को छोड़ दे

चरण 2: समुच्चय i=1 
चरण 3: R = 0110 
चरण 4: R = 0110 
चरण 5: R>=D, कथन को लिखा गया है
चरण 5b: R=10 (R−D)
चरण 5c: Q=10 (समुच्चय Q(i) to 1)

चरण 2: समुच्चय i=0 
चरण 3: R = 100 
चरण 4: R = 100 
चरण 5: R>=D, कथन को लिखा गया है 
चरण 5b: R=0 (R−D)
चरण 5c: Q=11 (समुच्चय Q(i) to 1)

end: Q=112 (310) और R=0.

मध्यम विभाजन विधियाँ

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

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

जहाँ पर

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

प्रत्यानयन विभाजन

• प्रत्यानयन विभाजन निश्चित-बिंदु भिन्नात्मक संख्याओं पर संचालित होता है और काल्पनिक संख्या 0 <D <N पर निर्भर करता है।
• भागफल अंक q अंक समुच्चय {0,1} से बनते हैं।
• बाइनरी (सूत्र 2) प्रत्यानयन विभाजन के लिए मूल एल्गोरिथम है:

R := N
D := D << n            -- R और D को N और Q की शब्द चौड़ाई की दोगुनी आवश्यकता होती है
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- स्थानांतरित मान से परीक्षण घटाव (2 से गुणा करना बाइनरी प्रतिनिधित्व में परिवर्तन है)
  if R >= 0 then
    q(i) := 1          -- परिणामी बिट 1
  else
    q(i) := 0          -- परिणामी बिट 0
    R := R + D         -- नया आंशिक शेषफल (पुनर्स्थापना) स्थानांतरित मान है
  end
end

 जहाँ: N=अंश, D=भाजक, n=#बिट्स, R=आंशिक शेष, q(i)=भागफल का बिट

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

गैर-प्रत्यानयन विभाजन

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

R := N
D := D << n            -- R और D को N और Q की शब्द चौड़ाई की दोगुनी आवश्यकता होती है
for i = n − 1 .. 0 do  -- उदाहरण 31..0 के लिए 32 बिट
  if R >= 0 then
    q(i) := +1
    R := 2 * R − D
  else
    q(i) := −1
    R := 2 * R + D
  end if
end
 जहाँ: N=अंश, D=भाजक, n=#बिट्स, R=आंशिक शेष, q(i)=भागफल का बिट

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

निम्न भागफल को अंकों के समुच्चय {0,1} में बदलें:
प्रारम्भ	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1.धनात्मक मान	$P=11101010\,$
2. ऋणात्मक शब्द का मास्क मान	$M=00010101\,$
3. व्यवकलन : $P-M$:	$Q=11010101\,$
*.दो पूरक के अतिरिक्त किसी एक पूरक के साथ हस्ताक्षरित बाइनरी संकेत

यदि −1 के अंक $Q$ को शून्य (0) के रूप में संग्रहीत किया जाता है जैसा कि सामान्य $P$, $Q$ और कंप्यूटिंग $M$ तुच्छ मान है जो मूल $Q$ पर एक पूरक (बिट पूरक) है।

 Q:= Q − bit.bnot(Q)      -- यदि उपयुक्त Q में -1 अंक को शून्य के रूप में दर्शाया जाता है जैसा कि सामान्य है।

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

if R < 0 then
  Q:= Q − 1
  R:= R + D  -- यह केवल तभी आवश्यक है जब शेष ब्याज का हो।
end if

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

एसआरटी विभाजन

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

एसआरटी विभाजन गैर-प्रत्यानयन विभाजन के समान होता है लेकिन यह प्रत्येक भागफल अंक निर्धारित करने के लिए लाभांश और भाजक के आधार पर एक लुकअप तालिका का उपयोग करता है।

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

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

मूल इंटेल पेंटियम (P5 माइक्रोआर्किटेक्चर) प्रोसेसर का कुख्यात फ़्लोटिंग-पॉइंट विभाजन बग (एफडीआईवी) गलत कोडित लुकअप तालिका के कारण हुआ था। 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 द्विआधारी स्थान:

Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation)
D' := D / 2e+1   // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
N' := N / 2e+1
X := 48/17 − 32/17 × D'   // precompute constants with same precision as D
repeat $\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$ times  // can be precomputed based on fixed P
    X := X + X × (1 - D' × X)
end
return N' × X

उदाहरण के लिए, डबल-परिशुद्धता फ़्लोटिंग-पॉइंट विभाजन के लिए, यह विधि 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

यह भी देखें

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

अग्रिम पठन

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