除算アルゴリズム

除算アルゴリズムは、2 つの整数NとD (それぞれ分子と分母) が与えられ、ユークリッド除算の結果である商と余りを計算するアルゴリズムです。一部は手作業で適用され、その他はデジタル回路設計やソフトウェアで採用されています。

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

これらのアルゴリズムのバリエーションにより、高速乗算アルゴリズムを使用できます。その結果、大きな整数の場合、どの乗算アルゴリズムを使用しても、除算に必要なコンピュータ時間は、定数倍まで乗算に必要な時間と同じになります。

議論はフォームを参照する。 ${\displaystyle N/D=(Q,R)}$

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

は入力であり、

• Q =商
• R =残り

出力です。

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

R  : =  N 
Q  : =  0 
R ≥ Dの場合 R : = R − D Q : = Q + 1を実行し、( Q , R )を返します。   
      
      

 

商と余りが存在し、一意であることの証明 (ユークリッド除算で説明) により、加算、減算、比較を使用して、負の数と正の数の両方に適用できる完全な除算アルゴリズムが得られます。

function  division ( N ,  D ) 
  if  D  =  0  then  error ( DivisionByZero )  end 
  if  D  <  0  then  ( Q ,  R )  : =  division ( N ,  − D );  return  ( − Q ,  R )  end 
  if  N  <  0  then 
    ( Q , R )  : =  division ( − N ,  D ) 
    if  R  =  0  then  return  ( − Q ,  0 ) 
    else  return  ( − Q  −  1 ,  D  −  R )  end 
  end 
  -- この時点で、N ≥ 0 かつ D > 0 
  return  division_unsigned ( N ,  D ) 
end   
function  division_unsigned ( N ,  D ) 
  Q  : =  0 ;  R  : =  N 
  while  R  ≥  D  do 
    Q  : =  Q  +  1 
    R  : =  R  −  D 
  end 
  return  ( Q ,  R ) 
end

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

長除法は、10 進数表記で表された多桁の数字をペンと紙で除算するときに使用される標準的なアルゴリズムです。このアルゴリズムは、被除数の左端から右端へと徐々にシフトし、各段階で除数の最大可能な倍数 (桁レベル) を減算します。その後、倍数が商の桁になり、最終的な差が余りになります。

この方法は、2 進基数で使用すると、以下の剰余アルゴリズム (符号なし) 整数除算の基礎となります。短除算は、1 桁の除数に適した長除算の短縮形です。チャンキング (部分商法またはハングマン法とも呼ばれる) は、長除算の効率の低い形式ですが、理解しやすいかもしれません。各段階で現在よりも多くの倍数を減算できるようにすることで、長除算のより自由な形式も開発できます。

次のアルゴリズムは、有名な長除算の 2 進バージョンであり、 N をDで割り、商をQに、余りをRに格納します。次の疑似コードでは、すべての値が符号なし整数として扱われます。

 D  =  0 の場合、 エラー( DivisionByZeroException )が発生します。 終了
Q  : =  0                   -- 商と余りをゼロに初期化します。
R  : =  0                      
for  i  : =  n  −  1  ..  0  do   -- n は N のビット数です。
  R  : =  R  <<  1            -- R を 1 ビット左にシフトします。
  R ( 0 )  : =  N ( i )           -- R の最下位ビットを分子のビット i と同じに設定します。 
  R ≥ Dの場合 、R : = R − D Q ( i ) : = 1終了します。終了   
        
      
  

_{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。

低速除算法はすべて標準的な再帰方程式に基づいている^[2]

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

どこ：

• R _{j は}割り算のj番目の部分剰余である。
• 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 を掛けると 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回だけになるという利点があります。減算後に復元ステップがないため、^[3]操作回数を最大半分に減らし、より高速に実行できます。^[4] 負でない数の2進数（基数2）非復元除算の基本アルゴリズムは次のとおりです。

R  : =  N 
D  : =  D  <<  n             -- R と D は N と Q の 2 倍のワード幅が必要です。 
for  i  =  n  −  1  ..  0  do   -- たとえば 32 ビットの場合は 31..0 
  if  R  >=  0  then 
    q ( i )  : =  + 1 
    R  : =  2  *  R  −  D 
  else 
    q ( i )  : =  − 1 
    R  : =  2  *  R  +  D 
  end  if 
end
 
-- 注: N = 分子、D = 分母、n = ビット数、R = 部分剰余、q(i) = 商のビット数 i。

このアルゴリズムに従うと、商は -1 と +1 の数字で構成される非標準形式になります。最終的な商を形成するには、この形式を 2 進数に変換する必要があります。例:

の -1 桁目が、一般的なようにゼロ (0) として格納されている場合、 となり、計算は簡単です。元の に対して 1 の補数 (ビットごとの補数) を実行します。 ${\displaystyle Q}$${\displaystyle P}$ ${\displaystyle Q}$${\displaystyle M}$${\displaystyle 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   -- 剰余が重要な場合のみ必要
。 

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

SRT除算は、多くのマイクロプロセッサ実装でよく使われる除算方法です。 ^{[5] [6]}このアルゴリズムは、 IBMのDWスウィーニー、イリノイ大学のジェームズ・E・ロバートソン、インペリアル・カレッジ・ロンドンのKDトッチャーにちなんで名付けられました。彼らはほぼ同時期にこのアルゴリズムを独立して開発しました（それぞれ1957年2月、1958年9月、1958年1月に発表）。^{[7] [8] [9]}

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

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

非復元除算と同様に、最後の手順は、最後の商ビットを解決するための最終的な全角減算と、商の標準の 2 進形式への変換です。

インテルペンティアムプロセッサの悪名高い浮動小数点除算のバグは、ルックアップテーブルのコードが誤っていたために発生しました。1066エントリのうち5つが誤って省略されていました。^{[10] [11]}

ニュートン・ラプソン法では、ニュートン法を使用しての逆数を求め、その逆数に を掛けて最終的な商を求めます。${\displaystyle D}$${\displaystyle N}$${\displaystyle Q}$

ニュートン・ラプソン除算の手順は次のとおりです。

1. 除数の逆数の推定値を計算します。${\displaystyle X_{0}}$${\displaystyle 1/D}$${\displaystyle D}$
2. 逆数のより正確な推定値を連続的に計算します。ここでは、ニュートン・ラプソン法を使用します。${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$
3. 被除数に除数の逆数を掛けて商を計算します。${\displaystyle Q=NX_{S}}$

ニュートン法を適用して の逆数を求めるには、で零点を持つ関数を見つける必要があります。そのような関数として明らかなのは ですが、ニュートン・ラプソン反復法は の逆数が分かっていなければ計算できないため役に立ちません(さらに、反復による改善ではなく、1 ステップで正確な逆数を計算しようとします)。 が有効な関数であり、ニュートン・ラプソン反復法では次の式が得られます 。${\displaystyle D}$${\displaystyle f(X)}$${\displaystyle X=1/D}$${\displaystyle f(X)=DX-1}$${\displaystyle D}$${\displaystyle f(X)=(1/X)-D}$

$${\displaystyle 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}),}$$

これは、乗算と減算のみを使用して計算することも、2つの融合された乗算と加算を使用して計算することもできます。 ${\displaystyle X_{i}}$

計算の観点から見ると、式と は同等ではありません。2番目の式を使用して2 nビットの精度の結果を得るには、との積を の指定された精度( nビット)の2 倍で計算する必要があります。 ^[要出典]対照的に、 と の積は、の先頭のnビット (2 進小数点の後) がゼロである ため、 nビットの精度で計算するだけで済みます。${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}$${\displaystyle X_{i+1}=X_{i}(2-DX_{i})}$${\displaystyle X_{i}}$${\displaystyle (2-DX_{i})}$${\displaystyle X_{i}}$${\displaystyle X_{i}}$${\displaystyle (1-DX_{i})}$${\displaystyle (1-DX_{i})}$

エラーが と定義されている場合、次のようになります。 ${\displaystyle \varepsilon_{i}=1-DX_{i}}$

${\displaystyle {\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}}}$

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

初期推定値を選択するサブ問題では、除数Dにビットシフトを適用して0.5 ≤ D ≤ 1となるようにスケーリング するのが便利です 。同じビットシフトを分子Nに適用することで、商が変化しないことが保証されます。次に、次の形式の 線形近似を使用できます。${\displaystyle X_{0}}$

${\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}$

ニュートン・ラプソンを初期化する。区間 におけるこの近似の誤差の絶対値の最大値を最小化するには、 ${\displaystyle [0.5,1]}$

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

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

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

Remez アルゴリズムを使用して係数を計算し、1 より大きい次数の多項式近似を生成することが可能です。トレードオフは、初期推定により多くの計算サイクルが必要になることですが、その代わりにニュートン・ラプソン法の反復回数が少なくなることが期待されます。

この方法では収束は正確に2次式となるため、

${\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$

ステップは、 2 進数までの値を計算するのに十分です。これは、IEEE単精度の場合は 3、倍精度と倍精度拡張形式の場合は 4と評価されます。 ${\displaystyle P\,}$

以下は、 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 の繰り返し回数と同じ精度で定数を事前計算します
// 固定 P に基づいて事前計算できます ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$    
    X := X + X × (1 - D' × X)
終了
リターンN' × X

たとえば、倍精度浮動小数点除算の場合、この方法では 10 回の乗算、9 回の加算、および 2 回のシフトが使用されます。

ニュートン・ラプソン除算法は、以下のように変更すると少し速くなる。NとDをシフトしてDが[0.5, 1.0]になる ようにし、次のように初期化する。

${\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).}$

これは 1/ Dに最もよく適合する二次関数であり、誤差の絶対値は 1/99 以下になります。誤差が再スケールされた 3 次チェビシェフ多項式と等しくなるように選択されます。係数は事前に計算してハードコードする必要があります。

次に、ループ内で、エラーを 3 乗する反復処理を使用します。

${\displaystyle E:=1-D\cdot X}$

${\displaystyle Y:=X\cdot E}$

${\displaystyle X:=X+Y+Y\cdot E.}$

Y ⋅ E項は新しいものです。

Xが先頭のPビットで1/ Dと一致するまでループを実行すると、反復回数は

${\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil }$

^{これは99を3乗して2 P +1}になる回数です。

${\displaystyle Q:=N\cdot X}$

Pビットの商です。

初期化または反復のいずれかで高次多項式を使用すると、必要な追加の乗算をより多くの反復の実行に費やした方がよいため、パフォーマンスが低下します。

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

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

ゴールドシュミット除算の手順は次のとおりです。

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

N / Dが0 < D  < 1になるようにスケールされていると 仮定すると、各Fi_はDに基づきます。

${\displaystyle F_{i+1}=2-D_{i}.}$

被除数と除数を因数で乗算すると次のようになります。

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

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

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

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

$${\displaystyle {\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ステップ後、分母は次のように丸められる。${\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}$${\displaystyle 1-x^{2^{n}}}$1相対誤差あり

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

これはのときに最大となり、2進数の最小精度が提供されます。 ${\displaystyle 2^{-2^{n}}}$${\displaystyle x={\tfrac {1}{2}}}$${\displaystyle 2^{n}}$

ハードウェア実装用に設計された方法は、一般に、小数点以下が数千または数百万の整数には対応していません。このような状況は、たとえば暗号のモジュラー縮約などで頻繁に発生します。このような大きな整数の場合、より効率的な除算アルゴリズムによって、問題が少数の乗算を使用するように変換されます。この乗算は、 Karatsuba アルゴリズム、Toom-Cook 乗算、Schönhage-Strassen アルゴリズムなどの漸近的に効率的な乗算アルゴリズムを使用して実行できます。その結果、除算の計算量は、乗算の計算量と同じオーダーになります (乗法定数まで)。例としては、前述のニュートン法による乗算への縮約、 ^[18]や、わずかに高速な Burnikel-Ziegler 除算、^[19] Barrett 縮約、およびMontgomery 縮約アルゴリズムなどがあります。^{[20] [検証が必要]}ニュートン法は、同じ除数で何度も除算しなければならないシナリオでは特に効率的です。これは、最初のニュートン逆変換の後、各除算に必要な乗算は1回だけ（切り捨て）であるためです。

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

特に (1/ D )を使用する必要はありません。(1/ D )に簡約される任意の値 ( X / Y )を使用できます。たとえば、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とまったく同じ結果になりますが、近似によって導入された誤差はシフト演算で破棄されるビットにあるほど「十分に近い」ものです。^{[21] [22] [23]}バレット減算では、 Yの値に 2 の累乗を使用して、 Yによる除算を単純な右シフトにします。^[b]

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

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

${\displaystyle \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 }$

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

除算演算を実行すると、正確な商 と余りがコンピュータの精度の制限内に収まるように近似されます。除算アルゴリズムは次のように定義されます。 ${\displaystyle q}$ ${\displaystyle r}$

${\displaystyle [a=bq+r]}$

どこ。 ${\displaystyle 0\leq r<|b|}$

浮動小数点演算では、商は 、剰余はと表され、丸め誤差と が発生します。 ${\displaystyle q}$${\displaystyle {\tilde {q}}}$${\displaystyle r}$${\displaystyle {\tilde {r}}}$ ${\displaystyle \epsilon _{q}}$${\displaystyle \epsilon _{q}}$${\displaystyle \epsilon _{r}}$

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

この丸めにより小さな誤差が生じ、それが後続の計算を通じて伝播し蓄積される可能性がある。このような誤差は反復処理で特に顕著であり、ほぼ等しい値を減算する場合に有意性が失われると言われる。これらの誤差を軽減するために、ガード桁の使用や高精度の演算などの技術が採用されている。^{[28] [29]}

• ギャレー部門
• 乗算アルゴリズム
• Pentium FDIV のバグ

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