符号つき除算(非回復法)
前項の回復法では引きすぎたら引く前の値に戻したが、戻さずに次の桁で足しても同じ結果になる(例えば-1/8=-1/2+1/4+1/8)。この方法は引き放し法、非回復法、Non-Restoring法とよばれる。
非回復法では、商はビットごとに0,1でなく+1,-1で得られるので、次の手順で0,1に直せばよい。
|
+1のビットをp[N-1:0]とおくと、-1のビットは~p[N-1:0]だから q[N:0] = p[N-1:0]-(~p[N-1:0]) = p[N-1:0]+{1,p[N-1:0]}+1 = (1<<N)+{p[N-1:0],1} 例) q=(+1)*22+(-1)*21+(-1)*20 =1のときp[2:0]=100 ∴q[3:0]=1000+{100,1}=0001 |
前項の回復法の例を非回復法で手計算すると次のようになる。
|
【非回復法】 符号なし/符号なし |
説明 |
|
例）a[2:0]=101=(5) d[1:0]=11=(3) _______ 11)00101.0 r={00,a[2]} q[2]=+1 -) 11 d --- 110 t=r-d <0 100 r={r[1:0],a[1]} q[1]=-1 +) 11 d --- 111 t=r+d <0 111 r={r[1:0],a[0]} q[0]=-1 +) 11 d --- 010 t=r+d >=0 10.0 r={t[1:0],0} q[-1]=+1 -) 1.1 d ----- 00.1 t=r-d >=0
切捨の場合q[2:0]=+4-2-1=1 丸めの場合q[2:-1]=+4-2-1+0.5=1.5→2 |
←引き算はq[IA-1](aのMSB)から始める ←負だったらq[i]=-1として分母を足す 非負だったらq[i]=+1として分母を引く if(r<0) q[i]=-1 t=r+d else q[i]=+1 t=r-d 符号を判定するためt,rのビット幅は[ID:0]だけ必要
←切捨(0<=e<1)の場合はq[0]まで求めて終わり +1のビットをp[i]とおくとq[3:0]=1000+{p[2:0],1} t<0(引きすぎ)のときはq=q-1にすればよいので if(t<0) q[3:0]=1000+{p[2:0],0} else q[3:0]=1000+{p[2:0],1} ←-丸め(-0.5<=e<0.5)の場合はq[-1]まで求めて if(t<0) q[3:-1]=10000+{p[2:-1],0} else q[3:-1]=10000+{p[2:-1],1} さらにq[3:0]=q[3:0]+q[-1]とするので if(t<0) q[3:0]=1000+p[2:-1] else q[3:0]=1000+p[2:-1]+1 |
◇
回復法は減算だけ使うのに対して、非回復法は加減算両用の組合せ回路を使うので動作速度が遅くなりそうだが、正÷正だけでなく正÷負なども同じ回路で扱える利点がある。そこで、符号つき整数の除算を考える。
|
a / d = q + e (d>0) a / d = q - e (d<0) 分子a：符号つき、整数部IAビット 分母d：符号つき、整数部IDビット 商q： 符号つき、整数部IQビット、小数部FQビット (1) a,dが任意の値をとりうる場合は-2IA-1/1≦a/d≦(-2IA-1)/(-1)だからIQ=IA+1だけ必要 (2) -2IQ-1≦a/d≦2IQ-1-2-FQとわかっている場合はビット幅IQ<IA+1で十分 例) N個の値xi の平均値はxiの値の範囲内に必ず収まる 誤差e：(1) 切捨の場合 0 ≦e＜2-FQ ただしIQ<IA+1のときa=2IQ-1,d=-1だけe=2-FQになる (2) 丸めの場合 -2-FQ-1≦e＜2-FQ-1 |
手順は、分子と分母が同符号ならば引いて異符号なら足していけばよい。
簡単な例としてIA=3,ID=2,IQ=IA+1=4,FQ=0の場合で手計算すると次のようになる。(負/負や余り0の例は→補足)
|
【非回復法】 正/負 |
説明 |
|
例）a[2:0]=010=( 2) d[1:0]=11=(-1) _______ 11)00010.0 r=符号拡張a[2]>=0 q[2]=-1 +)111 符号拡張d --- 111 t=r+d <0 111 r={t[1:0],a[1]} q[1]=+1 -)111 符号拡張d --- 000 t=r-d >=0 000 r={t[1:0],a[0]} q[0]=-1 +)111 符号拡張d --- 111 t=r+d <0 11.0 r={t[1:0],0} q[-1]=+1 -)11.1 符号拡張d ---- 11.1 t=r-d
切捨の場合q=-4+2-1=-3(余り-1)→-2 丸めの場合q=-4+2-1+0.5=-2.5(余り-0.5)→-2 |
←引き算はq[IA-1](aのMSB)から始める ←異符号だったらq[i]=-1にして分母を足す 同符号だったらq[i]=+1にして分母を引く if(rとdが異符号) q[i]=-1 t=r+d else q[i]=+1 t=r-d 符号を判定するためt,rのビット幅は[ID:0]だけ必要
←切捨(0<=e<1)の場合はq[0]まで求めて終わり +1のビットをp[i]とおくとq[3:0]=1000+{p[2:0],1} t<0(引きすぎ)のときは、d>0ならばq=q-1, d<0ならばq=q+1とすればよいので if(t<0) q[3:0]=1000+{p[2:0],0}+(d<0)?10:0 else q[3:0]=1000+{p[2:0],1} ←丸め(-0.5<=e<0.5)の場合はq[-1]まで求めて if(t<0) q[3:-1]=10000+{p[2:-1],0}+(d<0)?10:0 else q[3:-1]=10000+{p[2:-1],1} d>=0ならばq[3:0]=q[3:0]+q[-1](切上げ), d<0ならばq[3:0]=q[3:0](切捨て)とすればよいので if(t<0) q[3:0]=1000+p[2:-1]+(d<0)? 1:0 else q[3:0]=1000+p[2:-1]+(d<0)? 0:1 |
ここで引き算の始まりをqのMSB q[IQ-1]=q[IA]ではなくq[IQ-2]=q[IA-1]にしているのは、非回復法ではp[IQ-2:0]からq[IQ-1:0]が求まるからである。
◇◇
このアルゴリズムをVitisHLSで合成可能なCコードで書くと次のようになる。ここで商qを小数点以下まで求めるためにa*2FQ/d=qとaを左シフトしている。
|
#include <ap_int.h> /********************************************************** * division: a/d = q + e (d>0) , a/d = q - e (d<0) * param range: IQ<=IA+1 * input range: d!=0,-2**(IQ-1)<=a/d<=2**(IQ-1)-2**(-FQ) * error range: 0<=e<2**(-FQ) (truncation) * ただしIQ<IA+1のときa=2**(IQ-1),d=-1だけe=2**(-FQ)になる *********************************************************/ template <int IA,int ID,int IQ,int FQ> ap_fixed<IQ+FQ,IQ> div_int_trn // (o) quotient (ap_int<IA> a // (i) dividend ,ap_int<ID> d // (i) divisor ) { ap_int<IA+FQ> a_tmp = (ap_int<IA+FQ>) a(IA-1,0)<<FQ; ap_int<ID+1> d_tmp = (ap_int<ID>) d(ID-1,0); ap_int<ID+1> r; ap_int<ID+1> t; ap_uint<IQ+FQ> p; ap_fixed<IQ+FQ,IQ> q; for(int i=IQ+FQ-2; i>=0; i--) { if(i==IQ+FQ-2) { r =(ap_int<IA-IQ+2>) a_tmp(IA+FQ-1,i); //sign-extension } else { r = (t(ID-1,0),a_tmp[i]); } p[i] = (r[ID]==d_tmp[ID]); t = (p[i])? (r - d_tmp):(r + d_tmp); } q(IQ+FQ-1,0) = ((ap_uint<IQ+FQ>) 1<<(IQ+FQ-1)) +(p,!t[ID])+((t[ID] & d_tmp[ID])?2:0); return q; } |
|
#include <ap_int.h> /********************************************************** * division: a/d = q + e (d>0) , a/d = q - e (d<0) * param range: IQ<=IA+1 * input range: d!=0, -2**(IQ-2)<=a/d<=2**(IQ-2) * error range: -2**(-FQ-1)<=e<2**(-FQ-1) (rounding) *********************************************************/ template <int IA,int ID,int IQ,int FQ> ap_fixed<IQ+FQ,IQ> div_int_rnd // (o) quotient (ap_int<IA> a // (i) dividend ,ap_int<ID> d // (i) divisor ) { ap_int<IA+FQ+1> a_tmp=(ap_int<IA+FQ+1>)a(IA-1,0)<<(FQ+1); ap_int<ID+1> d_tmp = (ap_int<ID>) d(ID-1,0); ap_int<ID+1> r; ap_int<ID+1> t; ap_uint<IQ+FQ> p; ap_fixed<IQ+FQ,IQ> q; for(int i=IQ+FQ-1; i>=0; i--) { if(i==IQ+FQ-1) { r = (ap_int<IA-IQ+2>) a_tmp(IA+FQ,i); //sign-extension } else { r = (t(ID-1,0),a_tmp[i]); } p[i] = (r[ID]==d_tmp[ID]); t = (p[i])? (r - d_tmp):(r + d_tmp); } q(IQ+FQ-1,0) = ((ap_uint<IQ+FQ>) 1<<(IQ+FQ-1)) + p + (t[ID]==d_tmp[ID]); return q; } |
このコードは次のテストベンチで検証してある。
(注意) テストベンチを実行するとわかるが、切捨の場合はIQ<IA+1のときa=2IQ-1,d=-1だけe=2-FQになる。例えばIA=3,IQ=2,FQ=0のとき010/(-1)=11+1すなわち2/(-1)=-3+1となる。一方、丸めの場合はもう1桁下まで計算するので2/(-1)=-2+0と正しい結果になる。
|
int main(int argc, char *argv[]) { const int IA=3; const int ID=3; #ifdef FULL_IQ const int IQ=4,FQ=1; // IQ=IA+1 #else const int IQ=2,FQ=1; // IQ<IA+1 #endif ap_int<IA> a; ap_int<ID> d; ap_fixed<IA+FQ+1,IA+1> q; double a_val,d_val,q_val,e_val; printf("-- IA=%-d ID=%-d IQ=%-d FQ=%-d\n",IA,ID,IQ,FQ); /* a,dを全範囲振って商と誤差を表示する */ for(int j=-pow(2,ID-1); j<pow(2,ID-1); j++) { if(j==0) continue; for(int i=-pow(2,IA-1); i<pow(2,IA-1); i++) { a = i; d = j; a_val = a.to_double(); d_val = d.to_double(); printf("-- a=%+f d=%+f",a_val,d_val); /* IQ<IA+1のとき大きいaはスキップする */ if( ((d_val>0)&&(-pow(2,IQ-1)*d_val<=a_val)&&(a_val<=(pow(2,IQ-1)-pow(2,-FQ))*d_val)) ||((d_val<0)&&(-pow(2,IQ-1)*d_val>=a_val)&&(a_val>=(pow(2,IQ-1)-pow(2,-FQ))*d_val)) ) { /* 切捨の場合 */ q = div_int_trn<IA,ID,IQ,FQ>(a,d); q_val = q.to_double(); e_val = a_val/d_val - q_val; if(d_val<0) e_val = -e_val; printf(" q_trn=%+f e=%+f",q_val,e_val); if(!(0<=e_val && e_val<pow(2,-FQ))) printf(" [FAIL]"); /* 丸めの場合 */ q = div_int_rnd<IA,ID,IQ,FQ>(a,d); q_val = q.to_double(); e_val = a_val/d_val - q_val; if(d_val<0) e_val = -e_val; printf(" q_rnd=%+f e=%+f",q_val,e_val); if(!(-pow(2,-FQ-1)<=e_val && e_val<pow(2,-FQ-1))) printf(" [FAIL]"); } printf("\n"); } } return 0; } |
◇◇◇
(補足) IA=3,ID=2,IQ=IA+1=4,FQ=0の場合の計算例
|
【非回復法】 負/負 |
【非回復法】 負/負 余り０ |
|
例）a[2:0]=100=(-4) d[1:0]=11=(-1) _______ 11)11100.0 r=符号拡張a[2]<0 q[2]=+1 -)111 d --- 000 t=r-d >=0 000 r={t[1:0],a[1]} q[1]=-1 +)111 符号拡張d --- 111 t=r+d <0 110 r={t[1:0],a[0]} q[0]=+1 -)111 符号拡張d --- 111 t=r-d <0 11.0 r={t[1:0],0} q[-1]=+1 -)11.1 符号拡張d --- 11.1 t=r-d
切捨の場合q=+4-2+1=3(余り-1)→4 丸めの場合q=+4-2+1+0.5=3.5(余り-0.5)→4 |
例）a[2:0]=101=(-3) d[1:0]=11=(-1) _______ 11)11101.0 r=符号拡張a[2]<0 q[2]=+1 -)111 d --- 000 t=r-d >=0 000 r={t[1:0],a[1]} q[1]=-1 +)111 符号拡張d --- 111 t=r+d <0 111 r={t[1:0],a[0]} q[0]=+1 -)111 符号拡張d --- 000 t=r-d >=0 00.0 r={t[1:0],0} q[-1]=-1 +)11.1 符号拡張d --- 11.1 t=r+d
切捨の場合q=+4-2+1=3(余り0) 丸めの場合q=+4-2+1-0.5=2.5(余り-0.5)→3 |
|
【非回復法】 正/負 |
【非回復法】 正/負 余り０ |
|
例）a[2:0]=010=( 2) d[1:0]=11=(-1) _______ 11)00010.0 r=符号拡張a[2]>=0 q[2]=-1 +)111 d --- 111 t=r+d <0 111 r={t[1:0],a[1]} q[1]=+1 -)111 符号拡張d --- 000 t=r-d >=0 000 r={t[1:0],a[0]} q[0]=-1 +)111 符号拡張d --- 111 t=r+d <0 11.0 r={t[1:0],0} q[-1]=+1 -)11.1 符号拡張d ---- 11.1 t=r-d
切捨の場合q=-4+2-1=-3(余り-1)→-2 丸めの場合q=-4+2-1+0.5=-2.5(余り-0.5)→-2 |
例）a[2:0]=011=( 3) d[1:0]=11=(-1) _______ 11)00011.0 r=符号拡張a[2]>=0 q[2]=-1 +)111 d --- 111 t=r+d <0 111 r={t[1:0],a[1]} q[1]=+1 -)111 符号拡張d --- 000 t=r-d >=0 001 r={t[1:0],a[0]} q[0]=-1 +)111 符号拡張d --- 000 t=r+d >=0 00.0 r={t[1:0],0} q[-1]=-1 +)11.1 符号拡張d ---- 11.1 t=r+d
切捨の場合q=-4+2-1=-3(余り0) 丸めの場合q=-4+2-1-0.5=-3.5(余り-0.5)→-3 |