C ++程序，用于实现两个数相乘的Schonhage-Strassen算法

Schonhage-Strassen算法用于将两个数字相乘。SchonhageStrassen算法是用于大整数的渐近快速乘法算法。实际上，对于超过2²¹⁵至2²¹⁷（十进制10,000到40,000）的数字，Schonhage-Strassen算法开始胜过karatsuba和Toom-CooK等旧方法。

算法

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 << "输入数字：";    long a, b;    cin >> a >> b;    int n = noOfDigit(a);    int m = noOfDigit(b);    schonhageStrassenMultiplication(a, b, n, m); }

输出结果

输入数字：1234 5679 The Linear Convolution is: ( 5 16 34 61 63 55 36 ) The Product of the numbers is: 7007886