# C++ Program to Implement the Schonhage-Strassen Algorithm for Multiplication

«
»
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:

```\$ 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 