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

Z时代
2024-01-10
分类：综合

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);
}