2

私はC++で多倍長演算を実装するプロジェクトに取り組んでいます。私は最初のハードルに落ちました。私はc文字列を整数のバイナリ表現に変換しようとしています。整数のバイナリ表現には、おそらくintが保持できるよりも多くのビットが含まれます（これは理論上は任意のビット数である可能性があります）。私は基本的に、文字列に含まれる数値のバイナリ表現を保持するlongの配列を作成したいと考えています。インデックス0は、数値の最下位の「四肢」です。数は10進数だと思います。

私はすでにGMPのコードの使用を検討しましたが、それは私のニーズにとって不必要に複雑であり、プラットフォームに依存するコードが大量にあります。

どんな助けでも素晴らしいでしょう！詳細が必要な場合はお知らせください。

4

2 に答える 2

3

@SteveJessopが言ったように

class Number {
public:
    Number();
    void FromString( const char * );
    void operator *= ( int );
    void operator += ( int );
    void operator = ( int );
}

Number::FromString( const char * string )
{
    *this = 0;
    while( *string != '\0' ) {
        *this *= 10;
        *this += *string - '0';
        string++;
    }
}
于 2012-12-10T14:30:42.013 に答える
2

最初に行うことは、動作するテスト エンジンを用意することです。これは脳死した、理解しやすい、任意精度の算術エンジンです。

このエンジンの目的は数倍です。まず、文字列を任意精度の整数に簡単に変換できます。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。複数のバージョンを持つことは、テスト目的で非常に重要です。

于 2012-12-10T15:03:43.437 に答える