回復型除算

ウィキペディア小見出し辞書

回復型除算

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/26 11:07 UTC 版)

「除算 (デジタル)」の記事における「回復型除算」の解説

回復型（または復元型）除算 (restoring division) を固定小数点数に対して行う場合を解説する。ここで以下を前提とする。 0 ≤ N 0 < D < 1. 商の各桁 q は数字の集合 {0,1} のいずれかである。 二進（基数2）の基本的アルゴリズムは次の通り。 procedure divide_restoring(N: integer_n_bits; D: integer_2n_bits; var Q: integer_n_bits);const n = 32;var i : integer; P : integer_2n_bits;begin (* 商をゼロで初期化 *) Q := 0; (* P と D は N や Q の倍の幅が必要 *) P := N; D := D shl n; for i := n - 1 downto 0 do begin P := 2 * P - D; (* シフトした値から減算を試みる *) if P >= 0 then Q := Q + (1 shl i); (* 結果ビットは 1 *) else P := P + D; (* 新たな部分的剰余は（回復した）シフトした値 *) end;end; なお、q(i) は商のi番目のビットを意味する。このアルゴリズムでは減算の前にシフトした値 2P をセーブしておいて、回復（復元）させるステップが必要だが、これはレジスタ T を例えば T = P << 1 としておいて、減算 2P − D の結果が負だった場合にレジスタ T を P にコピーすればよい。 不実行回復型除算は回復型除算とよく似ているが、2*P[i] の値をセーブしておく点が異なり、TP[i] ≤ 0 の場合でも D を加算して戻してやる必要がない。