非回復型除算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/26 11:07 UTC 版)
非回復型（または非復元型）除算 (non-restoring division) は商の桁の数字として {0,1} ではなく {−1,1} を使用する。引きっ放し法ともいう。二進（基数2）の基本的アルゴリズムは次の通り。 procedure divide_non_restoring(N, D: integer_n_bits; var q: array_n_of_pm1);const n = 32;var i: integer; P: integer_n_bits;begin P := N; for i := 0 to n - 1 do begin if P >= 0 then begin q[(n - 1) - i] := 1; P := 2 * P - D; end else begin q[(n - 1) - i] := -1; P := 2 * P + D; end; end;end; このアルゴリズムで得られる商は、各桁が −1 と +1 であり、通常の形式ではない。そこで通常の二進形式への変換が必要である。例えば、次のようになる。 次の結果を {0,1} の通常の二進形式に変換する : Q = 111 1 ¯ 1 1 ¯ 1 1 ¯ {\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}} ステップ: 1. 負の項のマスクを作る: N = 00010101 {\displaystyle N=00010101\,} 2. Nの2の補数を作る: N ¯ = 11101011 {\displaystyle {\bar {N}}=11101011} 3. 正の項のマスクを作る: P = 11101010 {\displaystyle P=11101010\,} 4. P {\displaystyle P\,} と N ¯ {\displaystyle {\bar {N}}} の総和: Q = 11010101 {\displaystyle Q=11010101\,} ここで、 N ¯ = n e g ( n o t ( P ) ) = P + 1 {\displaystyle {\bar {N}}={\rm {{neg}({\rm {{not}(P))=P+1}}}}} が成り立つことに注意すると、以下のように修正できる。 procedure divide_non_restoring(N, D: integer_n_bits; var Q: integer_n_bits);const n = 32;var i: integer; P: integer_n_bits;begin Q := 0; P := N; for i := 0 to n - 1 do begin if P >= 0 then begin Q := Q + (1 shl ((n - 1) - i)); P := 2 * P - D; end else P := 2 * P + D; end; Q := 2 * Q + 1; if P < 0 then Q := Q - 1; (* 引き過ぎている場合、戻す *)end;
※この「非回復型除算」の解説は、「除算 (デジタル)」の解説の一部です。
「非回復型除算」を含む「除算 (デジタル)」の記事については、「除算 (デジタル)」の概要を参照ください。
- 非回復型除算のページへのリンク
