特定の言語に関係なく有効な任意精度の算術演算のための共通の実装方法はありますか？

Question

私は、（Bignum、IntegerまたはBigIntと呼ばれることもある）任意精度の算術演算を実装するさまざまな方法について考えています。

共通イディオムは、スペース要件が拡大または縮小場合は実際の値を格納するための配列を使用し、必要に応じて再配分することであるように思えます。

より正確には、配列要素のビットサイズは、多くの場合、二番目に大きいサイズ一般的にサポートされている（おそらく実装がオーバーフローして計算を簡単にするために？）、電子のようです。 g。言語/プラットフォームは、128ビットサイズの数値をサポートしています - オーバーフローを処理するために64ビットの数値の配列+ 128ビットの変数

は基本的に任意精度演算を実現するためのさまざまな方法がありますか「しようとした真の」道上の巨大な性能損失なしにそれを実装するのですか？

私の質問は、基本的なデータ構造であり、操作のアルゴリズムではありません。私はKaratsuba、Toom-Cookらを知っています。

Answer 1

Chinese Remainder Theorem〜represent large integersは、通常のbase-2^nシステムとは基本的に異なる方法で使用できます。

Iは、CRTベースの表現は、依然として従来の表現のように、利用可能な最も便利ネイティブ演算に基づいて、素子のアレイを使用すると信じています。しかし、これらの要素は、base-2^n桁ではなく、primesのシーケンスで除算したときに数値の剰余を保持します。

従来の表現の場合と同様に、使用される要素の数によって表現可能な番号の最大サイズが決まります。残念ながら、1つのCRTベースの数値が別のCRTベースの数値よりも大きいかどうかを計算することは容易ではないため、表現が最大サイズをオーバーフローしたかどうかを判断することは困難です。加算と乗算はCRT表現では非常に高速であることに注意してください。オーバーフローの問題に対処できるなら、利点があります。

はしかし、あなたの質問に答えるために：私はベース-2^n個のシステムが実際に最も人気のあるBIGNUMライブラリで使用されている「しようとした真の」表現、であると言うことは正確であると信じています。私は、大きな整数の場合