Big Integerに加えて、私は理論を知っています...実際にはまだ錆びています。

Question

シンプルなビッグ整数クラスを構築しようとしています。インターネット上のいくつかのページとそのすべてを読みましたが、 。私は理論を知っていますが、私はキャリーが必要だと知っていますが、私が見てきたすべての例は、文字列と基数10にもっと焦点を当てています。プラスの代入演算子については助けていただきたいと思います。その残りの部分は、自分で把握しようとします。

#include <iostream> 
#include <string> 
#include <vector> 

using std::cout; 
using std::endl; 

class big_integer { 
    using box = std::vector<int unsigned>; 
    box data {0}; 

    box split(std::string const & p_input) const { 
     box output; 
     for (size_t i {}; i < p_input.size(); i += 8) { 
      output.push_back(stoi(p_input.substr(i, 8))); 
     } 
     return output; 
    } 

public: 
    big_integer(std::string const & p_data) 
     : data {split(p_data)} 
    {} 

    big_integer(int unsigned const p_data) 
     : data {p_data} 
    {} 

    big_integer & operator +=(big_integer const & p_input) { 
     int carry {}; 

     for (size_t i {}; i < data.size(); ++i) { 

      //Need help here! 
      //All examples I see either use primitive arrays 
      //or are too esoteric for me to understand.    
      //data[i] += p_input.data[i] + carry; 

     } 

     return *this; 
    } 

    std::string to_string() const { 
     std::string output; 
     output.reserve(data.size() * 8); 
     for (auto const i : data) { 
      output.append(std::to_string(i)); 
     } 
     return output; 
    } 
}; 

std::ostream & operator <<(std::ostream & p_output, big_integer const & p_input) { 
    return p_output << p_input.to_string(); 
} 

int main() { 
    big_integer test1 {"126355316523"}; 
    big_integer test2 {255}; 

    test1 += test1; 

    cout << test1 << endl; 
    cout << test2 << endl; 
    return 0; 
} 

Answer 1

右。ですから、基本的な問題は、unsignedとcarryを与えるためにunsigned + unsigned + carryを行う方法です。最初の桁に0xFFFF + 0xFFFF == 0xFFFE + 1のキャリーを16ビットの整数とみなした場合（32ビットで同じに動作しますが）、次の桁で0xFFFF + 0xFFFF +桁上げ== 0xFFFF +キャリー。したがってキャリーは1つに過ぎません。アルゴリズムは次のとおり

unsigned lhs, rhs, carry_in; // Input 
    unsigned sum, carry_out;  // Output 

    sum = lhs + rhs; 
    carry_out = sum < lhs ; 
    sum += carry_in; 
    carry_out = carry_out || sum < lhs; 

基本的アイデアはunsignedで加算を行い、その後ラッピングを検出する（したがってキャリー）することです。非常に厄介なことは、これは、条件付き論理の大量であり、複数の命令である "桁上げ加算"を実装することです。これはこれまで使用していたすべての命令セットの命令です。 （注：それはむしろ||よりcarry_out使用|の最終的な計算をする価値があるかもしれない - それは、パフォーマンスのために悪いですこれは、分岐いつものように、プロファイルを、それが助けかどうかを確認するために保存されます。）

を使用すると、最終的にしようとしている場合乗算をサポートするには、 "数字"の2倍のタイプが必要です。この場合、加算にも使うことができます。上記の変数を使用して、「署名のない長い長い」と仮定すると、あなたの「ワイド」タイプです：

const auto temp = (unsigned long long)lhs + rhs + carry_in; 
    sum = temp; // Will truncate. 
    carry_out = temp > UINT_MAX; 

あなたの「ワイド」タイプを選択すると、注意が必要です。最初のパスとして、あなたの数字にはuint32_t、ワイドタイプにはuint64_tを使用するのが最善でしょう。

多精度算術の実装の詳細については、Chapter 14 from Handbook of Applied Cryptographyが便利です。