数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 程序实现两数相乘的 Schonhage-Strassen 算法
Schonhage-Strassen 算法用于对两个数字进行乘法。SchonhageStrassen 算法是大整数渐近快速乘法算法。在实践中，Schonhage-Strassen 算法对于超过 2215 到 2217（10,000 到 40,000 位小数）的数字比 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 << "Enter the numbers:";
long a, b;
cin >> a >> b;
int n = noOfDigit(a);
int m = noOfDigit(b);
schonhageStrassenMultiplication(a, b, n, m);
}输出
Enter the numbers:1234 5679 The Linear Convolution is: ( 5 16 34 61 63 55 36 ) The Product of the numbers is: 7007886
更新日期：2019 年 7 月 30 日
1K+ 次浏览
广告