これを読めば、大きな整数の乗算と分割統治アルゴリズムを学ぶことができます。

[[352004]]

データ暗号化処理には多くの複雑な暗号化アルゴリズムがあり、これらの暗号化アルゴリズムでは非常に大きな整数演算が多数使用されることがよくあります。しかし、プログラミング言語にはデータのサイズに一定の制限があり、データが大きすぎるとデータオーバーフローが発生し、大きな整数データの操作が実行できなくなります。この記事では、大きな整数に対するデータ操作を実装する方法を学びます。この記事のコードは C++ を使用して実装します。

一般的な乗算演算

掛け算の計算には比較的簡単でわかりやすい方法があります。小学校で習った縦割りの計算法を使って掛け算の計算をすることができます。

垂直乗算

上図の列計算方法を参考にコードを実装します。

 #include <iostream>
 #include <文字列>
 #include <stdlib.h>
 #include <ベクター>
 #include <cstring>
 #include <アルゴリズム> 
 
 std::string を乗算します (std::string a、std::string b)
 {
    std::string 結果 = "" ;
 int行 = b.size ( );
列のサイズを整数にする
int tmp[行][列];
    memset(tmp,0,sizeof( int )*row*col); 
     
    逆順( a.begin (),a.end ( ));
    逆順( b.begin (),b.end ( )); 
     
 ( int i = 0; i < b.size ( ) ); i++)の場合
    {
 ( int j = 0; j < a.size ( ) ); j++)の場合
        {
            std::string bit_a = std::string(1, a.at (j));
            std::string bit_b = std::string(1, b.at (i)); 
             
            tmp[i][j] += std::stoi(bit_a) * std::stoi(bit_b); 
         
            tmp[i][j+1] = tmp[i][j] / 10;
            tmp[i][j] % = 10; 
 
        } 
 
    } 
 
 int N = a.size ( ) + b.size ( );
整数 合計[N];
    memset(合計, 0, sizeof( int )*N); 
     
 ( int n = 0; n < N; n++)の場合
    {
整数i = 0;
整数j = n; 
         
        i <= n && j >= 0 の場合
        {
            if(i < 行 && j < 列)
            {
合計[n] += tmp[i][j];
            } 
             
            私は++;
            j --;  
        } 
 
        (n+1 < N)の場合
        {
合計[n+1] =合計[n] / 10;
合計[n] %= 10;
        } 
 
    } 
 
    ブールゼロ開始フラグ = true ;
 ( int i = N-1; i >= 0; i --)の場合 
    {
        if(合計[i] = = 0 && ゼロ開始フラグ)
        {
続く;
        } 
         
        ゼロ開始フラグ = false ;
        結果を追加します(std::to_string(合計[i]));
    } 
     
結果を返します。
 } 
 
 
 intメイン()
 {
    std::string a = "3456" ;
    std::string b = "1234" ; 
 
    std::string 結果 = multiply(a, b);
    std::cout << a << " * " << b << " = " << 結果 <<std::endl; 
     
 0を返します。
 }

便宜上、最初に各乗数を反転し、最後に結果を反転します。計算処理では、乗算結果を格納する配列を同じ列にシフトして加算するのではなく、斜めに加算することで、スペースと計算ステップを削減できます。上記のコードを実行した結果は以下のようになります。

運用結果

文字列の長さには特別な制限がないため、上記のアルゴリズムは大きな整数演算に適用できます。

分割統治アルゴリズム

上記の垂直列方式は大きな整数の乗算の問題を非常にうまく解決できますが、より効率的な方法である分割統治アルゴリズムを選択することもできます。クイックソートやバイナリサーチなど、多くの分野に応用できる非常に重要なアルゴリズムです。アルゴリズムの名前から、大きな問題を小さな問題に分割し、最初に小さな問題を解決してから最後にこの問題を解決することがわかります。そのため、分割統治法と呼ばれています。ここで、この方法を使用して、大きな整数をプログラミング言語を使用して直接計算できる小さな整数に分割し、最終的に大きな整数の値を取得できます。

2 つの大きな整数があるとします。これを a (サイズは n ビット) と b (サイズは m ビット) と設定します。ここではバイナリ検索法を使用してデータを分割します。これら 2 つの整数は次のように分解できます。

しかし、

作る、

上記の式によれば、a*b を 4 つの小さな整数の乗算、つまり 4 つの式 z3、z2、z1、z0 に分解できます。分解された乗算値がまだ大きい場合は、コンピュータープログラミング言語が直接計算できるようになるまで、同じ方法で分解を続け、より小さな乗算値に分解することができます。

例えば、上記の 3456 と 1234 を掛け合わせる場合、下の図を参考にして、バイナリ検索で整数を段階的に分割します。計算のために、2 つの整数を 1 桁の整数に分割します。

3456 と 1234 の分割手順図

次に、分割統治アルゴリズムのコード実装を見てみましょう。ここでは再帰的な方法を使用します。

 #include <iostream>
 #include <文字列>
 #include <stdlib.h>
 #include <ベクター>
 #include <cstring>
 #include <アルゴリズム>
 #include <cmath> 
 
 std::stringを追加します(std::string a、std::string b)
 {
 int N = std:: max ( a.size (), b.size ( ));
整数 合計[N];
    memset(合計, 0, sizeof( int )*N); 
     
    逆順( a.begin (),a.end ( ));
    逆順( b.begin (),b.end ( )); 
 
 ( int i = 0; i< N; i++)の場合
    {
整数ビットa = 0;
ビットb = 0;
        i < a.size () の場合、 bit_a = std::stoi(std::string(1, a.at ( i)));
        i < b.size () の場合、bit_b = std::stoi(std::string(1, b.at ( i))); 
 
合計[i] += (bit_a + bit_b); 
 
        i < N-1 &&合計[i]>9 の場合
        {
合計[i+1] =合計[i] / 10;
合計[i] %=10;
        }
    } 
 
    std::string 結果 = "" ;
    ブールゼロ開始フラグ = true ;
 ( int i = N-1; i >= 0; i --)の場合 
    {
        if(合計[i] = = 0 && ゼロ開始フラグ)
        {
続く;
        } 
         
        ゼロ開始フラグ = false ;
        結果を追加します(std::to_string(合計[i]));
    } 
 
 
結果を返します。
 } 
 
 std::string の分割と征服 (std::string a、std::string b)
 {
    a.size () < 2 && b.size ( ) < 2の場合
    {
 std::to_string(std::stoi(a) * std::stoi(b))を返します。
    } 
     
 int n = a.size ( );
 b.size ( ) は、文字列の先頭に0 を付加します。 
     
整数半分N = n/2;
整数半分M = m/2; 
 
    std::string a0 = "0" ;
    std::string a1 = "0" ;
    if( a.size () > halfN && halfN > 0)
    {
        a1 = a.substr(0, 半分N);
        a0 = a.substr(halfN, a.size () - halfN);
    }
それ以外 
    {
        a1 = "0" ;
        0 = 0;
    } 
     
    std::string b0 = "0" ;
    std::string b1 = "0" ;
    b.size () > halfM && halfM > 0の場合
    {
        b1 = b.substr(0, halfM);
        b0 = b.substr(halfM, b.size () - halfM); 
 
    }
それ以外 
    {
        b1 = "0" ;
        0 = 0;
    } 
 
    std::string a1b1 = 分割して征服します(a1、b1);
    std::string a0b0 = 分割して征服する(a0, b0);
    std::string a1b0 = 分割して征服する(a1、b0);
    std::string a0b1 = 分割して征服します(a0、b1); 
     
    a1b1.append((n - 半分N) + (m - 半分M), '0' );
    a1b0.append(n - 半分のN、 '0' );
    a0b1.append(m - halfM, '0' ); 
 
    std::string 結果 = "" ;
    結果 = (a1b1, a1b0)を追加します。
    結果 =追加(結果、a0b1);
    結果 =追加(結果、a0b0); 
 
結果を返します。
 } 
 
 intメイン()
 {
    std::string a = "3456" ;
    std::string b = "1234" ; 
 
    std::cout << a << " * " << b << " = " <<divideAndConquer(a, b) << std::endl; 
 
 0を返します。
 }

プログラムの実行結果は次のとおりです。

分割統治アルゴリズムの演算結果

この記事はWeChat公式アカウント「Will's Canteen」から転載したものです。下のQRコードからフォローできます。この記事を転載する場合は、Will’s Dashitang パブリックアカウントにご連絡ください。