2つの数値の乗算のためのSchonhage-Strassenアルゴリズムを実装するC++プログラム

Schonhage-Strassenアルゴリズムは、2つの数値を乗算するために使用されます。 SchonhageStrassenアルゴリズムは、大きな整数に対して漸近的に高速な乗算アルゴリズムです。実際には、Schonhage-Strassenアルゴリズムは、2 ² を超える数で、カラツバやToom-CooKなどの古い方法よりも優れたパフォーマンスを発揮し始めます。 ¹⁵ 〜2 ²¹⁷ （10進数で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