概要

• 現代CPU での大きな整数の加算・減算を高速化する技術を解説
• キャリー伝播 が並列化の障害となる理由と、CPU命令の違いによる性能差を説明
• 基数変換（radix 2⁵¹表現） を利用したキャリー伝播の遅延方法を紹介
• 実際のアセンブリコード例と、正規化処理の仕組みを具体的に解説
• 減算への応用や、パフォーマンス向上の理由も説明

現代CPUにおける高速な加算・減算

• 紙の筆算 では右端（1の位）から順に加算し、キャリーを左へ伝播する手順
• 大きな整数 （例: 256ビット以上）の加算も、基本的に同様のアルゴリズムを採用
• なぜ右端から始めるかというと、 キャリー（繰り上がり） の伝播が必要なため
• 左端から加算すると、途中でキャリーが発生した場合に 再計算 が必要となり、効率が悪化
• 並列化 が難しく、計算の各段階が前段階の結果に依存する構造

CPUでの加算命令とキャリー処理

• CPU は10進数ではなく、通常は64ビット整数を単位に演算
• 256ビット整数を加算する場合、 64ビットごとに分割 （リムブ化）し、対応する部分同士を加算
• 各リムブでオーバーフローが発生する場合、 キャリー を次のリムブに伝播する必要
• x86系CPUには adc（add with carry）命令 があり、前回のキャリーを自動的に加算
• 例:

  add D, H
  adc C, G
  adc B, F
  adc A, E
  

  このように、 下位から上位へ キャリーを伝播

キャリー伝播による性能低下

• adc命令 は通常のadd命令よりも 実行が遅い 傾向
• Haswell世代CPU では、add命令は最大4命令同時実行可能
• しかしadc命令は 逐次実行 が必要なため、並列化できず性能が大幅に低下
• SIMD命令 （例: vpaddq）を使えば、複数の加算を同時実行可能だが、adcによるキャリー伝播がボトルネック

キャリーを遅延させるアイデア（紙上の例）

• キャリー発生を抑えるために、 各桁の取りうる値の範囲を拡張 （例: 0-9, A-Z, * の37種類）
• これにより、 複数の数値をキャリーなしで加算 可能
• ただし、最終的には正規化して 通常の表現に戻す 必要
• この手法は キャリー伝播を遅延 させるアイデアの本質

コンピュータにおけるキャリー遅延（radix 2⁵¹表現）

• ハードウェアの制約で 取りうる値の範囲自体は変えられない

• 代わりに、リムブの ビット幅を減らし、余ったビットをキャリー用に確保

• 例: 256ビット整数を 5つのリムブ（52, 51, 51, 51, 51ビット） に分割

• これにより、 キャリー発生を遅延 し、複数回の加算をキャリーなしで並列実行可能

• この方式は radix 2⁵¹表現 と呼ばれ、 暗号分野 でよく使われる

  • 各リムブの上位ビットをキャリー用に確保
  • 例えば13ビット余裕があれば、 213回まで加算 をキャリーなしで実行可能

実装例と正規化処理

• 加算は単純なadd命令のみを使い、 並列処理 が可能
• 加算後は 正規化（キャリー伝播） 処理を実施
  • 各リムブの余剰ビットを次のリムブに加算
  • and命令でリムブのビット幅を制限
• 例:

  mov T, E
  shr T, 51
  add D, T
  and E, 0x0007FFFFFFFFFFFF
  

• 変換コストを含めても、従来方式より高速 な場合が多い

減算への応用

• 減算 も同様の手法を拡張可能
• 減算では 負のキャリー が発生するため、リムブを 符号付き整数 として扱う
• 各リムブの最上位ビットを 符号ビットとして確保
• その結果、加算よりも 1ビット分だけ余裕が減少 するが、実用上は問題なし

まとめ

• リムブ数の増加や操作数の増加 にも関わらず、 キャリー伝播の遅延 によって大幅な性能向上
• 現代CPUの並列実行能力 を最大限活用できる手法
• 暗号分野 などでの大きな整数演算の高速化に有効
• 直感に反するが、分割と余裕を持たせることで逆に高速化 が実現可能
• キャリーの遅延と正規化処理 の組み合わせが鍵