Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: दो संख्याओं के गुणन के लिए शॉनहेज-स्ट्रासेन एल्गोरिदम इम्प्लीमेंट करना


दो संख्याओं को गुणा करने के लिए शॉनहेज-स्ट्रासेन एल्गोरिदम का उपयोग किया जाता है। शॉनहेज-स्ट्रासेन एल्गोरिदम बड़े पूर्णांकों के लिए एक एसिम्पटोटिकली फास्ट मल्टीप्लिकेशन एल्गोरिदम है। व्यवहार में शॉनहेज-स्ट्रासेन एल्गोरिदम करत्सुबा और टूम-कुक जैसे पुराने तरीकों से 2²¹⁵ से 2²¹⁷ (10,000 से 40,000 दशमलव) अंकों से अधिक संख्याओं के लिए बेहतर प्रदर्शन करना शुरू करता है।

एल्गोरिदम

Begin
    function noOfDigit(x)
        एक वेरिएबल n घोषित करें और n = 0 असाइन करें
        जब तक (x > 0)
            x = x / 10
            n बढ़ाएं
        n लौटाएं
End

Begin
    schonhageStrassenMultiplication के लिए एल्गोरिदम:
    schonhageStrassenMultiplication(a, b, n, m)
    linearConvolution[n + m - 1] ऐरे परिभाषित करें
    i = 0 से (n + m - 1)-1 तक
        linearConvolution[i] = 0;
        long p = a
        i = 0 से m-1 तक
            a = p
            j = 0 से n-1 तक
                linearConvolution[i + j] += (b % 10) * (a % 10);
                a /= 10
            b /= 10
        i = (n + m - 2) से 0 तक
            linearConvolution[i] प्रिंट करें
            long product = 0
            nextCarry = 0, base = 1
            i = 0 से (n + m - 1)-1 तक
                linearConvolution[i] += nextCarry;
                product = product + (base * (linearConvolution[i] % 10));
                nextCarry = linearConvolution[i] / 10;
                base *= 10;
            संख्याओं का गुणनफल प्रिंट करें।
End

उदाहरण कोड

#include <iostream>
using namespace std;

int noOfDigit(long x) {
    int n = 0;
    while (x > 0) {
        x /= 10;
        n++;
    }
    return n;
}

void schonhageStrassenMultiplication(long a, long b, int n, int m) {
    int linearConvolution[n + m - 1];
    for (int i = 0; i < (n + m - 1); i++)
        linearConvolution[i] = 0;
    
    long p = a;
    for (int i = 0; i < m; i++) {
        a = p;
        for (int j = 0; j < n; j++) {
            linearConvolution[i + j] += (b % 10) * (a % 10);
            a /= 10;
        }
        b /= 10;
    }
    
    cout << "The Linear Convolution is: ( ";
    for (int i = (n + m - 2); i >= 0; i--) {
        cout << linearConvolution[i] << " ";
    }
    cout << ")";
    
    long product = 0;
    int nextCarry = 0, base = 1;
    for (int i = 0; i < n + m - 1; i++) {
        linearConvolution[i] += nextCarry;
        product = product + (base * (linearConvolution[i] % 10));
        nextCarry = linearConvolution[i] / 10;
        base *= 10;
    }
    cout << "\nThe Product of the numbers is: " << product;
}

int main(int argc, char **argv) {
    cout << "Enter the numbers:";
    long a, b;
    cin >> a >> b;
    int n = noOfDigit(a);
    int m = noOfDigit(b);
    schonhageStrassenMultiplication(a, b, n, m);
}

आउटपुट

Enter the numbers: 1234 5679
The Linear Convolution is: ( 5 16 34 61 63 55 36 )
The Product of the numbers is: 7007886

  1. C++ में विग्नेरे सिफर (Vigenere Cipher) का कार्यान्वयन C++ में विग्नेरे सिफर (Vigenere Cipher) का कार्यान्वयन

    विग्नेरे सिफर अल्फाबेटिक टेक्स्ट को एन्क्रिप्ट करने की एक प्रकार की पॉलीअल्फाबेटिक सब्स्टीट्यूशन विधि है। विग्नेरे सिफर टेबल का उपयोग किया जाता है जिसमें A से Z तक के अल्फाबेट्स 26 पंक्तियों में लिखे होते हैं, इस विधि में एन्क्रिप्शन और डिक्रिप्शन के लिए। एन्क्रिप्शन Key: WELCOME Message: Thisis

  1. - C++ प्रोग्राम: रिकर्सिव यूक्लिड एल्गोरिदम से GCD ज्ञात करना

    महत्तम समापवर्तक (GCD) दो संख्याओं का GCD वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है। उदाहरण 63 = 7 × 3 × 3 21 = 7 × 3 GCD(63, 21) = 21 यूक्लिड का रिकर्सिव एल्गोरिदम एल्गोरिदम: gcd(a, b) = gcd(b, a % b) जब तक b शून्य न हो जाए। C++ प्रोग्राम उदाहरण #include <iostream> using namespac

  1. - C++ प्रोग्राम: दो संख्याओं को स्वैप करें

    परिचयदो संख्याओं को स्वैप करने का प्रोग्राम बनाने के दो तरीके हैं। एक में टेम्प वेरिएबल का उपयोग शामिल है और दूसरा तरीका तीसरे वेरिएबल का उपयोग नहीं करता है। इन्हें विस्तार से समझाया गया है - टेम्प वेरिएबल का उपयोग करके दो संख्याओं को स्वैप करेंउदाहरण#include <iostream> using namespace std; i