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.

`#include <iostream>`

using namespace std;

int noOfDigit(long a)

`{`

int n = 0;

while (a > 0)

`{`

a /= 10;

n++;

`}`

return n;

`}`

void schonhageStrassenMultiplication(long x, long y, int n, int m)

`{`

int linearConvolution[n + m - 1];

for (int i = 0; i < (n + m - 1); i++)

linearConvolution[i] = 0;

long p = x;

for (int i = 0; i < m; i++)

`{`

x = p;

for (int j = 0; j < n; j++)

`{`

linearConvolution[i + j] += (y % 10) * (x % 10);

x /= 10;

`}`

y /= 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);

`}`

Output:

$ 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.**

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

« Prev Page - C++ Program to Generate Prime Numbers Between a Given Range Using the Sieve of Sundaram