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

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

एल्गोरिदम

Begin
   function noOfDigit( x)
   Declare a variable n and assign n = 0;
   while (x > 0)
      x = x /10
      Increment n
   return n
End

Begin
   Algorithm for schonhageStrassenMultiplication:
   schonhageStrassenMultiplication(a, b, n, m)
   define an array linearConvolution[n + m - 1]
   for i = 0 to (n + m - 1)-1
      linearConvolution[i] = 0;
      long p = a
   for i = 0 to m-1
      a = p
   for j = 0 to n-1
      linearConvolution[i + j] += (b mod 10) * (a mod 10);
      a /= 10
      b /= 10
   for i = (n + m - 2) to 0
      Print linearConvolution[i]
      long product = 0
      nextCarry = 0, base = 1
   for i = 0 to (n + m - 1)-1
      linearConvolution[i] += nextCarry;
      product = product + (base * (linearConvolution[i] % 10));
      nextCarry = linearConvolution[i] / 10;
      base *= 10;
      Print the product of numbers.
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