दो संख्याओं को गुणा करने के लिए शॉनहेज-स्ट्रासेन एल्गोरिदम का उपयोग किया जाता है। शॉनहेज-स्ट्रासेन एल्गोरिदम बड़े पूर्णांकों के लिए एक एसिम्पटोटिकली फास्ट मल्टीप्लिकेशन एल्गोरिदम है। व्यवहार में शॉनहेज-स्ट्रासेन एल्गोरिदम करत्सुबा और टूम-कुक जैसे पुराने तरीकों से 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