두 숫자의 곱셈을 위한 Schonhage-Strassen 알고리즘을 구현하는 C++ 프로그램

Schonhage-Strassen 알고리즘은 두 수를 곱하는 데 사용됩니다. SchonhageStrassen 알고리즘은 큰 정수에 대한 점근적으로 빠른 곱셈 알고리즘입니다. 실제로 Schonhage-Strassen 알고리즘은 2 ² 이상의 숫자에 대해 karatsuba 및 Toom-CooK와 같은 이전 방법을 능가하기 시작합니다. ¹⁵ 2 ²¹⁷ 까지 (십진수 10,000 ~ 40,000) 자릿수.

알고리즘

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