Booth's multiplication algorithm
بوتھ کا ضرب الگورتھم ایک ضرب الگورتھم ہے جو دو کے تکمیل اشارے میں دو دستخط شدہ بائنری نمبروں کو ضرب دیتا ہے۔ الگورتھم کو اینڈریو ڈونلڈ بوتھ نے 1950 میں لندن کے بلومسبری کے برک بیک کالج میں کرسٹلگرافی پر تحقیق کرتے ہوئے ایجاد کیا تھا۔ بوتھ کا الگورتھم کمپیوٹر فن تعمیر کے مطالعہ میں دلچسپی رکھتا ہے۔ الگورتھم بوتھ کا الگورتھم دستخط شدہ دو کی تکمیل کی نمائندگی میں 'N'-بٹ ضرب Y کے بٹس کے ملحقہ جوڑوں کا جائزہ لیتا ہے، جس میں کم سے کم اہم بٹ، y−1 = 0 سے نیچے ایک مضمر بٹ بھی شامل ہے۔ ہر بٹ yi کے لیے، 0 سے N−1 تک چلنے والے i کے لیے، بٹس yi اور yi−1 پر غور کیا جاتا ہے۔ جہاں یہ دو بٹس برابر ہیں، پروڈکٹ جمع کرنے والا P کو بغیر کسی تبدیلی کے چھوڑ دیا جاتا ہے۔ جہاں yi = 0 اور yi − 1 = 1 ہے، ضرب بار 2i کو P میں شامل کیا جاتا ہے ؛ اور جہاں yi = 1 اور yi − 1 = 0 ہے، ضرب بار 2i کو P سے گھٹا دیا جاتا ہے۔ P کی حتمی قیمت دستخط شدہ پروڈکٹ ہے۔ ضرب اور پروڈکٹ کی نمائندگی کی وضاحت نہیں کی گئی ہے۔ عام طور پر، یہ دونوں دو کی تکمیل کی نمائندگی میں بھی ہوتے ہیں، جیسے ضرب، لیکن کوئی بھی نمبر سسٹم جو اضافہ اور گھٹاؤ کی حمایت کرتا ہے وہ بھی کام کرے گا۔ جیسا کہ یہاں بیان کیا گیا ہے، اقدامات کی ترتیب کا تعین نہیں کیا گیا ہے۔ عام طور پر، یہ ایل ایس بی سے ایم ایس بی کی طرف بڑھتا ہے، جو i = 0 سے شروع ہوتا ہے۔ 2i سے ضرب کے بعد عام طور پر مراحل کے درمیان دائیں طرف P جمع کرنے والے کی اضافی منتقلی سے تبدیل کیا جاتا ہے۔ کم بٹس کو باہر منتقل کیا جا سکتا ہے، اور اس کے بعد کے اضافے اور گھٹاؤ کو صرف P کے سب سے زیادہ N بٹس پر کیا جا سکتا ہے۔ ان تفصیلات پر بہت سے تغیرات اور اصلاحات ہیں۔ الگورتھم کو اکثر ضرب میں 1s کے تاروں کو ہائی آرڈر + 1 اور سٹرنگ کے سروں پر لو آرڈر-1 میں تبدیل کرنے کے طور پر بیان کیا جاتا ہے۔ جب کوئی تار ایم ایس بی سے گزرتا ہے، تو کوئی ہائی آرڈر + 1 نہیں ہوتا ہے، اور خالص اثر مناسب قیمت کے منفی کے طور پر ہوتا ہے۔ ایک عام نفاذ بوتھ کے الگورتھم کو دو پہلے سے طے شدہ اقدار A اور S میں سے ایک کو پروڈکٹ P میں بار بار شامل کرکے (عام غیر دستخط شدہ بائنری اضافے کے ساتھ) نافذ کیا جا سکتا ہے، پھر P پر دائیں طرف ریاضی کی تبدیلی انجام دی جا سکتی ہے۔ فرض کریں کہ m اور r بالترتیب ضرب اور ضرب ہیں۔ اور فرض کریں کہ x اور y m اور r میں بٹس کی تعداد کی نمائندگی کرتے ہیں۔ A اور S کی اقدار اور P کی ابتدائی قیمت کا تعین کریں۔ ان تمام نمبروں کی لمبائی (x + y + 1) کے برابر ہونی چاہیے۔ ج: سب سے اہم (بائیں طرف) بٹس کو m کی قیمت سے پر کریں۔ باقی (y + 1) بٹس کو صفر سے پر کریں۔ S: سب سے اہم بٹس کو دو کے تکمیلی اشارے میں (−m) کی قدر سے بھریں۔ بقیہ (y + 1) بٹس کو صفر سے بھریں۔ پی: سب سے اہم ایکس بٹس کو صفر سے بھریں۔ اس کی دائیں طرف، r کی قدر شامل کریں۔ سب سے کم اہم (دائیں طرف) بٹ کو صفر سے پر کریں۔ پی کے دو سب سے کم اہم (دائیں طرف) بٹس کا تعین کریں۔ اگر وہ 1 ہیں، تو پی + اے کی قیمت معلوم کریں۔ کسی بھی اوور فلو کو نظر انداز کریں۔ اگر وہ 10 ہیں، تو P + S کی قیمت معلوم کریں۔ کسی بھی اوور فلو کو نظر انداز کریں۔ اگر وہ 00 ہیں تو کچھ نہ کریں۔ اگلے مرحلے میں براہ راست P کا استعمال کریں۔ اگر وہ 11 سال کے ہیں تو کچھ نہ کریں۔ اگلے مرحلے میں براہ راست P کا استعمال کریں۔ ریاضیاتی طور پر دوسرے مرحلے میں حاصل کردہ قدر کو ایک ہی جگہ سے دائیں طرف منتقل کریں۔ فرض کریں کہ P اب اس نئی قدر کے برابر ہے۔ اقدامات 2 اور 3 کو اس وقت تک دہرائیں جب تک کہ وہ بار بار نہ ہو جائیں۔ پی سے سب سے کم اہم (دائیں طرف) بٹ ڈراپ کریں۔ یہ ایم اور آر کا پروڈکٹ ہے۔ مثال 3 × (−4) تلاش کریں، جس میں ایم = 3 اور آر = −4، اور ایکس = 4 اور وائی = 4: ایم = 0011،-ایم = 1101، آر = 1100 اے = 0011 0000 0 ایس = 1101 0000 0 پی = 0000 1100 0 لوپ کو چار بار انجام دیں: پی = 0000 1100 0۔ آخری دو بٹس 00 ہیں۔ P = 0000 0110 0۔ ریاضیاتی دائیں شفٹ۔ P = 0000 0110 0۔ آخری دو بٹس 00 ہیں۔ P = 0000 0011 0۔ ریاضیاتی دائیں شفٹ۔ P = 0000 0011 0۔ آخری دو بٹس 10 ہیں۔ P = 1101 0011 0۔ P = P + S. P = 1110 1001 1. ریاضیاتی دائیں شفٹ۔ P = 1110 1001 1۔ آخری دو بٹس 11 ہیں۔ P = 1111 0100 1۔ ریاضیاتی دائیں شفٹ۔ پروڈکٹ 1111 0100 ہے، جو کہ −12 ہے۔ مذکورہ بالا تکنیک ناکافی ہوتی ہے جب ضرب سب سے زیادہ منفی نمبر ہوتا ہے جس کی نمائندگی کی جا سکتی ہے (جیسے۔ اگر ضرب میں 4 بٹس ہوں تو یہ قدر −8 ہے)۔ اس کی وجہ یہ ہے کہ-m کی گنتی کرتے وقت ایک اوور فلو ہوتا ہے، ضرب کی نفی، جو S سیٹ کرنے کے لیے ضروری ہے۔ اس مسئلے کی ایک ممکنہ اصلاح A، S، اور P کو ایک ایک بٹ تک بڑھانا ہے، جبکہ وہ اب بھی ایک ہی نمبر کی نمائندگی کرتے ہیں۔ یعنی، جب کہ-8 کو پہلے چار بٹس میں 1000 سے ظاہر کیا جاتا تھا، اب اسے 5 بٹس میں 1000 سے ظاہر کیا جاتا ہے۔ اس کے بعد اوپر بیان کردہ نفاذ کے بعد، A اور S کے بٹس کے تعین میں ترمیم کے ساتھ ؛ مثال کے طور پر، m کی قیمت، جو اصل میں A کے پہلے x بٹس کو تفویض کی گئی تھی، اب x + 1 بٹس تک بڑھا دی جائے گی اور A کے پہلے x + 1 بٹس کو تفویض کی جائے گی۔ ذیل میں، ضرب اور ضرب کے لیے 4 بٹس کا استعمال کرتے ہوئے −8 کو 2 سے ضرب دے کر بہتر تکنیک کا مظاہرہ کیا گیا ہے: A = 1 1000 0000 0 S = 0 1000 0000 0 P = 0 0000 0010 0 لوپ کو چار بار انجام دیں: P = 0 0000 0010 0۔ آخری دو بٹس 00 ہیں۔ P = 0 0000 0001 0۔ دائیں شفٹ۔ P = 0 0000 0001 0۔ آخری دو بٹس 10 ہیں۔ P = 0 1000 0001 0۔ P = P + S. P = 0 0 100 0000 1. دائیں شفٹ۔ P = 0 0 100 0000 1۔ آخری دو بٹس 1 ہیں۔ P = 1 1100 0000 1۔ پی = پی + اے۔ پی = 1 1110 0000 0۔ دائیں شفٹ۔ P = 1 1110 0000 0۔ آخری دو بٹس 00 ہیں۔ P = 1 1111 0000 0۔ دائیں شفٹ۔ پروڈکٹ 11110000 ہے (پہلی اور آخری بٹ کو ضائع کرنے کے بعد) جو کہ −16 ہے۔ یہ کیسے کام کرتا ہے ایک مثبت ضرب پر غور کریں جو 1s کے ایک بلاک پر مشتمل ہے جس کے گرد 0s ہے۔ مثال کے طور پر 00111110۔ پروڈکٹ اس طرح دیا جاتا ہے: جہاں M ضرب ہے۔ در حقیقت، یہ دکھایا جا سکتا ہے کہ بائنری نمبر میں 1s کی کسی بھی ترتیب کو دو بائنری نمبروں کے فرق میں توڑا جا سکتا ہے: اس لیے، ضرب کو اصل نمبر میں ایک کی تار سے آسان کارروائیوں کے ذریعے تبدیل کیا جا سکتا ہے، ضرب کو جوڑ کر، جزوی پروڈکٹ کو مناسب جگہوں سے تبدیل کر کے، اور پھر آخر میں ضرب کو گھٹا کر۔ یہ اس حقیقت کا استعمال کر رہا ہے کہ بائنری ملٹی پلیئر میں 0s سے نمٹنے کے دوران شفٹ کے علاوہ کچھ کرنا ضروری نہیں ہے، اور یہ ریاضیاتی خاصیت 99 = 100−1 کو 99 سے ضرب دیتے ہوئے استعمال کرنے سے ملتا جلتا ہے۔ اس اسکیم کو ضرب میں 1s کے بلاکس کی کسی بھی تعداد تک بڑھایا جا سکتا ہے (بشمول بلاک میں ایک واحد 1 کا معاملہ)۔ اس طرح، بوتھ کا الگورتھم ایک اضافی کارکردگی کا مظاہرہ کرتے ہوئے اس پرانی اسکیم کی پیروی کرتا ہے جب اس کا سامنا ایک بلاک کے پہلے ہندسے (0 1) سے ہوتا ہے اور جب اسے بلاک کے آخر (1 0) کا سامنا ہوتا ہے تو گھٹاؤ ہوتا ہے۔ یہ منفی ضرب کے لیے بھی کام کرتا ہے۔ جب ضرب والے کو لمبے بلاکس میں گروپ کیا جاتا ہے، تو بوتھ کا الگورتھم عام ضرب الگورتھم کے مقابلے میں کم اضافے اور گھٹاؤ انجام دیتا ہے۔ بائنری ملٹی پلیئر غیر ملحقہ شکل ریڈینڈینٹ بائنری نمائندگی والیس ٹری ڈیڈا ملٹی پلیئر حوالہ جات مزید پڑھنا بیرونی لنکس ریڈکس-4 بوتھ انکوڈنگ ریڈکس-8 بوتھ انکوڈنگ ان اے فارمل تھیوری آف آر ٹی ایل اور کمپیوٹر آرتھمیٹک بوتھ کے الگورتھم جاوا اسکرپٹ سمیلیٹر امپلیمینٹیشن ان ازگر 1950 تعارف 1950 لندن 1950 میں سائنس بائنری آرتھمیٹک کمپیوٹر آرتھمیٹک الگورتھم ملٹی پلیکیشن برک بیک، یونیورسٹی آف لندن