C ++程序，用于实现两个数相乘的Schonhage-Strassen算法
Schonhage-Strassen算法用于将两个数字相乘。SchonhageStrassen算法是用于大整数的渐近快速乘法算法。实际上，对于超过2215至2217（十进制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