除算と平方根のハード実装 ─ 復元法からNewton-Raphsonまで

なぜ除算だけが遅いのか

加算も乗算も、現代のコアでは1サイクル前後で結果が出ます。ところが除算は数十サイクルかかり、しかも多くの実装でパイプライン化されていません。同じ四則演算なのに、なぜ除算だけがこれほど遅いのか。

理由は除算の本質にあります。乗算は部分積を「すべて一度に生成して木で足し込む」並列処理に落とせますが、除算は「商の上位桁が決まらないと、引き算する被除数（部分剰余）が定まらず、次の桁を決められない」という桁ごとの逐次依存を抱えます。筆算の割り算で、上の位の商を立ててから引き算し、その残りを下ろして次の位へ進むのと同じ構造です。この依存が並列化を阻み、除算アルゴリズムは大きく二系統に分かれます。商を1桁ずつ確定する桁回復法（digit-recurrence）と、逆数を反復近似する乗算ベース法です。

復元法と非復元法 ── 商を1桁ずつ立てる

最も素朴なのが**復元法（restoring division）**です。被除数を部分剰余Rに置き、各ステップで除数Dを引いてみます。

復元法（1ビットずつ）
  R を被除数で初期化、商 Q を空に
  各ステップ（上位桁から）:
    R = 2R - D            ; 1桁分シフトして除数を引く
    if R >= 0:  商桁 = 1   ; 引けた
    else:       商桁 = 0,  R = R + D   ; 引きすぎたので D を戻す（復元）

問題は「引きすぎたとき除数を足し戻す（復元する）」ステップです。最悪では毎ステップで引いては戻すので、加減算が2回必要になり遅くなります。

これを改良したのが非復元法（non-restoring division）です。引きすぎてもその場では戻さず、商桁を -1（負の桁）として記録し、次のステップで足し算に切り替えて辻褄を合わせます。

非復元法でも**1サイクルに商1桁（1ビット）**しか出ないのは変わりません。64ビットの除算なら原理的に64回前後の反復が要り、これが「除算＝数十サイクル」の出発点です。

SRT除算 ── 冗長表現で基数を上げる

商を1ビットずつしか出せないのを破るのがSRT除算（Sweeney・Robertson・Tocher の頭文字）です。実用の高速除算器はほぼこれを基礎にしています。SRTの工夫は2つあります。

第一に、商桁に冗長な集合を許すこと。基数4のSRTなら商桁を {-2,-1,0,1,2} のように本来必要な以上の値域から選びます。値域を重ねて冗長にすると、各桁を「ぴったり正しい1通り」に決め込む必要がなくなり、多少ラフでも許されるようになります。

第二に、この冗長性のおかげで部分剰余の上位数ビットと除数の上位数ビットだけを見れば商桁を選べる、という点です。下位まで桁上げを伝搬させて符号を確定する必要がないので、商桁の選択が速くなります。実装では部分剰余を桁上げ保存（和ベクトルと桁上げベクトルの2本）のまま持ち回り、商選択は両者の上位ビットを足した概算値で行う**商選択テーブル（QST）**を引きます。

基数を上げるほど1反復で出るビット数が増え、反復回数が減ります。ただし基数を上げると商桁の倍数（例えば基数16なら除数の最大8倍まで）を事前生成する必要があり、商選択テーブルも肥大化します。さらに、冗長集合の幅と部分剰余を見るビット数の関係が成立する範囲でしか正しく動かないため、テーブル設計にはロバートソン図と呼ばれる図を使って商桁の選択境界を厳密に詰めます。

Newton-Raphsonと二次収束 ── 除算を乗算に変える

桁回復法とは別系統が乗算ベース法です。発想は単純で、a / b を a × (1/b) と見て、逆数 1/b を反復で近似し、最後に被除数aを掛けます。逆数を求めるのに使うのがNewton-Raphson法です。

1/b は関数 f(x) = 1/x - b の零点なので、Newton反復は次の漸化式になります（割り算を含まないのが要点）。

逆数の Newton-Raphson 反復
  x_{n+1} = x_n * (2 - b * x_n)
  各反復で:  乗算2回（b*x_n と x_n*(2 - …)）
  初期値 x_0 はテーブル（LUT）で b の上位ビットから引く

この反復のすごみは二次収束にあります。誤差を e_n = 1 - b*x_n と置くと e_{n+1} = e_n^2 が成り立ち、毎反復で誤差が二乗される＝正しい精度ビット数がほぼ倍々に増えます。初期テーブルで8ビット合っていれば、1反復で約16ビット、2反復で約32ビット、3反復で約64ビットに届きます。つまり倍精度でも反復は3〜4回で十分です。

乗算ベース法の長所は、専用の桁選択回路が要らず、既存の乗算器を反復利用できる点です。短所は、各反復が乗算1〜2回ぶんのレイテンシを食うことと、結果が直接「正しく丸めた商」になる保証がなく、最後に剰余を1回計算して最終丸めを補正する必要があることです。

平方根も同じ枠組みで解ける

平方根が除算ユニットに同居できるのは、まったく同じ2系統の手法が使えるからです。

桁回復側では、SRTを拡張したSRT平方根があります。除算が「部分剰余からDを引いて商桁を立てる」のに対し、平方根は「部分剰余からこれまでの根の2倍＋新桁を引いて根の桁を立てる」形になり、引く相手が反復で育っていくだけで、商選択テーブルと冗長桁・桁上げ保存剰余という骨格は除算と共有できます。だから多くのFPUは除算と平方根を一つの桁回復ユニットにまとめます。

乗算ベース側では、1/√b（逆数平方根）をNewton反復で求めます。

逆数平方根の Newton-Raphson 反復
  x_{n+1} = x_n * (3 - b * x_n^2) / 2
  √b は最後に b * (1/√b) で得る（割り算を避けられる）

この形も二次収束で、しかも反復に除算が現れません（/2 はビットシフト）。ゲームや信号処理で有名な「高速逆数平方根」も、粗い初期値からこのNewton反復を1回回す近似でした。浮動小数点ユニットでは、この逆数平方根を初期テーブル＋数回のNewton反復で正確に詰め、最後に整列・丸めを行います。

なぜパイプライン化しにくいのか

最後に、冒頭の問いに原理から答えます。乗算がパイプライン化できて除算ができにくいのは、反復間のデータ依存の違いです。

桁回復法は、商の次の桁を選ぶのに今の部分剰余が要り、その部分剰余は前の桁が決まらないと作れません。乗算ベース法も、Newton反復の x_{n+1} は x_n を使うので反復が直列に連なります。どちらも自分の出力が次の入力に戻る帰還ループを持つため、乗算のように段の間にレジスタを挟んで毎サイクル新しい演算を投入する、という単純なパイプライン化ができません。

結果として除算器は、ループ回路を反復利用する非パイプライン・長レイテンシの実行ユニットとして実装され、アウトオブオーダのスケジューラからは「占有時間が長く、連続発行を絞る必要のある資源」として扱われます。除算が稀である前提でハードを小さく作り、頻度の高い乗算にトランジスタを割く、という設計判断がここから来ています。

まとめ

• 除算は商の桁が逐次依存するため並列化しにくく、桁回復法（復元・非復元・SRT）と乗算ベース法（Newton-Raphson・Goldschmidt）の二系統がある。
• 非復元法は引きすぎても除数を戻さず商桁 -1 で加減算の向きを切り替える。SRTは冗長な商桁集合と部分剰余・除数の上位ビットだけを見る商選択で基数を上げ、1反復で複数ビットを確定する。
• Newton-Raphson／Goldschmidtは除算を逆数の乗算に置き換え、誤差が毎反復で二乗される二次収束で精度ビット数を倍々に増やす。乗算器を反復利用でき、平方根も逆数平方根のNewton反復で同じ枠組みに乗る。
• どちらの系統も自分の出力が次反復の入力に戻る帰還ループを持つため、乗算のようにパイプライン化できず、除算器は非パイプライン・長レイテンシの実行ユニットになる。