प्रभाग एल्गोरिथ्म

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.

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

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

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

चर्चा प्रपत्र का संदर्भ लेगी $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: Long division § Algorithm for arbitrary base

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

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

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

Main article: Long division § Binary division

See also: Binary number § Division

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

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- Initialize quotient and remainder to zero
R := 0                     
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

उदाहरण

यदि हम N=1100 लेते हैं₂ (12₁₀) और डी=100₂ (4₁₀)

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

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

चरण 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) पुनर्स्थापना विभाजन के लिए मूल एल्गोरिदम है:

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
  if R >= 0 then
    q(i) := 1          -- Result-bit 1
  else
    q(i) := 0          -- Result-bit 0
    R := R + D         -- New partial remainder is (restored) shifted value
  end
end

-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient

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

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

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

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do  -- for example 31..0 for 32 bits
  if R >= 0 then
    q(i) := +1
    R := 2 * R − D
  else
    q(i) := −1
    R := 2 * R + D
  end if
end
 
-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

इस एल्गोरिथम का अनुसरण करते हुए, भागफल एक गैर-मानक रूप में होता है जिसमें -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)      -- Appropriate if −1 digits in Q are represented as zeros as is common.

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

if R < 0 then
  Q := Q − 1
  R := R + D  -- Needed only if the remainder is of interest.
end if

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

एसआरटी प्रभाग

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

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

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

मूल इंटेल पेंटियम (पी5 माइक्रोआर्किटेक्चर) प्रोसेसर का पेंटियम 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}$, इसे स्केल करने के लिए विभाजक डी पर बिट-शिफ्ट लागू करना सुविधाजनक है ताकि 0.5≤डी≤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\,$ द्विआधारी स्थान. यह IEEE एकल परिशुद्धता के लिए 3 और डबल परिशुद्धता और विस्तारित परिशुद्धता प्रारूप दोनों के लिए 4 का मूल्यांकन करता है।

छद्म कोड

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

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

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 शब्द नया है.

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

$\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:

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

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

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

यह मानते हुए कि एन/डी को स्केल किया गया है ताकि 0 <डी<1, प्रत्येक एफ_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}$.

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

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

गोल्डस्मिड्ट विधि का उपयोग उन कारकों के साथ किया जा सकता है जो द्विपद प्रमेय द्वारा सरलीकरण की अनुमति देते हैं। मान लीजिए $N/D$ को ऐसे दो की घात द्वारा बढ़ाया गया है $D\in \left({\tfrac {1}{2}},1\right]$. हम चुनते हैं $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 कदम $\left(x\in \left[0,{\tfrac {1}{2}}\right)\right)$, हर $1-x^{2^{n}}$ तक गोल किया जा सकता है 1 सापेक्ष त्रुटि के साथ

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

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

बड़ी-पूर्णांक विधियाँ

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

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

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

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

हालाँकि, जब तक D स्वयं दो की घात नहीं है, कोई X और Y नहीं है जो उपरोक्त शर्तों को पूरा करता हो। सौभाग्य से, (एन·एक्स)/वाई पूर्णांक अंकगणित में एन/डी के समान ही परिणाम देता है, भले ही (एक्स/वाई) बिल्कुल 1/डी के बराबर न हो, लेकिन इतना करीब हो कि सन्निकटन द्वारा प्रस्तुत त्रुटि में हो शिफ्ट ऑपरेशन द्वारा छोड़े गए बिट्स। बैरेट कटौती Y के मान के लिए 2 की शक्तियों का उपयोग करती है ताकि Y द्वारा विभाजन को एक सरल दायां बदलाव बनाया जा सके।

एक ठोस निश्चित-बिंदु अंकगणितीय उदाहरण के रूप में, 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 {\text{ where }}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.