C++ 程序实现 Schonhage-Strassen 算法以将两个数字相乘
c++server side programmingprogramming
Schonhage-Strassen 算法用于将两个数字相乘。SchonhageStrassen 算法是一种用于大整数的渐近快速乘法算法。实际上，对于 2215 到 2217(10,000 到 40,000 个十进制)以上的数字，Schonhage-Strassen 算法开始胜过 karatsuba 和 Toom-CooK 等旧方法。
算法
开始 function noOfDigit( x) 声明变量 n 并赋值 n = 0; while (x > 0) x = x /10 增加 n 返回 n 结束 开始 schonhageStrassenMultiplication 算法: schonhageStrassenMultiplication(a, b, n, m) 定义一个数组 linearConvolution[n + m - 1] for i = 0 到 (n + m - 1)-1 linearConvolution[i] = 0; long p = a 对于 i = 0 到 m-1 a = p 对于 j = 0 到 n-1 linearConvolution[i + j] += (b mod 10) * (a mod 10); a /= 10 b /= 10 对于 i = (n + m - 2) 到 0 打印 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; 打印数字的乘积。 结束
示例代码
#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 << "线性卷积为:( ";
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 << "\n数字的乘积为: " << 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 线性卷积为:( 5 16 34 61 63 55 36 ) 数字的乘积为:7007886
