15.8.3 桁上がり・桁借り上げ処理

GMPにおける最もチャレンジングな課題は，リムからリムへの桁上がり・桁借り下げ処理です。mpn_addmul_1関数や mpn_add_n関数では，桁上がり処理はリム間の処理にお任せしています。

キャリーフラグを持っているプロセッサ上では，直線的なCISC スタイルの adcを使うのが一番効果的です。 AMD K6 のmpn_addmul_1は，例外的に分岐処理がうまく働く環境の一例です。

RISCプロセッサ上では，通常，オーバーフローした値に対しての加算と比較が使用可能です。この種のものは mpn/generic/aors_n.cで見ることができます。桁上がり・桁借り上げ処理は，環境によって異なりますが，4命令使う必要があるケースがあり，これは少なくとも1リムあたり4サイクル必要になるということです。.別の環境では１，２命令で済むこともあります。広いスーパースカラープロセッサのパフォーマンスは完全に，リムごとの桁借り上げ(carry-in)，桁下がり(carry-out) 処理に要する命令数で決まってきます。

ベクトルプロセッサ上では，1ビットの桁上がりは1リムを超えることはめったにない，という事実を踏まえて効率化します。 つまり，リムに1ビット加える際には，桁上がりによるハミダシはリムが0xFF…FFである時に限られ，この結果， 2^mp_bits_per_limbになります。mpn/cray/add_n.c はこの処理を行っている具体例で，この中では全てのリムを並列に加算し，キャリービットもまとめて並列に加えており，そこからさらにハミダシ桁上がりが発生することは滅多にないことが分かります。

x86プロセッサ上では，GCC (例えばversion 2.95.2)はRISCスタイルのイデオムで，良いキャリー処理のコードを生成することはありません。本来ならadc や sbbを使うのが望ましいところで，条件付きジャンプを生成してしまいます。 キャリービットを含むループは，どうもアセンブラコードで書かないといい結果が得られないようです。