符号つき除算(非回復法)

[←]　[↑]　[→]

---

分子と分母が符号つき整数の場合の除算は符号つき除算(非回復法)に書いたとおりで、これを固定小数点に直したものは次のとおり。余りは切捨でなく丸め(四捨五入)とする。

a / d = q + e (d>0)  a / d = q - e (d<0)

分子a：符号つき、整数部IAビット、小数部FAビット (-2^IA-1≦a≦2^IA-1-2^-FA)

分母d：符号つき、整数部IDビット、小数部FDビット (d≠0,-2^ID-1≦d≦2^ID-1-2^-FD)

商q：　符号つき、整数部IQビット、小数部FQビット (-2^IQ-1≦q≦2^IQ-1-2^-FQ)

　　　　(1) a,dが任意の値をとりうる場合

　　　　　a/d≦(-2^IA-1)/(-2^-FD)=2^IA-1+FDだから整数部はIQ=IA+FD+1だけ必要

　　　　　小数部はFQ≧FA-FD

　　　　(2) -2^IQ-1≦a/d≦2^IQ-1-2^-FQとわかっている場合はビット幅IQ<IA+FD+1で十分

　　　　　例) N個の値x_i の平均値はx_iの値の範囲内に必ず収まる

誤差e：丸めの場合 -2^-FQ-1≦e＜2^-FQ-1

VitisHLSで合成可能なCコードは

#include <ap_int.h>

/*********************************************************

 * division: a/d = q + e (d>0) , a/d = q - e (d<0)

 *   param range: IQ<=IA+FD+1 FQ>=FA-FD

 *   input range: d!=0,-2**(IQ-1)<=a/d<=2**(IQ-1)-2**(-FQ)

 *   error range: -2**(-FQ-1)<=e<2**(-FQ-1) (rounding)

 ********************************************************/

template <int IA,int FA,int ID,int FD,int IQ,int FQ>

ap_fixed<IQ+FQ,IQ> div_fixed // (o) quotient

  (ap_fixed<IA+FA,IA> a // (i) dividend

  ,ap_fixed<ID+FD,ID> d // (i) divisor

  ) {

  ap_int<IA+FD+FQ+1> a_tmp

     = (ap_int<IA+FD+FQ+1>) a(IA+FA-1,0)<<(FQ-FA+FD+1);

  ap_int<ID+FD+1> d_tmp = (ap_int<ID+FD>) d(ID+FD-1,0);

  ap_int<ID+FD+1> r;

  ap_int<ID+FD+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+FD-IQ+2>) a_tmp(IA+FD+FQ,i); // sign-ext

    } else {

      r = (t(ID+FD-1,0),a_tmp[i]);

    }

    p[i] = (r[ID+FD]==d_tmp[ID+FD]);

    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+FD]==d_tmp[ID+FD]);

  return q;

}

このコードは次のテストベンチで検証してある。

int main(int argc, char *argv[]) {

  const int IA=3,FA=1;

  const int ID=2,FD=2;

#ifdef FULL_IQ

  const int IQ=6,FQ=3;  // IQ=IA+FD+1 FQ>=FA-FD

#else

  const int IQ=4,FQ=3;  // IQ<IA+FD+1 FQ>=FA-FD

#endif

  ap_fixed<IA+FA,IA> a;

  ap_fixed<ID+FD,ID> d;

  ap_fixed<IQ+FQ,IQ> q;

  double a_val,d_val,q_val,e_val;

  printf("-- IA=%-d FA=%-d ID=%-d FD=%-d IQ=%-d FQ=%-d\n",IA,FA,ID,FD,IQ,FQ);

/* a,dを全範囲振って商と誤差を表示する */

  for(int j=-pow(2,ID+FD-1); j<pow(2,ID+FD-1); j++) {

    if(j==0) continue;

    for(int i=-pow(2,IA+FA-1); i<pow(2,IA+FA-1); i++) {

      a = (float) i * pow(2,-FA);

      d = (float) j * pow(2,-FD);

      a_val = a.to_double();

      d_val = d.to_double();

      printf("-- a=%+f d=%+f",a_val,d_val);

      d_abs = (d_val<0)? (-d_val):(d_val);

/* IQ<IA+FD+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_fixed<IA,FA,ID,FD,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=%+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;

}

---

[←]　[↑]　[→]