C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

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


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

  1. ヴィジュネル暗号を実装するためのC++プログラム

    Vigenere Cipherは、アルファベットのテキストを暗号化する一種の多表式置換方法です。 この方法での暗号化と復号化には、AからZまでのアルファベットが26行で書き込まれるVigenereCipherTableが使用されます。 暗号化 キー: ようこそ メッセージ: Thisistutorialspoint ここでは、指定されたキーの長さが元のメッセージの長さと等しくなるまで、そのキーを繰り返してキーを取得する必要があります。 暗号化の場合は、メッセージの最初の文字とキー(TとW)を取得します。V行とW列が一致するVigenere Cipher Tableのアルファベ

  2. 2つの数値を交換するC++プログラム

    2つの数値を交換するプログラムを作成する方法は2つあります。 1つは一時変数を使用することを含み、2番目の方法は3番目の変数を使用しません。これらは次のように詳細に説明されています- 一時変数を使用して2つの数値を交換するプログラム 一時変数を使用して2つの数値を交換するプログラムは次のとおりです。 例 #include <iostream > using namespace std; int main() {    int a = 10, b = 5, temp;    temp = a;    a = b; &nbs