दो संख्याओं को गुणा करने का सबसे तेज़ तरीका

परिचय

दो संख्याएं बाइनरी स्ट्रिंग के रूप में दी गई हैं, हमारा कार्य उन संख्याओं के गुणन का परिणाम तेज़ और कुशल तरीके से ढूंढना है।

विभाजन और विजय (Divide and Conquer) रणनीति का उपयोग करके, हम इस समस्या को बहुत कुशल तरीके से हल कर सकते हैं। हम संख्याओं को दो हिस्सों में विभाजित करेंगे।

मान लें Xleft और Xright पहली संख्या X के दो भाग हैं, और Yleft, Yright दूसरी संख्या Y के दो भाग हैं। तो गुणनफल:

इसे सरल बनाने के लिए, हम यह ऑपरेशन कर सकते हैं:

इनपुट और आउटपुट

इनपुट: दो बाइनरी संख्याएं: 1101 और 0111
आउटपुट: परिणाम है: 91

एल्गोरिदम

addBitString(num1, num2)

इनपुट: जोड़ने के लिए दो संख्याएं।

आउटपुट: जोड़ के बाद परिणाम।

Begin
    num1 और num2 की लंबाई समायोजित करें
    length := num1 की लंबाई
    carry := 0
    i := length -1 से 0 तक नीचे, करें
        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
    यदि carry ≠ 0, तो
        finalSum := 1 + finalSum
    finalSum लौटाएं
End

multiply(num1, num2)

इनपुट: गुणा करने के लिए दो संख्याएं।

आउटपुट: गुणन के बाद परिणाम।

Begin
    num1 और num2 की लंबाई समायोजित करें
    length := num1 की लंबाई
    यदि n = 0, तो
        0 लौटाएं
    यदि n = 1, तो
        (num1[0] * num2[0]) लौटाएं
    firstHalf := n/2
    secondHalf := (n - firstHalf)
    n1Left := num1 से (0 से firstHalf) का उपस्ट्रिंग
    n1Right := num1 से (firstHalf से secondHalf) का उपस्ट्रिंग
    n2Left := num2 से (0 से firstHalf) का उपस्ट्रिंग
    n2Right := num2 से (firstHalf से secondHalf) का उपस्ट्रिंग
    p1 := multiply(n1Left, n2Left)
    p2 := multiply(n1Right, n2Right)
    add1 := addBitString(n1Left, n1Right)
    add2 := addBitString(n2Left, n2Right)
    p3 := multiply(add1, add2)
    mask1 := 1 को बाएं शिफ्ट करें 2*secondHalf बिट्स के लिए
    mask2 := 1 को बाएं शिफ्ट करें secondHalf बिट्स के लिए
    P1*mask2 + (p3 – p1 – p2)*mask2 + p2 लौटाएं
End

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int lengthAdjust(string &num1, string &num2) {
    // बाइनरी स्ट्रिंग की लंबाई समायोजित करें और स्ट्रिंग की लंबाई भेजें
    int len1 = num1.size();
    int len2 = num2.size();
    if (len1 < len2) {
        for (int i = 0; i < len2 - len1; i++)
            num1 = '0' + num1; // पहली स्ट्रिंग से पहले 0 जोड़ें
    } else if (len1 > len2) {
        for (int i = 0; i < len1 - len2; i++)
            num2 = '0' + num2; // दूसरी स्ट्रिंग से पहले 0 जोड़ें
    }
    return num1.size();
}

string addBitStrings(string num1, string num2) {
    string finalSum;
    int length = lengthAdjust(num1, num2); // लंबाई समायोजित करें और लंबाई संग्रहीत करें
    int carry = 0; // कैरी आरंभ करें
    for (int i = length - 1; i >= 0; i--) {
        int num1Bit = num1[i] - '0';
        int num2Bit = num2[i] - '0';
        int sum = (num1Bit ^ num2Bit ^ carry) + '0'; // हम जानते हैं sum = A XOR B XOR C
        finalSum = (char)sum + finalSum;
        // कैरी = (A AND B) OR (B AND C) OR (C AND A)
        carry = (num1Bit & num2Bit) | (num2Bit & carry) | (num1Bit & carry);
    }
    if (carry) // जब कैरी मौजूद हो
        finalSum = '1' + finalSum; // कैरी को MSB के रूप में जोड़ें
    return finalSum;
}

long int multiply(string num1, string num2) {
    int n = lengthAdjust(num1, num2); // उन्हें समायोजित करने के बाद लंबाई खोजें
    if (n == 0) // जब 0 लंबाई की स्ट्रिंग हो, तो 0 लौटाएं
        return 0;
    if (n == 1) // एकल बिट गुणन करें
        return (num1[0] - '0') * (num2[0] - '0');
    int firstHalf = n/2; // पहली आधी रेंज
    int secondHalf = (n - firstHalf); // दूसरी आधी रेंज
    string num1Left = num1.substr(0, firstHalf); // संख्या 1 का पहला आधा
    string num1Right = num1.substr(firstHalf, secondHalf); // संख्या 1 का दूसरा आधा
    string num2Left = num2.substr(0, firstHalf);
    string num2Right = num2.substr(firstHalf, secondHalf);
    // बाएं दाएं गुणन खोजें, और बाएं और दाएं भाग को जोड़ने के बाद गुणा करें
    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);
}

आउटपुट

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