Cách nhanh nhất nhân hai số (Fastest Way to multiply two Numbers)

Giới thiệu

Hai số được cho dưới dạng chuỗi nhị phân, nhiệm vụ của ta là tìm kết quả nhân của hai số đó theo cách nhanh và hiệu quả.

Sử dụng chiến lược Chia để trị (Divide and Conquer), ta có thể giải quyết bài toán theo cách rất hiệu quả. Ta sẽ chia các số thành hai nửa.

Giả sử Xleft và Xright là hai phần của số thứ nhất X, và Yleft, Yright là hai phần của số thứ hai Y. Vậy tích là:

Để đơn giản hóa, ta có thể thực hiện phép toán này:

Đầu vào và Đầu ra

Đầu vào: Hai số nhị phân: 1101 và 0111
Đầu ra: Kết quả là: 91

Thuật toán

addBitString(num1, num2)

Đầu vào: Hai số để cộng.

Đầu ra: Kết quả sau phép cộng.

Begin
    điều chỉnh độ dài num1 và num2
    length := độ dài của num1
    carry := 0
    for i := length -1 down to 0, do
        num1Bit := num1[i]
        num2Bit := num2[i]
        sum := num1Bit XOR num2Bit XOR carry
        finalSum := sum + finalSum
        carry := (num1Bit AND num2Bit) OR (num2Bit AND carry) OR (num1Bit AND carry)
    done
    if carry ≠ 0, then
        finalSum := 1 + finalSum
    return finalSum
End

multiply(num1, num2)

Đầu vào: Hai số để nhân.

Đầu ra: Kết quả sau phép nhân.

Begin
    điều chỉnh độ dài num1 và num2
    length := độ dài của num1
    if n = 0, then
        return 0
    if n = 1, then
        return (num1[0] * num2[0])
    firstHalf := n/2
    secondHalf := (n - firstHalf)
    n1Left := substring (0 to firstHalf) từ num1
    n1Right := substring (firstHalf to secondHalf) từ num1
    n2Left := substring (0 to firstHalf) từ num2
    n2Right := substring (firstHalf to secondHalf) từ num2
    p1 := multiply(n1Left, n2Left)
    p2 := multiply(n1Right, n2Right)
    add1 := addBitString(n1Left, n1Right)
    add2 := addBitString(n2Left, n2Right)
    p3 := multiply(add1, add2)
    mask1 := dịch 1 sang trái 2*secondHalf bit
    mask2 := dịch 1 sang trái secondHalf bit
    return P1*mask2 + (p3 – p1 – p2)*mask2 + p2
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int lengthAdjust(string &num1, string &num2) {
    // điều chỉnh độ dài chuỗi nhị phân và gửi độ dài chuỗi
    int len1 = num1.size();
    int len2 = num2.size();
    if (len1 < len2) {
        for (int i = 0; i < len2 - len1; i++)
            num1 = '0' + num1;  // thêm 0 trước chuỗi thứ nhất
    } else if (len1 > len2) {
        for (int i = 0; i < len1 - len2; i++)
            num2 = '0' + num2;  // thêm 0 trước chuỗi thứ hai
    }
    return num1.size();
}

string addBitStrings(string num1, string num2) {
    string finalSum;
    int length = lengthAdjust(num1, num2);  // điều chỉnh và cập nhật độ dài số
    int carry = 0;  // khởi tạo carry
    for (int i = length-1; i >= 0; i--) {
        int num1Bit = num1[i] - '0';
        int num2Bit = num2[i] - '0';
        int sum = (num1Bit ^ num2Bit ^ carry) + '0';  // tổng = A XOR B XOR C
        finalSum = (char)sum + finalSum;
        // carry = (A AND B) OR (B AND C) OR (C AND A)
        carry = (num1Bit & num2Bit) | (num2Bit & carry) | (num1Bit & carry);
    }
    if (carry)  // khi có carry
        finalSum = '1' + finalSum;  // thêm carry làm MSB
    return finalSum;
}

long int multiply(string num1, string num2) {
    int n = lengthAdjust(num1, num2);  // tìm độ dài sau điều chỉnh
    if (n == 0)  // khi chuỗi độ dài 0, trả về 0
        return 0;
    if (n == 1)  // thực hiện nhân bit đơn
        return (num1[0] - '0') * (num2[0] - '0');
    int firstHalf = n/2;  // Phạm vi nửa đầu
    int secondHalf = (n - firstHalf);  // Phạm vi nửa sau
    string num1Left = num1.substr(0, firstHalf);  // nửa đầu của số 1
    string num1Right = num1.substr(firstHalf, secondHalf);  // nửa sau của số 1
    string num2Left = num2.substr(0, firstHalf);
    string num2Right = num2.substr(firstHalf, secondHalf);
    // tìm nhân trái phải, và nhân sau khi cộng trái và phải
    long int P1 = multiply(num1Left, num2Left);
    long int P2 = multiply(num1Right, num2Right);
    long int P3 = multiply(addBitStrings(num1Left, num1Right), addBitStrings(num2Left, num2Right));
    return P1*(1<<(2*secondHalf)) + (P3 - P1 - P2)*(1<<secondHalf) + P2;
}

int main() {
    string num1, num2;
    cout << "Enter First number in Binary: "; cin >> num1;
    cout << "Enter Second number in Binary: "; cin >> num2;
    cout << "The result is: " << multiply(num1, num2);
}

Kết quả

Enter First number in Binary: 1101
Enter Second number in Binary: 0111
The result is: 91