C で任意の長さの整数を実装するにはどうすればよいですか?

C での任意長の整数の実装

一般的な long int の容量を超える数値を処理するタスクに直面すると、多くのプログラマは既存のオープンソース実装に頼る。ただし、独自のカスタム BigInt クラスを作成するという課題は、数値演算の複雑さについての貴重な洞察を提供します。

アプローチ

BigInt 実装の基本的なアプローチには、数値の表現が含まれます。文字列として、より小さい桁 (1 桁など) に分割し、配列に格納します。これにより、比較演算子の簡単な実装が可能になります。課題は、加算や乗算などのより複雑な演算の実装にあります。

加算

加算を実行するには、CPU で使用される 2 項演算を模倣します。 BigInt の値配列の各要素が追加され、オーバーフローがあれば次の要素に引き継がれます。例として、= 演算子の実装を考えてみましょう。

BigInt& operator+=(const BigInt& operand) {
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size()); count++) {
    BT op0 = count < value_.size() ? value_.at(count) : 0,
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result - carry < std::max(op0, op1)) {
      BT carry_old = carry;
      carry = digits_result;
      digits_result =
          (op0 + op1 + carry) >> sizeof(BT) * 8; // NOTE [1]
    } else
      carry = 0;
  }

  return *this;
}

乗算

乗算は加算を繰り返すことで実行できます。あるいは、Karatsuba メソッドのような効率的なアルゴリズムを使用することもできます。

追加の考慮事項

BigInt クラスは、operator<< などの標準演算子を提供する必要があります。演算子<などのシフト演算子と比較演算子用。 std::ostream 演算子と友達になる<<便利な出力が可能になります。比較を実行する前に size() で桁数を確認するなど、効率を向上させるための最適化を行うことができます。

以上がC で任意の長さの整数を実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。