c - 大整数演算

Question

Cで非常に大きな整数に対して算術演算を実行するために使用されるさまざまな手法を知りたいです。私が知っているのは、文字列を使用して数値を保持し、加算、減算などの演算を定義することです。ライブラリの使用には興味がありません。この質問は純粋に知識に関するものです。使用された他のそのような方法/技術を提案してください。

Answer 1

整数をバイト配列として表現するのと同じくらい低レベルになり、CPU がワードレベルで行うのと同じように、すべての操作 (加算、減算、乗算、除算、比較など) を実行できます。

最も単純なアルゴリズムは足し算と引き算で、必要に応じて数字を順番に足したり引いたりします。

負の数は 2 の補数で表すことができます。

比較のために、違いが見つかるまで上位桁を比較するだけです。

乗算の場合、実装できる最も単純な (そして最も遅い) アルゴリズムは加算の繰り返しです。

除算については、乗算よりも少し複雑です。http: //en.wikipedia.org/wiki/Division_algorithmを参照してください。

これの一般的なアプリケーションは公開鍵暗号であり、そのアルゴリズムは通常、数百桁の整数を使用した算術演算を使用します。

これについては、OpenSSL BIGNUM のドキュメントを確認してください: https://www.openssl.org/docs/crypto/bn.html

Answer 2

番号 A 用、番号 B 用、結果用の 3 つのリンクされたリストを使用できます。

次に、各数字をユーザーからの文字入力として読み取り、それを整数にして、その時点で読み取った数値に対応するリスト内の新しいノードに保存します。

そして最後に、足し算、引き算などの操作を関数として書くだけです。それぞれで、学校で学んだそれぞれのアルゴリズムに従い、LSB ノードから開始して MSB ノードまで進み、常に次の基本パワーを念頭に置きます。各番号 (1 ノード * 10^0、2 ノード * 10^1、3 ノード * 10^2、...、n ノード * 10^n )。