Thuật toán Booth là một thuật toán nhân hai số nhị phân có dấu trong ký hiệu 2’s khen. Booth đã sử dụng máy tính để bàn có tốc độ thay đổi nhanh hơn so với việc thêm và tạo thuật toán để tăng tốc độ của chúng.
Thuật toán
Begin Put multiplicand in BR and multiplier in QR and then the algorithm works as per the following conditions: 1. If Qn and Qn+1 are same i.e. 00 or 11 perform arithmetic shift by 1 bit. 2. If Qn Qn+1 = 10 do A= A + BR and perform arithmetic shift by 1 bit. 3. If Qn Qn+1 = 01 do A= A – BR and perform arithmetic shift by 1 bit. End
Mã mẫu
#include<iostream>
using namespace std;
void add(int a[], int x[], int q);
void complement(int a[], int n) {
int i;
int x[8] = { NULL };
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--Enter the multiplicand and multipier in signed 2's
complement form if negative--";
cout << "\n Number of multiplicand bit=";
cin >> brn;
cout << "\nmultiplicand=";
for (i = brn - 1; i >= 0; i--)
cin >> br[i]; //multiplicand
for (i = brn - 1; i >= 0; i--)
mt[i] = br[i];
complement(mt, brn);
cout << "\nNo. of multiplier bit=";
cin >> qrn;
sc = qrn;
cout << "Multiplier=";
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);
} Đầu ra
--Enter the multiplicand and multipier in signed 2's complement form if negative-- Number of multiplicand bit=5 multiplicand=0 1 1 1 1 No. of multiplier bit=5 Multiplier=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