โปรแกรม C++ สำหรับการคูณของอัลกอริทึมบูธสำหรับการคูณตัวเลขที่มีเครื่องหมาย 2 ตัว

อัลกอริทึมบูธ (Booth's Algorithm)

อัลกอริทึมบูธเป็นอัลกอริทึมการคูณที่คูณตัวเลขไบนารีที่มีเครื่องหมาย 2 ตัวในรูปแบบคอมพลีเมนต์ 2 (2's complement) บูธใช้เครื่องคิดเลขแบบโต๊ะที่มีความเร็วในการเลื่อนบิต (shifting) สูงกว่าการบวก จึงได้สร้างอัลกอริทึมนี้ขึ้นเพื่อเพิ่มความเร็วในการคำนวณ

ขั้นตอนของอัลกอริทึม

เริ่มต้น
  วางตัวถูกคูณ (Multiplicand) ใน BR และตัวคูณ (Multiplier) ใน QR
  จากนั้นอัลกอริทึมจะทำงานตามเงื่อนไขต่อไปนี้:
  1. หาก Qn และ Qn+1 เหมือนกัน คือ 00 หรือ 11 ให้ทำการเลื่อนคณิตศาสตร์ (arithmetic shift) 1 บิต
  2. หาก Qn Qn+1 = 10 ให้ทำ A = A + BR และเลื่อนคณิตศาสตร์ 1 บิต
  3. หาก Qn Qn+1 = 01 ให้ทำ A = A - BR และเลื่อนคณิตศาสตร์ 1 บิต
สิ้นสุด

โค้ดตัวอย่าง

#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--Enter the multiplicand and multiplier 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);
    return 0;
}

ผลลัพธ์ตัวอย่าง

--Enter the multiplicand and multiplier 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