C++ Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers

«
»
This is a C++ Program to implement Schonhage-Strassen algorithm to multiply two numbers.

Here is source code of the C++ Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int noOfDigit(long a)
  6. {
  7.     int n = 0;
  8.     while (a > 0)
  9.     {
  10.         a /= 10;
  11.         n++;
  12.     }
  13.     return n;
  14. }
  15. void schonhageStrassenMultiplication(long x, long y, int n, int m)
  16. {
  17.  
  18.     int linearConvolution[n + m - 1];
  19.     for (int i = 0; i < (n + m - 1); i++)
  20.         linearConvolution[i] = 0;
  21.  
  22.     long p = x;
  23.     for (int i = 0; i < m; i++)
  24.     {
  25.         x = p;
  26.         for (int j = 0; j < n; j++)
  27.         {
  28.             linearConvolution[i + j] += (y % 10) * (x % 10);
  29.             x /= 10;
  30.         }
  31.         y /= 10;
  32.     }
  33.     cout << "The Linear Convolution is: ( ";
  34.     for (int i = (n + m - 2); i >= 0; i--)
  35.     {
  36.         cout << linearConvolution[i] << " ";
  37.     }
  38.     cout << ")";
  39.  
  40.     long product = 0;
  41.     int nextCarry = 0, base = 1;
  42.     ;
  43.     for (int i = 0; i < n + m - 1; i++)
  44.     {
  45.         linearConvolution[i] += nextCarry;
  46.         product = product + (base * (linearConvolution[i] % 10));
  47.         nextCarry = linearConvolution[i] / 10;
  48.         base *= 10;
  49.     }
  50.     cout << "\nThe Product of the numbers is: " << product;
  51.  
  52. }
  53. int main(int argc, char **argv)
  54. {
  55.     cout << "Enter the numbers:";
  56.     long a, b;
  57.     cin >> a >> b;
  58.     int n = noOfDigit(a);
  59.     int m = noOfDigit(b);
  60.     schonhageStrassenMultiplication(a, b, n, m);
  61. }

Output:

advertisement
$ g++ Schonhage-StrassenAlgorithm.cpp
$ a.out
 
Enter the numbers:3452 1245
The Linear Convolution is: ( 3 10 25 43 44 33 10 )
 Product of the numbers is: 4297740

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.