خوارزمية القسمة

يقوم تطبيق بديل بزيادة الباقي وإعادة ضبطه عندما يصل إلى المقسوم عليه.

ل${\displaystyle x,y\in \mathbb {N} _{0}}$، تقوم الخوارزمية بحساب${\displaystyle q,r\,}$بحيث${\displaystyle x=qy+r\,}$، مع${\displaystyle 0\leq r<y}$:

${\displaystyle \operatorname {div} (x,y)=\left\lfloor x/y\right\rfloor }$

${\displaystyle x{\bmod {y}}=xy\left\lfloor x/y\right\rfloor }$

انظر إلى هذا الكود المكتوب بلغة بايثون :

دالة ` divide_unsigned2` ( البسط : عدد صحيح ، المقام : عدد صحيح ) -> tuple [ عدد صحيح ، عدد صحيح ] الناتج : عدد صحيح = 0 الباقي : عدد صحيح = 0 لكل _ في نطاق ( البسط ) : الباقي += 1 إذا كان الباقي يساوي المقام : الناتج + = 1 الباقي = 0 ...

ملحوظات

• الحالات الخاصة هي

${\displaystyle x{\bmod {1}}=0}$و${\displaystyle x{\bmod {0}}=x}$[ ^{2 ]​}

• لا تتم قراءة المتغير quotientمطلقًا. لذا، عند إزالة قيمه المُسندة - المُظللة - من الكود وإزالته quotientمن قائمة الإخراج، فإن دالة divide_unsigned2 ، مثل دالة divide_unsigned ، ستظل تُحسب.${\displaystyle x{\bmod {y}}}$.

التنفيذ البديل كآلة عدّ: يمكن بناء آلة عدّ بسيطة (CM) على التنفيذ البديل. تعليمات آلة العدّ هي ^{[ 3 ] [ 4 ]}

• Z (n): استبدل r _n بـ 0.
• S (n): أضف 1 إلى r _n .
• J (m, n, q): إذا كان r _m = r _n ، انتقل إلى التعليمات رقم q؛ وإلا فانتقل إلى التعليمات التالية في البرنامج.

برنامج آلة العد هو ^{[ 5 ]}

1: J(1,5,0) 2: S(4) 3: J(4,2,6) 4: S(5) 5: J(0,0,1) 6: S(3) 7: Z(4) 8: S(5) 9: J(0,0,1) 

بعد أن ينتهي المعالج من الحساب على قيم السجلات الأولية R1=N، R2=D (السجلات المتبقية = 0)،

يحتوي المسجل R3 على الجزء الصحيح من ناتج قسمة N/D، و

يحتفظ السجل R4 بالباقي.

ستقوم الخوارزمية التالية، وهي النسخة الثنائية من عملية القسمة المطولة الشهيرة ، بقسمة N على D ، ووضع الناتج في Q والباقي في R. في الشفرة الزائفة التالية، تُعامل جميع القيم كأعداد صحيحة غير مُوقّعة.

إذا كانت D = 0، فسيتم تنفيذ خطأ ( DivisionByZeroException ). Q : = 0 -- تهيئة ناتج القسمة والباقي إلى الصفر. R : = 0 for i : = n − 1 .. 0 do -- حيث n هو عدد البتات في N. R : = R << 1 -- إزاحة R إلى اليسار بمقدار بت واحد. R ( 0 ) : = N ( i ) -- تعيين أقل بت أهمية في R مساويًا للبت i من البسط. إذا كانت R ≥ D، فسيتم تنفيذ ما يلي: R : = R − D. Q ( i ) : = 1 end end

تعتمد عملية القسمة الاسترجاعية على الأعداد الكسرية ذات النقطة الثابتة وتعتمد على الافتراض 0 < D < N.

يتم تكوين أرقام القسمة q من مجموعة الأرقام {0,1}.

الخوارزمية الأساسية لعملية القسمة الثنائية (الأساس 2) هي:

R : = N D : = 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 R : = R + D -- الباقي الجزئي الجديد هو القيمة المُزاحة (المُستعادة) end endحيث: N = البسط، D = المقام، n = عدد البتات، R = الباقي الجزئي، q(i) = البت رقم i من ناتج القسمة

القسمة الاستعادة غير الفعالة تشبه القسمة الاستعادة باستثناء أنه يتم حفظ قيمة 2R، لذلك لا يلزم إضافة D مرة أخرى في حالة R < 0.

تستخدم عملية القسمة غير المُستعادة مجموعة الأرقام { −1 , 1} لأرقام ناتج القسمة بدلاً من {0, 1}. ورغم أن هذه الخوارزمية أكثر تعقيدًا، إلا أنها تتميز عند تطبيقها على الأجهزة بوجود عملية قرار واحدة فقط وعملية جمع/طرح واحدة لكل بت من بتات ناتج القسمة؛ فلا توجد خطوة استعادة بعد الطرح، ^{[ 7 ]} مما يُقلل عدد العمليات إلى النصف تقريبًا ويُسرّع تنفيذها. ^{[ 8 ]} الخوارزمية الأساسية للقسمة غير المُستعادة للأعداد غير السالبة في النظام الثنائي (الأساس 2) هي:

-- المدخلات: N (البسط)، D (المقام) -- n = عدد البتات عادةً ما يتم تخزين R و D في سجلات بعرض 2n أو ما شابه ذلك للتعامل مع عمليات الإزاحةR : = N -- تهيئة الباقيfor i = n − 1 .. 0 do -- على سبيل المثال 31..0 لـ 32 بت -- إزاحة الباقي إلى اليسار (جبريًا: 2 * R) if R >= 0 then R : = 2 * R - D ; -- طرح D q ( i ) : = 1 ; -- تسجيل بت الناتج كـ 1 else R : = 2 * R + D ; -- إضافة D (استعادة) q ( i ) : = - 1 ; -- تسجيل بت الناتج كـ -1 end if end for

باتباع هذه الخوارزمية، يكون ناتج القسمة بصيغة غير قياسية تتكون من الرقمين -1 و+1. يجب تحويل هذه الصيغة إلى النظام الثنائي للحصول على ناتج القسمة النهائي. مثال:

حوّل ناتج القسمة التالي إلى مجموعة الأرقام {0,1}:
يبدأ:	${\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}$
1. تكوين الحد الموجب:	${\displaystyle P=11101010\,}$
2. إخفاء الحد السالب: [ ملاحظة 1 ]	${\displaystyle M=00010101\,}$
3. اطرح:${\displaystyle P-M}$:	${\displaystyle Q=11010101\,}$
↑ تدوين ثنائي موقّع مع المتمم الأحادي بدون المتمم الثنائي .

إذا كانت الأرقام -1 من${\displaystyle Q}$يتم تخزينها على شكل أصفار (0) كما هو شائع، ثم${\displaystyle P}$يكون${\displaystyle Q}$والحوسبة${\displaystyle M}$الأمر بسيط: قم بإجراء عملية المتمم الأحادي (المتمم بتًا بتًا) على الأصل${\displaystyle Q}$.

Q : = Q − bit . bnot ( Q ) -- مناسب إذا تم تمثيل الأرقام -1 في Q كأصفار كما هو شائع.

أخيرًا، تكون نواتج القسمة المحسوبة بهذه الخوارزمية فردية دائمًا، ويكون الباقي في R ضمن النطاق −D ≤ R < D. على سبيل المثال، 5 / 2 = 3R − 1. لتحويل الباقي إلى قيمة موجبة، قم بخطوة استعادة واحدة بعد تحويل Q من الصيغة غير القياسية إلى الصيغة القياسية.

إذا كان R < 0 فإن Q : = Q − 1 و R : = R + D -- مطلوب فقط إذا كان الباقي هو المطلوب. نهاية الشرط

الباقي الفعلي هو R >> n. (كما هو الحال مع القسمة الاسترجاعية، يتم استخدام البتات ذات الترتيب الأدنى من R بنفس معدل إنتاج بتات ناتج القسمة Q، ومن الشائع استخدام مسجل إزاحة واحد لكليهما.)

تُعدّ قسمة SRT طريقة شائعة للقسمة في العديد من تطبيقات المعالجات الدقيقة . ^{[ 9 ] [ 10 ]} سُمّيت الخوارزمية نسبةً إلى دي دبليو سويني من شركة IBM ، وجيمس إي روبرتسون من جامعة إلينوي ، وكيه دي توشر من إمبريال كوليدج لندن . وقد طوّروا جميعًا الخوارزمية بشكل مستقل في نفس الفترة الزمنية تقريبًا (نُشرت في فبراير 1957، وسبتمبر 1958، ويناير 1958 على التوالي). ^{[ 11 ] [ 12 ] [ 13 ]}

القسمة SRT تشبه القسمة غير المستعادة، ولكنها تستخدم جدول بحث يعتمد على المقسوم والمقسوم عليه لتحديد كل رقم من أرقام ناتج القسمة.

يتمثل الاختلاف الأهم في استخدام تمثيل زائد للناتج. فعلى سبيل المثال، عند تطبيق قسمة SRT ذات الأساس 4، يُختار كل رقم من أرقام الناتج من بين خمسة احتمالات: -2، -1، 0، +1، أو +2. ولهذا السبب، لا يشترط أن يكون اختيار رقم الناتج مثاليًا؛ إذ يمكن للأرقام اللاحقة تصحيح الأخطاء الطفيفة. (على سبيل المثال، زوجا أرقام الناتج (0،  +2) و(1،  -2) متكافئان، لأن 0 × 4 + 2 = 1 × 4 - 2 ). يسمح هذا التسامح باختيار أرقام الناتج باستخدام عدد قليل فقط من البتات الأكثر أهمية في المقسوم والمقسوم عليه، بدلًا من الحاجة إلى طرح كامل العرض. وهذا التبسيط بدوره يسمح باستخدام أساس أكبر من 2.

مثل القسمة غير المستعادة، فإن الخطوات النهائية هي طرح كامل العرض لحل بت القسمة الأخير، وتحويل القسمة إلى الشكل الثنائي القياسي.

كان سبب خطأ قسمة الأعداد العشرية الشهير في معالج إنتل بنتيوم الأصلي هو جدول بحث مُبرمج بشكل خاطئ. استخدمت معالجات بنتيوم جدولًا مكونًا من 2048 خلية، وكان من المفترض ملء 1066 خلية منها، ولكن تم حذف قيم من خمس خلايا عن طريق الخطأ. ^{[ 14 ] [ 15 ] [ 16 ]}

تستخدم طريقة نيوتن-رافسون طريقة نيوتن لإيجاد مقلوب${\displaystyle D}$واضرب ذلك المقلوب في${\displaystyle N}$لإيجاد ناتج القسمة النهائي${\displaystyle Q}$.

خطوات قسمة نيوتن-رافسون هي:

1. احسب تقديرًا${\displaystyle X_{0}}$للمقابل${\displaystyle 1/D}$من المقسوم عليه${\displaystyle D}$.
2. حساب تقديرات أكثر دقة بشكل متتابع${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$من المقلوب. وهنا يتم استخدام طريقة نيوتن-رافسون على هذا النحو.
3. احسب ناتج القسمة بضرب المقسوم في مقلوب المقسوم عليه:${\displaystyle Q=NX_{S}}$.

من أجل تطبيق طريقة نيوتن لإيجاد مقلوب${\displaystyle D}$، من الضروري إيجاد دالة${\displaystyle f(X)}$الذي يحتوي على صفر في${\displaystyle X=1/D}$الدالة الواضحة من هذا النوع هي${\displaystyle f(X)=DX-1}$لكن تكرار نيوتن-رافسون لهذا الأمر غير مفيد، لأنه لا يمكن حسابه دون معرفة مقلوبه مسبقًا.${\displaystyle D}$(علاوة على ذلك، تحاول هذه الطريقة حساب المقلوب الدقيق في خطوة واحدة، بدلاً من السماح بالتحسينات التكرارية). إحدى الدوال التي تعمل بشكل صحيح هي${\displaystyle f(X)=(1/X)-D}$، والتي تعطيها عملية التكرار نيوتن-رافسون

$${\displaystyle 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}),}$$

والتي يمكن حسابها من${\displaystyle X_{i}}$باستخدام الضرب والطرح فقط، أو باستخدام عمليتي الضرب والجمع المدمجتين .

من وجهة نظر حسابية، فإن التعبيرات${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}$و${\displaystyle X_{i+1}=X_{i}(2-DX_{i})}$ليست متكافئة. للحصول على نتيجة بدقة 2^ n بت مع استخدام التعبير الثاني، يجب حساب حاصل الضرب بين${\displaystyle X_{i}}$و${\displaystyle (2-DX_{i})}$بدقة مضاعفة لـ${\displaystyle X_{i}}$( ن بت). في المقابل، يكون الناتج بين${\displaystyle X_{i}}$و${\displaystyle (1-DX_{i})}$يكفي حسابها بدقة n بت، لأن البتات n الأولى (بعد الفاصلة الثنائية) من${\displaystyle (1-DX_{i})}$هي أصفار.

إذا تم تعريف الخطأ على النحو التالي${\displaystyle \varepsilon _{i}=1-DX_{i}}$، ثم:

${\displaystyle {\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}}}$

يؤدي تربيع الخطأ في كل خطوة تكرارية - ما يُعرف بالتقارب التربيعي لطريقة نيوتن-رافسون - إلى مضاعفة عدد الأرقام الصحيحة في النتيجة تقريبًا مع كل تكرار ، وهي خاصية بالغة الأهمية عندما تحتوي الأعداد المعنية على العديد من الأرقام (كما هو الحال في مجال الأعداد الصحيحة الكبيرة). ولكن هذا يعني أيضًا أن التقارب الأولي للطريقة قد يكون بطيئًا نسبيًا، خاصةً إذا كانت التقديرات الأولية  ${\displaystyle X_{0}}$اختيار سيء.

التقدير الأولي

بالنسبة للمسألة الفرعية المتمثلة في اختيار تقدير أولي${\displaystyle X_{0}}$من الملائم تطبيق إزاحة بتية على المقسوم عليه D لتغيير مقياسه بحيث يكون 0.5  ≤ D ≤ 1. تطبيق الإزاحة البتية نفسها على البسط N يضمن عدم تغيير الناتج. بمجرد الوصول إلى نطاق محدود، يمكن استخدام تقريب متعدد الحدود بسيط لإيجاد تقدير أولي.   

التقريب الخطي ذو أقل خطأ مطلق في أسوأ الحالات على الفترة${\displaystyle [0.5,1]}$يكون:

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

معاملات التقريب الخطي${\displaystyle T_{0}+T_{1}D}$يتم تحديدها على النحو التالي. القيمة المطلقة للخطأ هي${\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}$يتم تحديد الحد الأدنى للقيمة المطلقة القصوى للخطأ بواسطة نظرية تشيبيشيف للتوازن المطبق على${\displaystyle F(D)=1-D(T_{0}+T_{1}D)}$الحد الأدنى المحلي لـ${\displaystyle F(D)}$يحدث ذلك عندما${\displaystyle F'(D)=0}$، والذي له حل${\displaystyle D=-T_{0}/(2T_{1})}$يجب أن تكون إشارة الدالة عند تلك القيمة الدنيا معاكسة لإشارة الدالة عند نقطتي النهاية، أي${\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}$للمعادلتين في المجهولين حل وحيد${\displaystyle T_{0}=48/17}$و${\displaystyle T_{1}=-32/17}$، والخطأ الأقصى هو${\displaystyle F(1)=1/17}$باستخدام هذا التقريب، تكون القيمة المطلقة لخطأ القيمة الأولية أقل من

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

أفضل معادلة تربيعية لـ${\displaystyle 1/D}$في الفترة

${\displaystyle X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.}$

تم اختيار هذه الطريقة لجعل الخطأ مساويًا لكثير حدود تشيبيشيف من الدرجة الثالثة المعاد قياسها من النوع الأول، مما يعطي قيمة مطلقة للخطأ أقل من أو تساوي 1/99. هذا التحسين يعادل${\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}$تكرارات نيوتن-رافسون، بتكلفة حسابية أقل من تكرار واحد.

من الممكن توليد معادلة متعددة الحدود من الدرجة الثانية أو أعلى، وذلك بحساب المعاملات باستخدام خوارزمية ريميز . ويكمن المقابل في أن التخمين الأولي يتطلب دورات حسابية أكثر، ولكن يُؤمل أن يكون ذلك في المقابل بتقليل عدد تكرارات خوارزمية نيوتن-رافسون.

بما أن التقارب في هذه الطريقة يكون تربيعيًا تمامًا، فإنه يترتب على ذلك أنه، انطلاقًا من خطأ أولي${\displaystyle \varepsilon _{0}}$،${\displaystyle S}$ستعطي التكرارات إجابة دقيقة لـ

${\displaystyle P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1}$

المنازل الثنائية. القيم النموذجية هي:

الأرقام الثنائية ذات الدقة المتبادلة

${\displaystyle \varepsilon _{0}}$	التكرارات
	0	1	2	3	4
${\displaystyle 1/17}$	3.09	7.17	15.35	31.70	64.40
${\displaystyle 1/99}$	5.63	12.26	25.52	52.03	105.07

يُعدّ التقدير الأولي التربيعي بالإضافة إلى تكرارين كافيًا لدقة IEEE المفردة ، بينما يُعدّ ثلاثة تكرارات غير كافية للدقة المزدوجة . أما التقدير الأولي الخطي بالإضافة إلى أربعة تكرارات فهو كافٍ لكل من صيغتي الدقة المزدوجة والمزدوجة الموسعة .

التكرار التكعيبي

هناك تكرار يستخدم ثلاث عمليات ضرب لتكعيب الخطأ:

${\displaystyle \varepsilon _{i}=1-DX_{i}}$

${\displaystyle Y_{i}=X_{i}\varepsilon _{i}}$

${\displaystyle X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.}$

مصطلح Y _i ε _i جديد.

بتوسيع ما سبق،${\displaystyle X_{i+1}}$يمكن كتابتها على النحو التالي

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

ونتيجة لذلك، فإن حد الخطأ

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

هذا يمثل 3/2 من حساب التكرار التربيعي، ولكنه يحقق${\displaystyle \log 3/\log 2\approx 1.585}$يُحقق هذا الأسلوب نفس القدر من التقارب، لذا فهو أكثر كفاءةً بشكل طفيف. بعبارة أخرى، يؤدي تكراران لهذا الأسلوب إلى رفع الخطأ إلى القوة التاسعة بنفس التكلفة الحسابية لثلاثة تكرارات تربيعية، والتي ترفع الخطأ إلى القوة الثامنة فقط.

عدد البتات الصحيحة بعد${\displaystyle S}$التكرارات هي

${\displaystyle P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1}$

المنازل الثنائية. القيم النموذجية هي:

بعض الدقة المتبادلة

${\displaystyle \varepsilon _{0}}$	التكرارات
	0	1	2	3
${\displaystyle 1/17}$	3.09	11.26	35.79	109.36
${\displaystyle 1/99}$	5.63	18.89	58.66	177.99

يُوفر التقدير الأولي التربيعي بالإضافة إلى تكرارين تكعيبيين دقة كافية للحصول على نتيجة ذات دقة مزدوجة وفقًا لمعيار IEEE. كما يُمكن استخدام مزيج من التكرارات التربيعية والتكعيبية.

يضمن استخدام تكرار تربيعي واحد على الأقل أن يكون الخطأ موجبًا، أي أن المقلوب يُقلل من قيمته الحقيقية. ^{[ 17 ] : 370} وهذا يُسهّل خطوة التقريب اللاحقة إذا لزم الحصول على ناتج قسمة مقرب بدقة.

يؤدي استخدام كثيرات الحدود ذات الدرجة الأعلى في التهيئة أو التكرار إلى تدهور الأداء لأن عمليات الضرب الإضافية المطلوبة يمكن استغلالها بشكل أفضل في إجراء المزيد من التكرارات.

تستخدم عملية القسمة لجولدشميت ^{[ 18 ]} (نسبة إلى روبرت إليوت جولدشميت) ^{[ 19 ]} عملية تكرارية لضرب كل من المقسوم والمقسوم عليه بشكل متكرر بعامل مشترك F _i ، يتم اختياره بحيث يتقارب المقسوم عليه إلى 1. وهذا يؤدي إلى تقارب المقسوم إلى ناتج القسمة المطلوب Q :

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

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

ينتج عن ضرب المقسوم والمقسوم عليه في العامل ما يلي:

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

بعد عدد كافٍ k من التكرارات${\displaystyle Q=N_{k}}$.

تُستخدم طريقة غولدشميت في معالجات AMD Athlon والطرازات الأحدث منها. ^{[ 20 ] [ 21 ]} تُعرف أيضًا باسم خوارزمية أندرسون إيرل غولدشميت باورز (AEGP) وتُطبّق في العديد من معالجات IBM . ^{[ 22 ] [ 23 ]} على الرغم من أنها تتقارب بنفس معدل تقارب تطبيق نيوتن-رافسون، إلا أن إحدى مزايا طريقة غولدشميت هي إمكانية إجراء عمليات الضرب في البسط والمقام بالتوازي. ^{[ 23 ]}