الگوریتم بوث

الگوریتم ضرب بوث (Booth's multiplication algorithm) با استفاده از یک الگوریتم ساده، دو عدد علامت دار را در یکدیگر ضرب می‌کند. مراحل اجرای این الگوریتم را در عکس زیر مشاهده می نمایید.

الگوریتم بوث رویه ای را برای ضرب اعداد دودویی در نمایش متمم ۲ علامتدار ارائه می نماید. برای راحت‌تر شدن ضرب اعداد دودویی به کار میرود. مبنای کار الگوریتم بر این اساس استوار است که رشته‌های 0 در مضروب فیه نیازی به جمع ندارند بلکه فقط جابجایی (شیفت) لازم دارند و رشته‌های 1 در مضروب فیه از بیت مرتبه 2^k تا بیت 2^m را می‌توان معادل 2^k+1 - 2^m تلقی کرد.

مثلاً عدد دودودیی 001110 (14+) دارای رشته‌های 1 از 2¹ تا 2³ است. (k=3 و m=1). این عدد را می‌توان به صورت 2^k+1 - 2^m = 2⁴ - 2¹ = 16 - 2 = 14 نوشت.

بنابراین ضرب Mx14 را که در آن M مضروب و 14 مضروب فیه است، می‌توان به صورت Mx2⁴ - Mx2¹ انجام داد. لذا حاصلضرب با چهار بار شیفت مضروب به چپ و تفریق M که یکبار به چپ شیفت داده شده‌است به‌دست می آید.

همانند همه روش‌های ضرب، الگوریتم بوث نیز به بررسی بیت‌های مضروب فیه و شیفت حاصلضرب جزئی نیاز دارد. قبل از شیفت، ممکن است مضروب طبق قواعد زیر با حاصلضرب جزئی جمع شود، از آن تفریق شود و یا حاصلضرب جزئی بلاتغییر باقی بماند.

به محض برخورد با اولین 1 کم ارزش در رشته 1‌ها در مضروب فیه، مضروب از حاصلضرب جزئی کم شود.
به محض برخورد با اولین 0 (به شرطی که قبل از آن 1 باشد) در رشته ای از 0‌ها در مضروب فیه، مضروب با حاصلضرب جزئی جمع شود.
وقتی که بیت جاری مضروب فیه همانند بیت قبلی باشد، حاصلضرب جزئی تغییر نمی‌کند.

الگوریتم فوق، برای مضورب فیه‌های مثبت و یا منفی بفرم متمم 2 قابل استفاده است. این بدان علت است که مضروب فیه منفی به رشته ای از 1‌ها خاتمه می یابد و آخرین عمل تفریق با وزن مناسب خواهد بود. مثلاً مضروب فیه 14- در نمایش متمم 2 عبارتست از 110010 و به صورت -2⁴+2²-2¹ = 14 با آن رفتار می‌شود.

یک نمونه اجرا از این برنامه برای اعداد 6 و 5 :

Operation A Q Q' X

1 Initialize 0000 0101 0 0110

2 A <- A-M 1010 0101 0 0110

3 ShiftR 1101 0010 1 0110

4 A <- A+M 0011 0010 1 0110

5 ShiftR 0001 1001 0 0110

6 A <- A-M 1011 1001 0 0110

7 ShiftR 1101 1100 1 0110

8 A <- A+M 0011 1100 1 0110

9 ShiftR 0001 1110 0 0110