除算アルゴリズム

除算アルゴリズムとは、2つの整数NとD（それぞれ分子と分母）が与えられたときに、それらの商および／または余り、つまりユークリッド除算の結果を計算するアルゴリズムのことである。手計算で用いられるものもあれば、デジタル回路設計やソフトウェアで使用されるものもある。

除算アルゴリズムは、大きく分けて低速除算と高速除算の2種類に分類されます。低速除算アルゴリズムは、反復ごとに最終商の1桁を生成します。低速除算の例としては、復元除算、非復元除算、非復元除算、SRT除算などがあります。高速除算法は、最終商の近似値から開始し、反復ごとに最終商の2倍の桁数を生成します。^{[ 1 ]}ニュートン・ラフソン法とゴールドシュミット法はこのカテゴリに属します。

これらのアルゴリズムの変種を用いることで、高速な乗算アルゴリズムを利用できるようになる。その結果、大きな整数については、どの乗算アルゴリズムを用いても、除算に必要なコンピュータ時間は、定数倍を除いて、乗算に必要な時間と同じになる。

議論はフォームを参照します $N/D=(Q,R)$ 、どこ

N =分子（被除数）
D =分母（除数）

は入力であり、

Q =商
R =余り

これが出力です。

繰り返し引き算による除算

最も単純な除算アルゴリズムは、歴史的にユークリッドの 『原論』第7巻命題1に示されている最大公約数アルゴリズムに組み込まれており、減算と比較のみを用いて2つの正の整数の余りを求めます。

function divide_unsigned ( N , D ) if D = 0 then error ( DivisionByZero ) end R : = N Q : = 0 while R ≥ D do R : = R − D Q : = Q + 1 end return ( Q , R ) end

商と余りが存在し、かつ一意であることの証明（ユークリッド除法で説明されている）は、加算、減算、比較を用いて、負の数と正の数の両方に適用できる完全な除算アルゴリズムを生み出す。

function divide ( N , D ) if D = 0 then error ( DivisionByZero ) end if D < 0 then ( Q , R ) : = divide ( N , − D ) return ( − Q , R ) end if N < 0 then ( Q , R ) : = divide ( − N , D ) if R = 0 then return ( − Q , 0 ) else -- 例: N = -7、D = 3 -- divide(-N, D) = divide(7, 3) = (2, 1) -- R ≠ 0 なので return (-2 - 1, 3 - 1) = (-3, 2) -- チェック: (-3)*3 + 2 = -7 return ( − Q − 1 , D − R ) end end -- この時点で、N ≥ 0 かつ D > 0 return divide_unsigned ( N , D ) end

この手順は常に R ≥ 0 を生成します。非常に単純ですが、 Ω (Q) ステップかかるため、長除法のような遅い除算アルゴリズムよりも指数関数的に遅くなります。Q が小さいことがわかっている場合（出力に敏感なアルゴリズムであるため）、この手順は有用であり、実行可能な仕様として使用できます。

代替実装

別の実装方法としては、剰余をインクリメントし、除数に達したらそれをリセットする方法がある。

のために $x,y\in \mathbb {N} _{0}$ アルゴリズムは計算します $q,r\,$ そのため $x=qy+r\,$ 、と $0\leq r<y$ :

\operatorname {div} (x,y)=\left\lfloor x/y\right\rfloor

x{\bmod {y}}=xy\left\lfloor x/y\right\rfloor

Pythonの以下のコードを考えてみてください。

def divide_unsigned2 ( numerator : int , denominator : int ) -> tuple [ int , int ] quotient : int = 0 remainder : int = 0 for _ in range ( numerator ): remainder += 1 if remainder == denominator : quotient += 1 remainder = 0 return quotient , remainder

注記

特別なケースは

x{\bmod {1}}=0

そして

x{\bmod {0}}=x

[ ²^]

変数は読み取られません。そのため、ハイライトされたquotient代入がコードから削除され、出力リストから削除されても、divide_unsigned2 はdivide_unsigned と同様に計算されます。quotient $x{\bmod {y}}$ 。

カウンタマシンとしての代替実装 シンプルなカウンタマシン（CM）は、代替実装に基づいて構築できます。CMの命令は^{[ 3 ]}^{[ 4 ]です。}

Z (n): r _{n を}0 に置き換えます。
S (n): r _nに 1 を加える。
J (m, n, q): r _m = r _nの場合、q 番目の命令にジャンプします。そうでない場合は、プログラムの次の命令に進みます。

カウンタマシンプログラムは^{[ 5 ]です。}

1: J(1,5,0) 2: S(4) 3: J(4,2,6) 4: S(5) 5: J(0,0,1) 6: S(3) 7: Z(4) 8: S(5) 9: J(0,0,1)

CM が初期レジスタ値 R1=N、R2=D (残りのレジスタ = 0) での計算を完了した後、

レジスタR3には除算N/Dの商（整数部分）が格納され、

レジスタR4には残差が格納されます。

長除法

筆算は、十進数で表された多桁の数を紙とペンで割り算する際に用いられる標準的なアルゴリズムです。被除数の左端から右端へと徐々に計算を進め、各段階で除数の最大の倍数（桁レベルで）を引いていきます。引いた倍数が商の桁となり、最終的な差が余りとなります。

2進数基数で使用する場合、この方法は、後述の（符号なし）整数除算と剰余アルゴリズムの基礎となります。短除法は、1桁の除数に適した長除法の簡略化された形式です。チャンキング（部分商法またはハングマン法とも呼ばれる）は、長除法の効率は劣りますが、理解しやすい形式です。各段階で現在持っている倍数よりも多くの倍数を減算できるようにすることで、長除法のより自由な形式も開発できます。

整数除算（符号なし）と剰余

以下のアルゴリズムは、有名な筆算の二進数版であり、 NをDで割り、商をQに、余りをRに格納します。以下の擬似コードでは、すべての値は符号なし整数として扱われます。

if D = 0 then error ( DivisionByZeroException ) end Q : = 0 -- 商と剰余をゼロに初期化R : = 0 for i : = n − 1 .. 0 do -- ここで n は N のビット数R : = R << 1 -- R を 1 ビット左シフトR ( 0 ) : = N ( i ) -- R の最下位ビットを分子の i ビットに等しく設定if R ≥ D then R : = R − D Q ( i ) : = 1 end end

例

_{N=1100 2} (12 ₁₀ ) および D=100 ₂ (4 ₁₀ )とすると

ステップ1：R=0、Q=0と設定する。 ステップ2：i=3とする（Nのビット数より1少ない）。 ステップ3：R=00とする（1ビット左シフト）。 ステップ4：R=01とする（R(0)をN(i)に設定する）。 ステップ5：R < Dなので、この文をスキップする。

ステップ2：i=2に設定 ステップ3：R=010 ステップ4：R=011 ステップ5：R < D、ステートメントはスキップ

ステップ2：i=1に設定 ステップ3：R=0110 ステップ4：R=0110 ステップ5：R>=D、ステートメントが入力 ステップ5b：R=10（R−D） ステップ5c：Q=10（Q(i)を1に設定）

ステップ2：i=0に設定 ステップ3：R=100 ステップ4：R=100 ステップ5：R>=D、ステートメントが入力 ステップ5b：R=0（R−D） ステップ5c：Q=11（Q(i)を1に設定）

終了 Q=11 ₂ (3 ₁₀ ) および R=0。

ゆっくりとした分割方法

遅い除算法はすべて標準的な漸化式に基づいています^{[ 6 ]}

R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,

どこ：

R _jは除算のj番目の部分剰余です(R(0) := N(i) ステップも含まれます)。
Bは基数（底、コンピュータや電卓では通常内部的に2）です。
q _n_{− (}_j_{+ 1)は、商の}n − ( j + 1)位の数字であり、数字の位置は最下位の 0 から最上位のn − 1まで番号が付けられています。
nは商の桁数です
Dは除数です

分割の復元

復元除算は固定小数点数に対して実行され、0 < D < Nという仮定に依存します。

商の数字qは、数字の集合{0,1}から構成される。

2進数（基数2）復元除算の基本アルゴリズムは次のとおりです。

R : = N D : = D << n -- R と D は N と Q の 2 倍のワード幅が必要ですfor i : = n − 1 .. 0 do -- 例えば 32 ビットの場合は 31..0 R : = 2 * R − D -- シフトされた値からの試行減算 (2 倍はバイナリ表現でのシフトです) if R >= 0 then q ( i ) : = 1 -- 結果ビット 1 else q ( i ) : = 0 -- 結果ビット 0 R : = R + D -- 新しい部分剰余は (復元された) シフトされた値ですend end-- ここで、N = 分子、D = 分母、n = ビット数、R = 部分剰余、q(i) = 商のビット番号i

非実行復元除算は、2R の値が保存される点を除いて復元除算と似ています。そのため、 R < 0の場合、D を再度加算する必要はありません。

非復元部門

非復元除算では、商の桁として{0, 1}ではなく{-1, 1}の桁セットを使用します。このアルゴリズムはより複雑ですが、ハードウェアで実装する場合、商ビットごとに1回の判定と加算/減算のみで済むという利点があります。減算後に復元ステップがないため^{[ 7 ]} 、演算回数を最大で半分に減らすことができ、より高速に実行できます^{[ 8 ]} 。非負数のバイナリ（基数2）非復元除算の基本アルゴリズムは次のとおりです。

-- 入力: N (分子)、D (分母) -- n = ビット数-- R と D は通常、シフトを処理するために幅 2n またはそれに近いレジスタに格納されますR : = N -- 剰余を初期化するfor i = n − 1 .. 0 do -- 例えば 31..0 で 32 ビットの場合-- 剰余を左にシフト (代数的に: 2 * R) if R >= 0 then R : = 2 * R - D ; -- D を減算q ( i ) : = 1 ; -- 商のビットを 1 として記録else R : = 2 * R + D ; -- D を加算 (復元) q ( i ) : = - 1 ; -- 商のビットを -1 として記録end if end for

このアルゴリズムに従うと、商は−1と+1の数字で構成される非標準形式になります。この形式をバイナリに変換して最終的な商を作成する必要があります。例：

−1 桁が $Q$ 一般的なようにゼロ（0）として保存され、 $P$ は $Q$ コンピューティング $M$ 自明です。元のデータに対して1の補数（ビットごとの補数）を実行します。 $Q$ 。

Q : = Q − bit . bnot ( Q ) -- Q の −1 桁が一般的なようにゼロとして表現される場合に適切です。

最後に、このアルゴリズムで計算される商は常に奇数であり、剰余Rは−D ≤ R < Dの範囲になります。例えば、5 / 2 = 3 R −1です。正の剰余に変換するには、 Qを非標準形式から標準形式に変換した後、復元ステップを1回実行します。

R < 0の場合、Q : = Q − 1、R : = R + D -- 余りが関心のある場合にのみ必要。end if

実際の剰余は R >> n です。（除算の復元と同様に、R の下位ビットは商 Q のビットが生成されるのと同じ速度で消費され、両方に単一のシフトレジスタを使用するのが一般的です。）

SRT部門

SRT 除算は、多くのマイクロプロセッサ実装でよく使われる除算方法です。^{[ 9 ]}^{[ 10 ]}このアルゴリズムは、 IBMの DW Sweeney、イリノイ大学の James E. Robertson 、インペリアルカレッジロンドンのKD Tocherにちなんで名付けられました。彼らは全員、ほぼ同時期に独立してこのアルゴリズムを開発しました (それぞれ 1957 年 2 月、1958 年 9 月、1958 年 1 月に発表)。^[¹¹^]^[¹²^]^[¹³^]

SRT除算は非復元除算に似ていますが、被除数と除数に基づいたルックアップテーブルを使用して、商の各桁を決定します。

最も大きな違いは、商に冗長な表現が用いられる点です。例えば、基数4のSRT除算を実装する場合、各商の桁は、 −2、−1、0、+1、+2の5つの選択肢から選ばれます。このため、商の桁の選択は必ずしも完璧である必要はなく、後の桁でわずかな誤差を補正できます。（例えば、0 × 4 + 2 = 1 × 4 − 2 なので、商の桁のペア(0, +2)と(1, −2)は等価です。）この許容範囲により、全幅減算を行う必要がなく、被除数と除数の最上位ビット数ビットのみを使用して商の桁を選択できます。この簡略化により、2より大きい基数を使用できるようになります。

非復元除算と同様に、最終ステップは、最後の商ビットを解決するための最終的な全幅減算と、商を標準バイナリ形式に変換することです。

初代Intel Pentiumプロセッサの悪名高い浮動小数点除算バグは、ルックアップテーブルのコーディングミスが原因でした。Pentium プロセッサは 2048 セルのテーブルを使用しており、そのうち 1066 セルに値が格納されるはずでしたが、5 つのセルの値が誤って省略されていました。^{[ 14 ]}^{[ 15 ]}^{[ 16 ]}

高速除算法

ニュートン・ラフソン区分

ニュートン・ラフソン法はニュートン法を用いて逆数を求める。 $D$ そしてその逆数を掛ける $N$ 最終的な商を求める $Q$ 。

ニュートン・ラフソン法の手順は以下のとおりです。

見積もりを計算する $X_{0}$ 逆数の場合 $1/D$ 除数の $D$ 。
より精度の高い推定値を順次計算する $X_{1},X_{2},\ldots ,X_{S}$ 逆数の。ここでニュートン・ラフソン法が用いられる。
被除数に除数の逆数を掛けて商を計算します。 $Q=NX_{S}$ 。

ニュートン法を適用して逆数を求めるには $D$ 関数を見つける必要がある $f(X)$ ゼロを持つ $X=1/D$ 明らかなそのような関数は $f(X)=DX-1$ しかし、このためのニュートン・ラフソン反復法は役に立たない。なぜなら、逆数を既に知っていなければ計算できないからである。 $D$ （さらに、反復的な改善を可能にするのではなく、1ステップで正確な逆数を計算しようとします）。実際に機能する関数は次のとおりです。 $f(X)=(1/X)-D$ 、ニュートン・ラフソン反復法では次のようになる。

X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),

これは以下から計算できます $X_{i}$ 乗算と減算のみを使用するか、2 つの融合乗算加算を使用します。

計算の観点から、式 $X_{i+1}=X_{i}+X_{i}(1-DX_{i})$ そして $X_{i+1}=X_{i}(2-DX_{i})$ これらは等価ではありません。2 番目の式を使用して 2 nビットの精度で結果を得るには、次の積を計算する必要があります。 $X_{i}$ そして $(2-DX_{i})$ 与えられた精度の2倍で $X_{i}$ （nビット）。対照的に、 $X_{i}$ そして $(1-DX_{i})$ nビットの精度で計算するだけでよい。なぜなら、 $(1-DX_{i})$ ゼロです。

エラーが次のように定義される場合 $\varepsilon _{i}=1-DX_{i}$ 、それから：

{\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}

各反復ステップで誤差を二乗するこの方法（ニュートン・ラフソン法のいわゆる二次収束）は、結果の正しい桁数が反復ごとにほぼ倍増するという効果をもたらします。これは、対象となる数値の桁数が多い場合（例えば、大きな整数領域）に非常に有用な特性となります。しかし、これはまた、特に初期推定値が小さい場合、この方法の初期収束が比較的遅くなる可能性があることを意味します。 $X_{0}$ 選択が適切ではない。

初期見積もり

初期推定値の選択という部分問題について $X_{0}$ 除数Dにビットシフトを適用して0.5 ≤ D ≤ 1となるようにスケーリングすると便利です。分子Nにも同じビットシフトを適用することで、商が変化しないことが保証されます。範囲が限定されたら、単純な多項式近似を使用して初期推定値を求めることができます。

区間における最小最悪ケース絶対誤差の線形近似 $[0.5,1]$ は：

X_{0}={48 \over 17}-{32 \over 17}D.

線形近似の係数 $T_{0}+T_{1}D$ は次のように決定されます。誤差の絶対値は $|\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|$ 誤差の最大絶対値の最小値は、チェビシェフの等振動定理を適用して決定されます。 $F(D)=1-D(T_{0}+T_{1}D)$ 局所最小値 $F(D)$ 発生するのは $F'(D)=0$ 解決策がある $D=-T_{0}/(2T_{1})$ その最小値における関数は、端点における関数とは逆の符号でなければならない。すなわち、 $F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))$ 2つの未知数を含む2つの方程式は、一意の解を持つ。 $T_{0}=48/17$ そして $T_{1}=-32/17$ 最大誤差は $F(1)=1/17$ この近似を用いると、初期値の誤差の絶対値は以下より小さくなる。

\vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.

最適な二次近似 $1/D$ 区間は

X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.

これは、誤差を再スケーリングした第1種3次チェビシェフ多項式に等しくするように選択され、誤差の絶対値は1/99以下になります。この改善は、 $\log _{2}(\log 99/\log 17)\approx 0.7$ ニュートン・ラフソン法による反復計算は、1回の反復計算よりも少ない計算コストで済みます。

レメズアルゴリズムを用いて係数を計算することで、2次以上の多項式近似を生成することが可能です。ただし、初期推定にはより多くの計算サイクルが必要となりますが、その代わりにニュートン・ラフソン法の反復回数を減らすことが期待できます。

この方法では収束が正確に二次関数であるため、初期誤差から次のことが導かれる。 $\varepsilon _{0}$ 、 $S$ 反復により、正確な答えが得られます。

P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1

バイナリの桁数。典型的な値は次のとおりです。

IEEE単精度では、2次式の初期推定値と2回の反復計算で十分な精度が得られますが、倍精度では3回の反復計算では限界があります。倍精度と倍精度拡張の両方の形式では、線形式の初期推定値と4回の反復計算で十分です。

擬似コード

以下は、 NとDの商をP桁の精度で計算するものです。

^{D を M × 2 e}で表す(1 ≤ M < 2、標準浮動小数点表現) D' := D / 2 ^e+1// 0.5 から 1 の範囲にスケーリング。ビットシフト / 指数減算で実行可能 N' := N / 2 ^e+1 X := 48/17 − 32/17 × D' // D と同じ精度で定数を事前計算するrepeat $\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$ 回数// 固定Pに基づいて事前に計算可能 X := X + X × (1 - D' × X) end return N' × X

例えば、倍精度浮動小数点除算の場合、この方法では10回の乗算、9回の加算、2回のシフト演算が必要になります。

3次反復

誤差を3乗するために3回の乗算を用いる反復処理があります。

\varepsilon _{i}=1-DX_{i}

Y_{i}=X_{i}\varepsilon _{i}

X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.

Y i _ε i_という項は新しいものです。

上記をさらに展開すると、 $X_{i+1}$ 次のように書くことができます

{\begin{aligned}X_{i+1}&=X_{i}+X_{i}\varepsilon _{i}+X_{i}\varepsilon _{i}^{2}\\&=X_{i}+X_{i}(1-DX_{i})+X_{i}(1-DX_{i})^{2}\\&=3X_{i}-3DX_{i}^{2}+D^{2}X_{i}^{3},\end{aligned}}

その結果、誤差項は

{\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-3DX_{i}+3D^{2}X_{i}^{2}-D^{3}X_{i}^{3}\\&=(1-DX_{i})^{3}\\&=\varepsilon _{i}^{3}.\end{aligned}}

これは二次反復の計算の3/2ですが、 $\log 3/\log 2\approx 1.585$ 収束性は同程度であるため、わずかに効率的です。言い換えれば、この方法を2回繰り返すと、誤差は9乗に増加しますが、計算コストは同じで、2次反復を3回繰り返すと誤差は8乗にしか増加しません。

正しいビット数 $S$ 反復回数は

P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1

バイナリの桁数。典型的な値は次のとおりです。

2次初期推定値に2回の3次反復計算を加えることで、IEEE倍精度結果に必要な十分な精度が得られます。また、2次反復計算と3次反復計算を組み合わせることも可能です。

少なくとも1回の二次反復を使用することで、誤差が正になることが保証されます。つまり、逆数が過小評価されます。^{[ 17 ]}^{： 370}正確に丸められた商が必要な場合は、これにより後続の丸めステップが簡略化されます。

初期化または反復処理において高次の多項式を使用すると、余分な乗算が必要になるため、その時間をより多くの反復処理に費やす方が効率的であるため、パフォーマンスが低下します。

ゴールドシュミット部門

ゴールドシュミット除法^{[ 18 ]}（ロバート・エリオット・ゴールドシュミットによる）^{[ 19 ]}は、除数が1に収束するように選択された共通因子F _iで被除数と除数の両方を繰り返し乗算する反復プロセスを使用します。これにより、被除数は求める商Qに収束します。

Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.

ゴルトシュミット除法の手順は以下のとおりです。

乗数F _iの推定値を生成します。
被除数と除数をF _iで掛けます。
除数が1に十分近い場合は、被除数を返し、そうでない場合は、ステップ1に戻る。

N / D が 0 < D < 1となるようにスケーリングされていると仮定すると、各F _{i は}Dに基づいている。

F_{i+1}=2-D_{i}.

被除数と除数を因数で掛け合わせると次のようになります。

{\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.

十分な回数kの反復の後 $Q=N_{k}$ 。

ゴールドシュミット法は、AMD Athlon CPU およびそれ以降のモデルで使用されています。^{[ 20 ]}^{[ 21 ]}また、アンダーソン・アール・ゴールドシュミットべき乗 (AEGP) アルゴリズムとしても知られており、さまざまなIBMプロセッサで実装されています。^{[ 22 ]}^{[ 23 ]}ニュートン・ラフソン法と同じ速度で収束しますが、ゴールドシュミット法の利点の 1 つは、分子と分母の乗算を並列に実行できることです。^{[ 23 ]}

二項定理

ゴールドシュミット法は、二項定理による簡略化を可能にする因子とともに使用できます。と仮定します。 $N/D$ ⁠は2のべき乗でスケーリングされ、 $D\in \left({\tfrac {1}{2}},1\right]$ 私たちは選びます $D=1-x$ そして $F_{i}=1+x^{2^{i}}$ これにより、

{\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}

。

$n$ ステップ後 $\left(x\in \left[0,{\tfrac {1}{2}}\right)\right)$ 分母 $1-x^{2^{n}}$ 丸めることができます1相対誤差付き

\varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}

これは最大で $2^{-2^{n}}$ いつ $x={\tfrac {1}{2}}$ これにより、最小限の精度が確保されます。 $2^{n}$ 二進数。

大規模整数法

ハードウェア実装用に設計された方法は、一般的に、数千または数百万の十進数を持つ整数には対応できません。このような整数は、たとえば暗号化におけるモジュラー削減などで頻繁に発生します。このような大きな整数に対しては、より効率的な除算アルゴリズムによって、問題を少数の乗算を使用するように変換し、その後、カラツバアルゴリズム、トゥーム・クック乗算、またはシェーンハーゲ・シュトラッセンアルゴリズムなどの漸近的に効率的な乗算アルゴリズムを使用して実行できます。結果として、除算の計算複雑度は、乗算の計算複雑度と同じオーダーになります（乗法定数を除く）。例としては、上記で説明したニュートン法による乗算への還元^[²⁴^]、およびわずかに高速なバーニケル・ジーグラー除算^[²⁵^]、バレット削減、モンゴメリー削減アルゴリズムなどがあります。^[²⁶^]ニュートン法は、同じ除数で何度も割る必要があるシナリオで特に効率的です。最初のニュートン逆変換の後、各除算には 1 つの (切り捨てられた) 乗算のみが必要だからです。

定数による除算

定数Dによる除算は、その逆数による乗算と同等です。分母は定数なので、その逆数 (1/ D ) も定数です。したがって、コンパイル時に(1/ D )の値を一度計算し、実行時に除算N/Dではなく乗算N ·(1/ D ) を実行することが可能です。浮動小数点演算では (1/ D )の使用はほとんど問題になりませんが、^[^a^]整数演算では、逆数は常にゼロと評価されます (| D | > 1 の場合)。

(1/ D )を明示的に使用する必要はありません。( X / Y ) が (1/ D ) に還元される値であれば、どれでも使用できます。たとえば、3 で割る場合、1/3、2/6、3/9、または 194/582 を使用できます。したがって、Yが 2 のべき乗であれば、除算ステップは高速右ビットシフトに還元されます。N/D を (N·X)/Y として計算すると、除算が乗算とシフトに置き換えられます。括弧が重要であることに注意してください。N ·( X / Y )はゼロに評価されます。

しかし、D自体が 2 のべき乗でない限り、上記の条件を満たすXとYは存在しません。幸いなことに、( N · X )/ Y は、 ( X / Y ) が1 / Dと完全に等しくなくても、近似によって生じる誤差がシフト操作によって破棄されるビットにあるほど「十分近い」場合でも、整数演算では N / Dとまったく同じ結果を与えます。 ^[²⁷^]^[²⁸^]^[²⁹^]バレット縮約では、 Yの値に 2 のべき乗を使用して、 Yによる除算を単純な右シフトにします。^[^b^]

具体的な固定小数点演算の例として、32 ビット符号なし整数の場合、3 による除算は⁠ 2863311531 / 2 ³³ ⁠による乗算に置き換えることができます。これは、2863311531 (16進数0xAAAAAAAB)による拡大乗算の後に 33 ビット右シフトを行うものです。2863311531 の値は⁠ 2 ³³ / 3 ⁠^{として計算され、切り上げられます。同様に、10 による除算は、3435973837 (0xCCCCCCCD) による乗算の後に 2 35} (または 35 ビット右シフト)による除算として表現できます。 ^[³¹^]^:^p230-234 OEIS は、乗算の定数のシーケンスを A346495として、右シフトの定数のシーケンスをA346496として提供しています。

除数 $D が$ 2 のべき乗でない一般的な $xビット符号なし整数除算の場合、次の恒等式は除算を 2 つの$ $x$ ビット加算/減算、1 つの $x$ ビット× $x$ ビット乗算 (結果の上位半分のみを使用)、およびいくつかのシフトに変換します。 $k=x+\lceil \log _{2}{D}\rceil$ そして $a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}$ :

\left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor

場合によっては、「定数を掛ける」を一連のシフトと加算または減算に変換することで、定数による除算をさらに短時間で実行できます。^{[ 32 ]}特に興味深いのは10による除算で、必要に応じて余りとともに正確な商が得られます。^{[ 33 ]}

丸め誤差

除算演算を実行すると、正確な商は $q$ そして残り $r$ コンピュータの精度限界内に収まるように近似されます。除算アルゴリズムは次のとおりです。

$[a=bq+r]$

どこ $0\leq r<|b|$ 。

浮動小数点演算では、商は $q$ は次のように表されます。 ${\tilde {q}}$ そして残りは $r$ として ${\tilde {r}}$ 丸め誤差が生じる $\epsilon _{q}$ そして $\epsilon _{r}$ :

$[{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]$

この丸め処理によって小さな誤差が生じ、それが後続の計算で伝播・蓄積される可能性があります。このような誤差は、反復処理やほぼ等しい値を減算する場合に特に顕著になります（有効数字の喪失と呼ばれます）。これらの誤差を軽減するために、ガード桁の使用やより高い精度（または任意精度）などの手法が用いられます。^{[ 34 ]}^{[ 35 ]}

注記

↑この最適化が引き起こす問題は「小さい」にもかかわらず、この相互最適化は不正確であるため、現代のコンパイラでは通常「高速数学」フラグの背後に隠されています。
↑現代のコンパイラは一般的にこの整数乗算とシフトの最適化を実行しますが、実行時にのみ判明する定数については、プログラム自身が最適化を実装する必要があります。^{[ 30 ]}

参考文献

↑ Rodeheffer, Thomas L. (2008-08-26).ソフトウェア整数除算(PDF) (技術レポート). Microsoft Research, Silicon Valley.
↑比較: プロシージャdivide_unsignedでは、厳密にdenominator正でなければなりません。
↑ Shepherdson, JC ; Sturgis, HE (1963). "再帰関数の計算可能性" . Journal of the Association for Computing Machinery . 10 (2): 217– 255. doi : 10.1145/321160.321170 .
↑カットランド、ナイジェル (1980).計算可能性：再帰関数理論入門(PDF) .ケンブリッジ大学出版局. p. 12. ISBN 97805212238432025年9月16日に取得。
↑このコードは「URMシミュレータ」上で動作します。オキシデンタル大学（ロサンゼルス）の無制限レジスタマシン（URM）シミュレータ（エミュレータ）は、「仮想URM」です。これは、ケンブリッジ大学出版局のナイジェル・J・カットランド著『計算可能性：再帰関数理論入門』に記載されているURM仕様に基づいて作成されています。
↑ Morris, James E.; Iniewski, Krzysztof (2017-11-22). Nanoelectronic Device Applications Handbook . CRC Press. ISBN 978-1-351-83197-0。
↑ Shaw, Robert F. (1950). "Arithmetic Operations in a Binary Computer" . Review of Scientific Instruments . 21 (8): 690. Bibcode : 1950RScI...21..687S . doi : 10.1063/1.1745692 . ISSN 0034-6748 . 2022-02-28 のオリジナルからアーカイブ済み. 2022-02-28に取得.
↑ Flynn. "Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)" (PDF) . Stanford University . 2022-04-18 のオリジナルからアーカイブ(PDF) . 2019-06-24に取得.
↑ Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (1998年9月9日). SRT部門: アーキテクチャ、モデル、実装(PDF) (技術報告書). スタンフォード大学. 2016年12月24日のオリジナルからアーカイブ(PDF) 。 2016年12月23日取得。
↑ McCann, Mark; Pippenger, Nicholas (2005). "SRT 除算アルゴリズムを動的システムとして捉える" . SIAM Journal on Computing . 34 (6): 1279–1301 . CiteSeerX 10.1.1.72.6993 . doi : 10.1137/S009753970444106X . hdl : 2429/12179 . 2022年8月24日のオリジナルからアーカイブ済み。 2022年8月24日に取得。
↑コック、ジョン、スウィーニー、DW（1957年2月11日）、「並列装置における高速演算（社内メモ）」、IBM、p.20 、2022年8月24日にオリジナルからアーカイブ、 2022年8月24日に取得 {{citation}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)
↑ Robertson, James (1958-09-01). "A New Class of Digital Division Methods". IRE Transactions on Electronic Computers . EC-7 (3). IEEE: 218–222 . Bibcode : 1958IRTEC...7..218R . doi : 10.1109/TEC.1958.5222579 . hdl : 2027/uiuo.ark:/13960/t0gt7529c .
↑ Tocher, KD (1958-01-01). "自動バイナリコンピュータのための乗算と除算の技術" . The Quarterly Journal of Mechanics and Applied Mathematics . 11 (3): 364– 384. doi : 10.1093/qjmam/11.3.364 . 2022-08-24のオリジナルからアーカイブ済み。2022-08-24 に取得。
↑ 「浮動小数点欠陥の統計分析」。インテル社。1994年。2013年10月23日にオリジナルからアーカイブ済み。 2013年10月22日に取得。
↑ Oberman, Stuart F.; Flynn, Michael J. (1995年7月).除算アルゴリズムと実装の分析(PDF) (技術報告書). スタンフォード大学. CSL-TR-95-675. 2017年5月17日のオリジナルからアーカイブ( PDF) 。 2016年12月23日取得。
↑ Shirriff, Ken (2024年12月28日). 「Intelの4億7500万ドルのエラー：Pentium部門のバグの背後にあるシリコン」 . Righto . 2024年12月30日閲覧。
↑ Ercegovac, Miloš D.; Lang, Tomás ( 2004). 「第7章：逆数除算、逆平方根、反復近似による平方根」『デジタル算術』Morgan Kaufmann、 367–395頁。ISBN 1-55860-798-6。
↑ Goldschmidt, Robert E. (1964). Applications of Division by Convergence (PDF) (Thesis). M.Sc. dissertation. MIT OCLC 34136725 . 2015年12月10日のオリジナルからアーカイブ(PDF) . 2015年9月15日取得.
↑ 「著者」 . IBM Journal of Research and Development . 11 : 125–127 . 1967. doi : 10.1147/rd.111.0125 . 2018年7月18日にオリジナルからアーカイブ済み。
↑ Oberman, Stuart F. (1999). "AMD-K7マイクロプロセッサにおける浮動小数点除算および平方根アルゴリズムと実装" (PDF) .第14回IEEEコンピュータ算術シンポジウム議事録 (カタログ番号99CB36336) . pp. 106–115 . doi : 10.1109/ARITH.1999.762835 . ISBN 0-7695-0116-8. S2CID 12793819 . 2015年11月29日にオリジナルからアーカイブ（PDF）されました。2015年9月15日に取得。
↑ Soderquist, Peter; Leeser, Miriam (1997年7月～8月)。「除算と平方根：適切な実装の選択」。IEEE Micro。17 ( 4): 56–66。Bibcode: 1997IMicr..17d..56S。doi : 10.1109 / 40.612224。
↑ SF Anderson、JG Earle、RE Goldschmidt、DM Powers。「IBM 360/370 モデル 91: 浮動小数点実行ユニット」、 IBM Journal of Research and Development、1997年1月
1 2 Guy, Even; Peter, Siedel; Ferguson, Warren (2005年2月1日). "Goldschmidtの除算アルゴリズムのパラメトリック誤差解析" . Journal of Computer and System Sciences . 70 (1): 118– 139. doi : 10.1016/j.jcss.2004.08.004 .
↑ Hasselström, Karl (2003). Fast Division of Large Integers: A Comparison of Algorithms (PDF) (M.Sc. in Computer Science thesis). Royal Institute of Technology. Archived from the original (PDF) on 8 July 2017. Retrieved 2017-07-08 .
↑ Joachim Ziegler、Christoph Burnikel (1998)、高速再帰部門、Max-Planck-Institut für Informatik、オリジナルから 2011 年 4 月 26 日にアーカイブ、2021 年 9 月 10 日に取得{{citation}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)
↑ Barrett, Paul (1987). 「標準デジタル信号プロセッサ上でのRivest-Shamir-Adleman公開鍵暗号アルゴリズムの実装」 . Proceedings on Advances in cryptology---CRYPTO '86 . London, UK: Springer-Verlag. pp. 311–323 . ISBN 0-387-18047-8。
↑ Granlund, Torbjörn; Montgomery, Peter L. (1994 年 6 月). "Division by Invariant Integers using Multiplication" (PDF) . SIGPLAN Notices . 29 (6): 61– 72. CiteSeerX 10.1.1.1.2556 . doi : 10.1145/773473.178249 . 2019 年 6 月 6 日にオリジナルからアーカイブ(PDF) 。 2015 年 12 月 8 日に取得.
↑ Möller, Niels; Granlund, Torbjörn (2011年2月)。「不変整数による改良除算」(PDF) . IEEE Transactions on Computers . 60 (2): 165– 175. Bibcode : 2011ITCmp..60..165M . doi : 10.1109/TC.2010.143 . S2CID 13347152 . 2015年12月22日のオリジナルからアーカイブ(PDF) . 2015年12月8日取得.
↑馬鹿げた_fish。「割り算の労働（エピソード III）：定数によるより高速な符号なし割り算」Wayback Machineに 2022-01-08 にアーカイブ済み。2011 年。
↑馬鹿げた魚。「libdivide、最適化された整数除算」。2021年11月23日にオリジナルからアーカイブ済み。2021年7月6日に取得。
↑ウォーレン・ジュニア、ヘンリー・S. (2013).ハッカーズ・ディライト（第2版）.アディソン・ウェスリー-ピアソン・エデュケーション社. ISBN 978-0-321-84268-8。
↑ラバッド、ロバート A.、ゴロフチェンコ、ニコライ、ニュートン、ジェームズ、パーカー、デイビッド; Massmind: "定数による二進除算" 2022年1月9日にWayback Machineにアーカイブ済み
↑ Vowels, RA (1992). "10による除算". Australian Computer Journal . 24 (3): 81–85 .
↑ L. Popyack, Jeffrey (2000年6月) 「丸め誤差」。ドレクセル大学。
↑ 「9. 機械数、丸め誤差、誤差伝播」チャールストン大学。2021年2月8日。

さらに読む

Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques" . quadibloc . 2018-07-03 のオリジナルからアーカイブ済み. 2018-07-16に取得.

[28] この最適化が引き起こす問題は「小さい」にもかかわらず、この相互最適化は不正確であるため、現代のコンパイラでは通常「高速数学」フラグの背後に隠されています。

[33] 現代のコンパイラは一般的にこの整数乗算とシフトの最適化を実行しますが、実行時にのみ判明する定数については、プログラム自身が最適化を実装する必要があります。^{[ 30 ]}

[1] Rodeheffer, Thomas L. (2008-08-26).ソフトウェア整数除算(PDF) (技術レポート). Microsoft Research, Silicon Valley.

[2] 比較: プロシージャdivide_unsignedでは、厳密にdenominator正でなければなりません。

[3] Shepherdson, JC ; Sturgis, HE (1963). "再帰関数の計算可能性" . Journal of the Association for Computing Machinery . 10 (2): 217– 255. doi : 10.1145/321160.321170 .

[4] カットランド、ナイジェル (1980).計算可能性：再帰関数理論入門(PDF) .ケンブリッジ大学出版局. p. 12. ISBN 97805212238432025年9月16日に取得。

[5] このコードは「URMシミュレータ」上で動作します。オキシデンタル大学（ロサンゼルス）の無制限レジスタマシン（URM）シミュレータ（エミュレータ）は、「仮想URM」です。これは、ケンブリッジ大学出版局のナイジェル・J・カットランド著『計算可能性：再帰関数理論入門』に記載されているURM仕様に基づいて作成されています。

[6] Morris, James E.; Iniewski, Krzysztof (2017-11-22). Nanoelectronic Device Applications Handbook . CRC Press. ISBN 978-1-351-83197-0。

[7] Shaw, Robert F. (1950). "Arithmetic Operations in a Binary Computer" . Review of Scientific Instruments . 21 (8): 690. Bibcode : 1950RScI...21..687S . doi : 10.1063/1.1745692 . ISSN 0034-6748 . 2022-02-28 のオリジナルからアーカイブ済み. 2022-02-28に取得.

[8] Flynn. "Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)" (PDF) . Stanford University . 2022-04-18 のオリジナルからアーカイブ(PDF) . 2019-06-24に取得.

[10] Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (1998年9月9日). SRT部門: アーキテクチャ、モデル、実装(PDF) (技術報告書). スタンフォード大学. 2016年12月24日のオリジナルからアーカイブ(PDF) 。 2016年12月23日取得。

[11] McCann, Mark; Pippenger, Nicholas (2005). "SRT 除算アルゴリズムを動的システムとして捉える" . SIAM Journal on Computing . 34 (6): 1279–1301 . CiteSeerX 10.1.1.72.6993 . doi : 10.1137/S009753970444106X . hdl : 2429/12179 . 2022年8月24日のオリジナルからアーカイブ済み。 2022年8月24日に取得。

[12] コック、ジョン、スウィーニー、DW（1957年2月11日）、「並列装置における高速演算（社内メモ）」、IBM、p.20 、2022年8月24日にオリジナルからアーカイブ、 2022年8月24日に取得 {{citation}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

[13] Robertson, James (1958-09-01). "A New Class of Digital Division Methods". IRE Transactions on Electronic Computers . EC-7 (3). IEEE: 218–222 . Bibcode : 1958IRTEC...7..218R . doi : 10.1109/TEC.1958.5222579 . hdl : 2027/uiuo.ark:/13960/t0gt7529c .

[14] Tocher, KD (1958-01-01). "自動バイナリコンピュータのための乗算と除算の技術" . The Quarterly Journal of Mechanics and Applied Mathematics . 11 (3): 364– 384. doi : 10.1093/qjmam/11.3.364 . 2022-08-24のオリジナルからアーカイブ済み。2022-08-24 に取得。

[15] 「浮動小数点欠陥の統計分析」。インテル社。1994年。2013年10月23日にオリジナルからアーカイブ済み。 2013年10月22日に取得。

[16] Oberman, Stuart F.; Flynn, Michael J. (1995年7月).除算アルゴリズムと実装の分析(PDF) (技術報告書). スタンフォード大学. CSL-TR-95-675. 2017年5月17日のオリジナルからアーカイブ( PDF) 。 2016年12月23日取得。

[17] Shirriff, Ken (2024年12月28日). 「Intelの4億7500万ドルのエラー：Pentium部門のバグの背後にあるシリコン」 . Righto . 2024年12月30日閲覧。

[DigitalArithmetic-18] Ercegovac, Miloš D.; Lang, Tomás ( 2004). 「第7章：逆数除算、逆平方根、反復近似による平方根」『デジタル算術』Morgan Kaufmann、 367–395頁。ISBN 1-55860-798-6。

[19] Goldschmidt, Robert E. (1964). Applications of Division by Convergence (PDF) (Thesis). M.Sc. dissertation. MIT OCLC 34136725 . 2015年12月10日のオリジナルからアーカイブ(PDF) . 2015年9月15日取得.

[20] 「著者」 . IBM Journal of Research and Development . 11 : 125–127 . 1967. doi : 10.1147/rd.111.0125 . 2018年7月18日にオリジナルからアーカイブ済み。

[21] Oberman, Stuart F. (1999). "AMD-K7マイクロプロセッサにおける浮動小数点除算および平方根アルゴリズムと実装" (PDF) .第14回IEEEコンピュータ算術シンポジウム議事録 (カタログ番号99CB36336) . pp. 106–115 . doi : 10.1109/ARITH.1999.762835 . ISBN 0-7695-0116-8. S2CID 12793819 . 2015年11月29日にオリジナルからアーカイブ（PDF）されました。2015年9月15日に取得。

[22] Soderquist, Peter; Leeser, Miriam (1997年7月～8月)。「除算と平方根：適切な実装の選択」。IEEE Micro。17 ( 4): 56–66。Bibcode: 1997IMicr..17d..56S。doi : 10.1109 / 40.612224。

[23] SF Anderson、JG Earle、RE Goldschmidt、DM Powers。「IBM 360/370 モデル 91: 浮動小数点実行ユニット」、 IBM Journal of Research and Development、1997年1月

[goldschmidt-analysis-24] 1 2 Guy, Even; Peter, Siedel; Ferguson, Warren (2005年2月1日). "Goldschmidtの除算アルゴリズムのパラメトリック誤差解析" . Journal of Computer and System Sciences . 70 (1): 118– 139. doi : 10.1016/j.jcss.2004.08.004 .

[25] Hasselström, Karl (2003). Fast Division of Large Integers: A Comparison of Algorithms (PDF) (M.Sc. in Computer Science thesis). Royal Institute of Technology. Archived from the original (PDF) on 8 July 2017. Retrieved 2017-07-08 .

[26] Joachim Ziegler、Christoph Burnikel (1998)、高速再帰部門、Max-Planck-Institut für Informatik、オリジナルから 2011 年 4 月 26 日にアーカイブ、2021 年 9 月 10 日に取得{{citation}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

[27] Barrett, Paul (1987). 「標準デジタル信号プロセッサ上でのRivest-Shamir-Adleman公開鍵暗号アルゴリズムの実装」 . Proceedings on Advances in cryptology---CRYPTO '86 . London, UK: Springer-Verlag. pp. 311–323 . ISBN 0-387-18047-8。

[29] Granlund, Torbjörn; Montgomery, Peter L. (1994 年 6 月). "Division by Invariant Integers using Multiplication" (PDF) . SIGPLAN Notices . 29 (6): 61– 72. CiteSeerX 10.1.1.1.2556 . doi : 10.1145/773473.178249 . 2019 年 6 月 6 日にオリジナルからアーカイブ(PDF) 。 2015 年 12 月 8 日に取得.

[30] Möller, Niels; Granlund, Torbjörn (2011年2月)。「不変整数による改良除算」(PDF) . IEEE Transactions on Computers . 60 (2): 165– 175. Bibcode : 2011ITCmp..60..165M . doi : 10.1109/TC.2010.143 . S2CID 13347152 . 2015年12月22日のオリジナルからアーカイブ(PDF) . 2015年12月8日取得.

[31] 馬鹿げた_fish。「割り算の労働（エピソード III）：定数によるより高速な符号なし割り算」Wayback Machineに 2022-01-08 にアーカイブ済み。2011 年。

[32] 馬鹿げた魚。「libdivide、最適化された整数除算」。2021年11月23日にオリジナルからアーカイブ済み。2021年7月6日に取得。

[Hacker's_Delight-34] ウォーレン・ジュニア、ヘンリー・S. (2013).ハッカーズ・ディライト（第2版）.アディソン・ウェスリー-ピアソン・エデュケーション社. ISBN 978-0-321-84268-8。

[35] ラバッド、ロバート A.、ゴロフチェンコ、ニコライ、ニュートン、ジェームズ、パーカー、デイビッド; Massmind: "定数による二進除算" 2022年1月9日にWayback Machineにアーカイブ済み

[36] Vowels, RA (1992). "10による除算". Australian Computer Journal . 24 (3): 81–85 .

[37] L. Popyack, Jeffrey (2000年6月) 「丸め誤差」。ドレクセル大学。

[38] 「9. 機械数、丸め誤差、誤差伝播」チャールストン大学。2021年2月8日。

[ 1 ]

2

[ 3 ]

[ 4 ]です。

[ 5 ]です。

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[

[

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[

[

[

[

[

[

[

[

[

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 30 ]