c - Tom-Cook 乗算アルゴリズムの実装

Question

Tom-Cook 3 ウェイ乗算アルゴリズムを実装するタスクがあります。私はウィキペディアの説明に従っていますhttp://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication、ウィキペディアページの「分割」手順に従って、2つの大きな数字を文字列に保存し、文字列を小さな数字に分割することができました。次のステップは「評価」です。新しい数値 p0 = m0 + m2 (Bordrato による「高速評価」 - 同じページにあります) を計算する必要があります。ここで、m0 と m2 は、大きな数値を分割して作成した数字です。 (前のステップで)。問題は、m0 と m2 を単純に合計できないことです。これらの 2 つの数値は依然として非常に大きく、標準的な方法で合計することは不可能なためです。これは、大きな数を追加するための独自のアルゴリズムを実装する必要があることを意味しますか (減算と除算も必要なので)、それとも何か不足していますか? 誰かが私に可能な実装または疑似コードをリンクしていただければ幸いです。

Answer 1

加算、減算、モジュロなどの独自のメソッドを実装する必要があります。以前、私は BigInteger ライブラリを実装しようとしていましたが、役立つリソースがいくつか見つかりました。

• BigNum Math book (前の回答で指摘されているように)
• Java OpenJdk BigInteger 実装、ドキュメント付き
• アルゴリズムとデータ構造 基本的なツールボックス (私はこの本でからつべを学びました)。

ちなみに、数値には底 2 を使用することをお勧めします (こちら を参照)。コンピューターの性質を利用して、操作をより簡単かつ迅速に行うことができるからです。