最初に行うことは、動作するテスト エンジンを用意することです。これは脳死した、理解しやすい、任意精度の算術エンジンです。
このエンジンの目的は数倍です。まず、文字列を任意精度の整数に簡単に変換できます。2 つ目は、後で改良されたエンジンをテストする手段です。たとえそれが本当に遅いとしても、それが正しいと確信するでしょう (また、2 つの独立した実装があるということは、どちらかの自信がなくても、一方のコーナー ケース エラーが別のケースでキャッチされる可能性があることを意味します)。
short
少なくとも 16 ビットでchar
あり、少なくとも 8 であると仮定します (コンパイラがサポートしている場合は、実際のスタイル タイプを使用してint_8
ください)。
short Add(unsigned char left, unsigned char right, unsigned char extra=0) { return unsigned short(left)+unsigned short(right)+unsigned short(extra); }
unsigned short Multiply(unsigned char left, unsigned char right) { return unsigned short(left)*unsigned short(right); }
std::pair<unsigned char,unsigned char> CarryCalc(unsigned short input) {
std::pair<unsigned char,unsigned char> retval;
retval.first = input & (1<<8-1);
retval.second = input>>8;
return retval;
}
struct BigNum {
std::vector<char> base256;
BigNum& operator+=( BigNum const& right ) {
if (right.base256.size() > base256.size())
base256.resize(right.base256.size());
auto lhs = base256.begin();
auto rhs = right.base256.begin();
char carry = 0;
for(; rhs != right.base256.end(); ++rhs, ++lhs) {
auto result = CarryCalc( Add( *lhs, *rhs, carry ) );
*lhs = result.first;
carry = result.second;
}
while( carry && lhs != base256.end() ) {
auto result = CarryCalc( Add( *lhs, 0, carry ) );
*lhs = result.first;
carry = result.second;
}
if (carry)
base256.push_back(carry);
return *this;
}
BigNum& scaleByChar( unsigned char right ) {
char carry = 0;
for(auto lhs = base256.begin(); lhs != base256.end(); ++lhs) {
unsigned short product = Multiply( *lhs, right );
product += carry;
auto result = CarryCalc( product );
*lhs = result.first;
carry = result.second;
}
if (carry)
base256.push_back(carry);
return *this;
}
BigNum& shiftRightBy8BitsTimes( unsigned int x ) {
if (x > base256.size()) {
base256.clear();
return *this;
}
base256.erase( base256.begin(), base256.begin()+x) )
return *this;
}
// very slow, O(x * n) -- should be O(n) at worst
BigNum& shiftLeftBy8BitsTimes( unsigned int x ) {
while( x != 0 ) {
base256.insert( base256.begin(), 0 );
--x;
}
return *this;
}
// very slow, like O(n^3) or worse (should be O(n^2) at worst, fix shiftLeft)
BigNum& operator*=( BigNum const& right ) {
unsigned int digit = 0;
BigNum retval;
while (digit < right.base256.size()) {
BigNum tmp = *this;
tmp.shiftLeftBy8BitsTimes( digit );
tmp.scaleByChar( right.base256[digit] );
retval += tmp;
++digit;
}
*this = retval;
return *this;
}
};
これは、恐ろしいパフォーマンスを持つ、迅速で汚れた任意精度の整数型 (まだコンパイルされていません) です。上記のようなものをテストし、それがしっかりしていることを確信してから、そこから構築してください。
コードの多くは、問題の実際の BigNum クラスをテンプレート引数として使用できるため、同じアルゴリズムを 2 つの異なる実装で実行し、テスト目的で結果を比較できます。
ああ、もう 1 つアドバイスがあります。CRTP を介して必要最小限の任意精度ライブラリを「改善」するテンプレート クラスを作成してください。目標は、 、 、 、 and Maybe と some と 関数を記述するだけ*=
で+=
よくunary -
、/=
残りshift_helper
のcompare_helper
メソッドはテンプレートによって自動的に記述されるようにすることです。ボイラープレートを 1 つの場所に置くことで、クラスの複数のバージョンを維持することが容易になりますBigNum
。複数のバージョンを持つことは、テスト目的で非常に重要です。