বুথের অ্যালগরিদম হল একটি গুণন অ্যালগরিদম যা ২'র সম্পূরক 표記법-এ দুটি সাইনড বাইনারি সংখ্যা গুণ করে। বুথ ডেস্ক ক্যালকুলেটর ব্যবহার করতেন যা যোগের চেয়ে শিফটিং-এ দ্রুত ছিল এবং গতিবৃদ্ধির জন্য এই অ্যালগরিদম তৈরি করেছিলেন।
অ্যালগরিদম
শুরু
গুণনীয়ক BR-এ এবং গুণক QR-এ রাখুন
তারপর অ্যালগরিদম নিম্নলিখিত শর্ত অনুযায়ী কাজ করে:
১. যদি Qn এবং Qn+1 একই হয় (০০ বা ১১) তবে ১ বিট এরითমেটিক শিফট সম্পাদন করুন।
২. যদি Qn Qn+1 = ১০ হয় তবে A = A + BR করুন এবং ১ বিট এরিতমেটিক শিফট করুন।
৩. যদি Qn Qn+1 = ০১ হয় তবে A = A - BR করুন এবং ১ বিট এরিতমেটিক শিফট করুন।
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void add(int a[], int x[], int q);
void complement(int a[], int n) {
int i;
int x[8] = { 0 };
x[0] = 1;
for (i = 0; i < n; i++) {
a[i] = (a[i] + 1) % 2;
}
add(a, x, n);
}
void add(int ac[], int x[], int q) {
int i, c = 0;
for (i = 0; i < q; i++) {
ac[i] = ac[i] + x[i] + c;
if (ac[i] > 1) {
ac[i] = ac[i] % 2;
c = 1;
} else
c = 0;
}
}
void ashr(int ac[], int qr[], int &qn, int q) {
int temp, i;
temp = ac[0];
qn = qr[0];
cout << "\t\tashr\t\t";
for (i = 0; i < q - 1; i++) {
ac[i] = ac[i + 1];
qr[i] = qr[i + 1];
}
qr[q - 1] = temp;
}
void display(int ac[], int qr[], int qrn) {
int i;
for (i = qrn - 1; i >= 0; i--)
cout << ac[i];
cout << " ";
for (i = qrn - 1; i >= 0; i--)
cout << qr[i];
}
int main(int argc, char **argv) {
int mt[10], br[10], qr[10], sc, ac[10] = { 0 };
int brn, qrn, i, qn, temp;
cout << "\n--গুণনীয়ক এবং গুণক ২'র সম্পূরক রূপে দিন যদি ঋণাত্মক হয়--";
cout << "\n গুণনীয়কের বিট সংখ্যা = ";
cin >> brn;
cout << "\nগুণনীয়ক = ";
for (i = brn - 1; i >= 0; i--)
cin >> br[i]; // গুণনীয়ক
for (i = brn - 1; i >= 0; i--)
mt[i] = br[i];
complement(mt, brn);
cout << "\nগুণকের বিট সংখ্যা = ";
cin >> qrn;
sc = qrn;
cout << "গুণক = ";
for (i = qrn - 1; i >= 0; i--)
cin >> qr[i];
qn = 0;
temp = 0;
cout << "qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n";
cout << "\t\t\tinitial\t\t";
display(ac, qr, qrn);
cout << "\t\t" << sc << "\n";
while (sc != 0) {
cout << qr[0] << "\t" << qn;
if ((qn + qr[0]) == 1) {
if (temp == 0) {
add(ac, mt, qrn);
cout << "\t\tsubtracting BR\t";
for (i = qrn - 1; i >= 0; i--)
cout << ac[i];
temp = 1;
} else if (temp == 1) {
add(ac, br, qrn);
cout << "\t\tadding BR\t";
for (i = qrn - 1; i >= 0; i--)
cout << ac[i];
temp = 0;
}
cout << "\n\t";
ashr(ac, qr, qn, qrn);
} else if (qn - qr[0] == 0)
ashr(ac, qr, qn, qrn);
display(ac, qr, qrn);
cout << "\t";
sc--;
cout << "\t" << sc << "\n";
}
cout << "Result=";
display(ac, qr, qrn);
}
আউটপুট
--গুণনীয়ক এবং গুণক ২'র সম্পূরক রূপে দিন যদি ঋণাত্মক হয়-- গুণনীয়কের বিট সংখ্যা = 5 গুণনীয়ক = 0 1 1 1 1 গুণকের বিট সংখ্যা = 5 গুণক = 1 0 1 1 1 qn q[n+1] BR AC QR sc initial 00000 10111 5 1 0 subtracting BR 10001 ashr 11000 11011 4 1 1 ashr 11100 01101 3 1 1 ashr 11110 00110 2 0 1 adding BR 01101 ashr 00110 10011 1 1 0 subtracting BR 10111 ashr 11011 11001 0 Result = 11011 11001
