خوارزمية بوث للضرب

خوارزمية بوث للضرب هي خوارزمية ضرب تُستخدم لضرب عددين ثنائيين مُوَقَّعين باستخدام نظام المتمم الثنائي . ابتكر هذه الخوارزمية أندرو دونالد بوث عام ١٩٥٠ أثناء بحثه في علم البلورات في كلية بيركبيك في بلومزبري ، لندن . ^{[ ١ ]} تُعدّ خوارزمية بوث ذات أهمية في دراسة هندسة الحاسوب .

تفحص خوارزمية بوث أزواج البتات المتجاورة للمضاعف Y ذي N بت ، والمُمثل بنظام المتمم الثنائي المُوَقَّع ، بما في ذلك بت ضمني أسفل البت الأقل أهمية ، y ₋₁ = 0. لكل بت y _i ، حيث i تتراوح من 0 إلى N − 1، يُؤخذ البتّان y _i و y _{i −1} في الاعتبار. عندما يتساوى هذان البتّان، يبقى مُجمِّع الضرب P دون تغيير. عندما يكون y _i = 0 و y _{i −1} = 1، يُضاف مضروبًا في 2 ⁱ إلى P ؛ وعندما يكون y _i = 1 و y _i−1 = 0، يُطرح مضروبًا في 2 ⁱ من P. القيمة النهائية لـ P هي حاصل الضرب المُوَقَّع.

لم تُحدد تمثيلات المضروب والناتج؛ عادةً ما يكون كلاهما في تمثيل المتمم الثنائي، مثل المضاعف، ولكن أي نظام عددي يدعم الجمع والطرح سيفي بالغرض. كما ذُكر هنا، لم يُحدد ترتيب الخطوات. عادةً ما تبدأ العملية من البت الأقل أهمية (LSB) إلى البت الأكثر أهمية (MSB) ، بدءًا من i = 0؛ ثم يُستبدل الضرب في 2i ^عادةً بإزاحة تدريجية للمُجمِّع P إلى اليمين بين الخطوات؛ يمكن إزاحة البتات المنخفضة، ويمكن بعد ذلك إجراء عمليات الجمع والطرح اللاحقة على أعلى N بت من P فقط . ^{[ 2 ]} توجد العديد من الاختلافات والتحسينات على هذه التفاصيل.

غالبًا ما تُوصف الخوارزمية بأنها تحوّل سلاسل الآحاد في المضاعف إلى +1 من الرتبة العليا و-1 من الرتبة الدنيا في نهايتي السلسلة. عندما تمر السلسلة عبر البت الأكثر أهمية (MSB)، لا يوجد +1 من الرتبة العليا، ويكون التأثير النهائي هو تفسيرها على أنها قيمة سالبة للقيمة المناسبة.

يمكن تنفيذ خوارزمية بوث عن طريق إضافة إحدى القيمتين المحددتين مسبقًا A و S إلى حاصل ضرب P بشكل متكرر (باستخدام الجمع الثنائي غير الموقّع العادي) ، ثم إجراء إزاحة حسابية إلى اليمين على P. لنفترض أن m و r هما المضروب والمضروب فيه على التوالي؛ ولنفترض أن x و y يمثلان عدد البتات في m و r .

1. حدد قيم A و S ، والقيمة الأولية لـ P. يجب أن يكون طول جميع هذه الأرقام مساوياً لـ ( x  + y + 1).    
   1. أ: املأ البتات الأكثر أهمية (الأقصى يسارًا) بقيمة m . املأ البتات المتبقية ( y  +  1) بأصفار.
   2. S: املأ البتات الأكثر أهمية بقيمة ( −m ) باستخدام ترميز المتمم الثنائي. املأ البتات المتبقية ( y  +  1) بأصفار.
   3. P: املأ خانات x الأكثر أهمية بالأصفار. إلى يمينها، أضف قيمة r . املأ الخانة الأقل أهمية (الأيمن) بالصفر.
2. حدد البتتين الأقل أهمية (الأقصى يمينًا) من P.
   1. إذا كانت القيم 01، فأوجد قيمة P  + A. تجاهل أي تجاوز. 
   2. إذا كانت القيمتان تساويان 10، فأوجد قيمة P  + S. تجاهل أي تجاوز. 
   3. إذا كانت القيمة 00، فلا تفعل شيئًا. استخدم P مباشرةً في الخطوة التالية.
   4. إذا كان عمرهم 11 عامًا، فلا تفعل شيئًا. استخدم P مباشرةً في الخطوة التالية.
3. قم بإزاحة القيمة التي تم الحصول عليها في الخطوة الثانية حسابيًا بمقدار خانة واحدة إلى اليمين. ولتكن قيمة P الآن مساوية لهذه القيمة الجديدة.
4. كرر الخطوتين 2 و 3 حتى يتم إنجازهما y مرة.
5. قم بحذف البت الأقل أهمية (الأقصى يمينًا) من P. هذا هو ناتج ضرب m و r .

أوجد 3 × ( − 4 )، حيث m = 3 و r = − 4، و x = 4 و y = 4:

• m = 0011، -m = 1101، r = 1100
• أ = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• قم بتنفيذ الحلقة أربع مرات:
  1. P = 0000 110 0 0. آخر بتين هما 00.
     • P = 0000 0110 0. إزاحة حسابية إلى اليمين.
  2. P = 0000 011 0 0. آخر بتين هما 00.
     • P = 0000 0011 0. إزاحة حسابية إلى اليمين.
  3. P = 0000 001 1 0. آخر بتين هما 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. الإزاحة الحسابية إلى اليمين.
  4. P = 1110 100 1 1. آخر خانتين هما 11.
     • P = 1111 0100 1. الإزاحة الحسابية إلى اليمين.
• الناتج هو 1111 0100، وهو يساوي -12 .

الأسلوب المذكور أعلاه غير كافٍ عندما يكون المضروب هو أكبر عدد سالب يمكن تمثيله (على سبيل المثال، إذا كان المضروب يتكون من 4 بتات، فإن قيمته ستكون -8 ). وذلك لأنه يحدث تجاوز عند حساب -m، وهو نفي المضروب، اللازم لتعيين S. أحد الحلول الممكنة لهذه المشكلة هو زيادة A وS وP بت واحد لكل منها، مع الحفاظ على تمثيلها لنفس العدد. أي، بينما كان -8 يُمثَّل سابقًا بأربعة بتات باستخدام 1000، فإنه يُمثَّل الآن بخمسة بتات باستخدام 11000. ويتبع هذا التنفيذ الموصوف أعلاه، مع تعديلات في تحديد بتات A وS. على سبيل المثال، سيتم الآن توسيع قيمة m ، التي تم تعيينها في الأصل لأول x بت من A، إلى x + 1 بت وتعيينها لأول x + 1 بت من A. فيما يلي، يتم توضيح التقنية المحسنة من خلال ضرب − 8 في 2 باستخدام 4 بت للمضروب والمضروب فيه:

• أ = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• قم بتنفيذ الحلقة أربع مرات:
  1. P = 0 0000 001 0 0 . آخر بتين هما 00.
     • P = 0 0000 0001 0. إزاحة لليمين.
  2. P = 0 0000 000 1 0. آخر خانتين هما 10.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. إزاحة إلى اليمين.
  3. P = 0 0100 000 0 1. آخر بتين هما 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. إزاحة إلى اليمين.
  4. P = 1 1110 000 0 0. آخر خانتين هما 00.
     • P = 1 1111 0000 0. إزاحة إلى اليمين.
• الناتج هو 11110000 (بعد تجاهل البت الأول والأخير) وهو -16 .

لنفترض مضاعفًا موجبًا يتكون من مجموعة من الآحاد محاطة بأصفار. على سبيل المثال، 00111110. يُعطى الناتج بالصيغة التالية: $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&1&1&0\\\hline \end{array}}=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$$ حيث M هو المضروب. يمكن تقليل عدد العمليات إلى عمليتين بإعادة كتابة المعادلة نفسها على النحو التالي: $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&0&0&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{1})=M\times 62.}$$

في الواقع، يمكن إثبات أن أي تسلسل من الرقم 1 في عدد ثنائي يمكن تقسيمه إلى الفرق بين عددين ثنائيين:

$${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$$

لذا، يمكن استبدال عملية الضرب بسلسلة الآحاد في العدد الأصلي بعمليات أبسط، كإضافة المضاعف، ثم إزاحة الناتج الجزئي الناتج بمواضع مناسبة، ثم طرح المضاعف. ويعتمد هذا على حقيقة أنه لا يلزم سوى الإزاحة عند التعامل مع الأصفار في المضاعف الثنائي، وهو مشابه لاستخدام الخاصية الرياضية التي تنص على أن 99  =  100 - 1 عند الضرب في 99.  

يمكن توسيع هذا المخطط ليشمل أي عدد من مجموعات الآحاد في المضاعف (بما في ذلك حالة وجود آحاد واحد فقط في المجموعة). وبالتالي،

$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&0&1&0\\\hline \end{array}}\ =M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$$$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&-1&1&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.}$$

تتبع خوارزمية بوث هذا المخطط القديم، حيث تُجري عملية جمع عند مصادفة الرقم الأول من مجموعة الآحاد (0 1)، وعملية طرح عند مصادفة نهاية المجموعة (1 0). وينطبق هذا على المضاعف السالب أيضًا. عندما تُجمّع الآحاد في المضاعف في مجموعات طويلة، تُجري خوارزمية بوث عمليات جمع وطرح أقل من خوارزمية الضرب العادية.

يستخدم معالج بنتيوم من إنتل نسخةً معدلةً من خوارزمية بوث ذات الأساس 8 في مضاعف الأجهزة ذي 64 بت. ونظرًا لطريقة تنفيذه لعملية الضرب في الأساس 8، فإنه يحتاج إلى دائرة مساعدة معقدة لإجراء عملية الضرب في 3 بطريقة تقلل زمن الاستجابة إلى أدنى حد، وذلك من خلال الجمع بين استخدام تقنيات التنبؤ بالحمل ، واختيار الحمل ، وجمع كوج-ستون . ^{[ 3 ]}

• المضاعف الثنائي
• شكل غير متجاور
• التمثيل الثنائي الزائد
• شجرة والاس
• مضاعف دادا

• كولين، أندرو (ربيع 1993). "حواسيب أندرو بوث في كلية بيركبيك" . القيامة (5). لندن: جمعية صيانة الحواسيب .
• باترسون، ديفيد أندرو ؛ هينيسي، جون ليروي (1998). تنظيم وتصميم الحاسوب: واجهة الأجهزة/البرمجيات (  الطبعة الثانية). سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: دار مورغان كوفمان للنشر . ISBN 1-55860-428-6.
• ستالينغز، ويليام (2000). تنظيم وبنية الحاسوب: التصميم من أجل الأداء (  الطبعة الخامسة). نيوجيرسي: برنتيس هول، إنك. ISBN 0-13-081294-3.
• سافارد، جون جي جي (2018) [2006]. "تقنيات حسابية متقدمة" . كوادريبلوك . مؤرشف من الأصل في 3 يوليو 2018. تم الاسترجاع في 16 يوليو 2018 .

• ترميز راديكس-4 للكابينة
• ترميز بوث ذو الأساس 8 في نظرية رسمية لـ RTL والحساب الحاسوبي
• محاكي جافا سكريبت لخوارزمية بوث
• التنفيذ بلغة بايثون
• التنفيذ بلغة C++
• التنفيذ بلغة جافا
• مزايا استخدام خوارزمية بوث