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

विभाजन एल्गोरिदम एक ऐसा एल्गोरिदम है जो यूक्लिडियन विभाजन के दिये गए दो पूर्णांक परिणाम 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
DD:= D << n            -- R और D को N और Q की शब्द चौड़ाई की दोगुनी आवश्यकता होती है
for i := n − 1 .. 0 do  -- उदाहरण 31..0 के लिए 32 बिट
  R := 2 * R − D          -- स्थानांतरित मान से परीक्षण घटाव (2 से गुणा करना बाइनरी प्रतिनिधित्व में परिवर्तन है)
  if R >= 0 then
    q(i) := 1          -- परिणामी बिट 1
  else
    q(i) := 0          -- परिणामी बिट 0
    R0:= 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 के बिट्स का उत्पादन होता है और दोनों के लिए एकल विस्थापन रजिस्टर का उपयोग करना सामान्य है।)

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

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

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

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

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

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

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

न्यूटन-रैफसन विभाजन

न्यूटन-रैफसन का गुणक व्युत्क्रम ज्ञात करने के लिए न्यूटन की विधि का उपयोग करता है $D$ और उस व्युत्क्रम को $N$ से गुणा करके अंतिम भागफल $Q$ज्ञात करें।

न्यूटन-रेफसन विभाजन के निम्न चरण हैं:

1. भाजक $X_{0}$ के व्युत्क्रम $D$ के लिए एक अनुमान $1/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 बिट्स की सटीकता के साथ गणना करने की आवश्यकता है, क्योंकि $(1-DX_{i})$ के प्रमुख n बिट्स (बाइनरी बिंदु के बाद) शून्य हैं।

यदि त्रुटि को $\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 का मानांकन करता है।

स्यूडोकोड

निम्नलिखित P बाइनरी स्थानों की परिशुद्धता के साथ N और D के भागफल की गणना करता है:

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  times   // can be precomputed based on fixed P
    X := X + X × (1 - D' × X)
end
return N' × X

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

वैरिएंट न्यूटन-रैफसन विभाजन

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

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

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

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

$E:=1-D\cdot X$

$Y:=X\cdot E$

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

इसमे Y·E एक नया पद है।

यदि पाश को तब तक निष्पादित किया जाता है जब तक कि x इसके प्रमुख P बिट्स पर 1/D से सहमत नहीं हो जाता है, तब पुनरावृत्तियों की संख्या इससे अधिक नहीं होती है।

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

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

$Q:=N\cdot X$

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

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

गोल्डश्मिट विभाजन

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

$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 D पर आधारित है:

$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}}}.$

पुनरावृत्तियों $Q=N_{k}$ की पर्याप्त संख्या k के बाद गोल्डश्मिट पद्धति का उपयोग एएमD एथलॉन सीपीयू और बाद के मॉडल में किया जाता है। इसे एंडरसन अर्ल गोल्डश्मिड्ट पॉवर (एईजीपी) एल्गोरिथम के रूप में भी जाना जाता है और इसे विभिन्न आईबीएम प्रोसेसर द्वारा कार्यान्वित किया जाता है। यद्यपि यह न्यूटन-रैफसन कार्यान्वयन के समान दर पर अभिसरण करता है, गोल्डश्मिट पद्धति का एक लाभ यह है कि अंश और भाजक में गुणा समानांतर में किया जा सकता है।

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

गोल्डश्मिट विधि का उपयोग उन कारकों के साथ किया जा सकता है जो द्विपद प्रमेय द्वारा सरलीकरण की स्वीकृति देते हैं।

माना कि N/D को दो की घात से बढ़ाया गया है $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}$ बाइनरी अंक प्रदान करता है।

विस्तृत-पूर्णांक विधि

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

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

एक निरंतर D द्वारा विभाजन इसके गुणक व्युत्क्रम द्वारा गुणा के बराबर होता है। चूँकि हर स्थिर होता है, इसलिए इसका व्युत्क्रम (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 का उपयोग किया जा सकता है। जिसके परिणामस्वरूप यदि Y की घात 2 होती है तो विभाजन चरण तीव्रता से दाएं बिट शिफ्ट में कम हो जाता है (N·X)/Y के रूप में N/D की गणना करने का प्रभाव एक विभाजन को एक गुणा मे परिवर्तित कर देता है। ध्यान दें कि कोष्ठक महत्वपूर्ण हैं, क्योंकि N·(X/Y) का मानांकन शून्य होगा।

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

सामान्य के लिए $x$-बिट अहस्ताक्षरित पूर्णांक विभाजन जहां विभाजक $D$ दो की घात नहीं है निम्नलिखित पहचान विभाजन को $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 से विभाजन है, जिसके लिए यदि आवश्यक हो तो शेष के साथ, सटीक भागफल प्राप्त किया जाता है।

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

पूरक त्रुटि

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

Further information: अस्थिर बिन्दु

यह भी देखें

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

अग्रिम पठन

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