8

ハードウェアに 32 ビット浮動小数点ハードウェア除算器を実装しようとしていますが、異なるアルゴリズム間のトレードオフについて何か提案が得られるかどうか疑問に思っています。

私の浮動小数点ユニットは現在、乗算と加算/減算をサポートしていますが、これを融合型乗加算 (FMA) 浮動小数点アーキテクチャに切り替えるつもりはありません。これは、領域の使用を最小限に抑えようとしている組み込みプラットフォームだからです。

4

1 に答える 1

4

むかしむかし、当時の軍用FPUで使用されていた、このきちんとした実装が簡単な浮動小数点/固定小数点除算アルゴリズムに出くわしました。

  1. 入力は符号なしでシフトする必要がありx < y、両方が範囲内にある< 0.5 ; 1 >

    sh = shx - shyシフトと元のサインの違いを保存することを忘れないでください

  2. find f(反復による) so y*f -> 1.... その後 x*f -> x/yの除算結果

  3. x*f後ろにシフトしてsh結果の符号を復元する(sig=sigx*sigy)

    これは、次のx*fように簡単に計算できます。

    z=1-y
(x*f)=(x/y)=x*(1+z)*(1+z^2)*(1+z^4)*(1+z^8)*(1+z^16)...(1+z^2n)

    どこ

    n = log2(num of fractional bits for fixed point, or mantisa bit size for floating point)

    z^2n固定ビット幅のデータ型でゼロになったときに停止することもできます。

[編集 2] 少し時間があったので、ここで 32 ビット IEEE 754 C++ 実装

将来の読者の混乱を避けるために、古い (bignum) 例を削除しました (必要に応じて、編集履歴から引き続きアクセスできます)。

//---------------------------------------------------------------------------
// IEEE 754 single masks
const DWORD _f32_sig    =0x80000000;    // sign
const DWORD _f32_exp    =0x7F800000;    // exponent
const DWORD _f32_exp_sig=0x40000000;    // exponent sign
const DWORD _f32_exp_bia=0x3F800000;    // exponent bias
const DWORD _f32_exp_lsb=0x00800000;    // exponent LSB
const DWORD _f32_exp_pos=        23;    // exponent LSB bit position
const DWORD _f32_man    =0x007FFFFF;    // mantisa
const DWORD _f32_man_msb=0x00400000;    // mantisa MSB
const DWORD _f32_man_bits=       23;    // mantisa bits
//---------------------------------------------------------------------------
float f32_div(float x,float y)
    {
    union _f32          // float bits access
        {
        float f;        // 32bit floating point
        DWORD u;        // 32 bit uint
        };
    _f32 xx,yy,zz; int sh; DWORD zsig; float z;
    //      result signum        abs value
    xx.f=x; zsig =xx.u&_f32_sig; xx.u&=(0xFFFFFFFF^_f32_sig);
    yy.f=y; zsig^=yy.u&_f32_sig; yy.u&=(0xFFFFFFFF^_f32_sig);
    // initial exponent difference sh and normalize exponents to speed up shift in range
    sh =0;
    sh-=((xx.u&_f32_exp)>>_f32_exp_pos)-(_f32_exp_bia>>_f32_exp_pos); xx.u&=(0xFFFFFFFF^_f32_exp); xx.u|=_f32_exp_bia;
    sh+=((yy.u&_f32_exp)>>_f32_exp_pos)-(_f32_exp_bia>>_f32_exp_pos); yy.u&=(0xFFFFFFFF^_f32_exp); yy.u|=_f32_exp_bia;
    // shift input in range
    while (xx.f> 1.0f) { xx.f*=0.5f; sh--; }
    while (xx.f< 0.5f) { xx.f*=2.0f; sh++; }
    while (yy.f> 1.0f) { yy.f*=0.5f; sh++; }
    while (yy.f< 0.5f) { yy.f*=2.0f; sh--; }
    while (xx.f<=yy.f) { yy.f*=0.5f; sh++; }
    // divider block
    z=(1.0f-yy.f);
    zz.f=xx.f*(1.0f+z);
    for (;;)
        {
        z*=z; if (z==0.0f) break;
        zz.f*=(1.0f+z);
        }
    // shift result back
    for (;sh>0;) { sh--; zz.f*=0.5f; }
    for (;sh<0;) { sh++; zz.f*=2.0f; }
    // set signum
    zz.u&=(0xFFFFFFFF^_f32_sig);
    zz.u|=zsig;
    return zz.f;
    }
//---------------------------------------------------------------------------

シンプルにしたかったので、まだ最適化されていません。たとえば、all*=0.5と*=2.0by exponentを置き換えることができinc/decます...float演算子で FPU の結果と比較すると/、ほとんどの FPU は 80 ビットの内部形式で計算し、この実装は 32 ビットでのみ実行されるため、これは少し正確ではありません。

ご覧のとおり、私は FPU から使用してい+,-,*ます。次のような高速 sqr アルゴリズムを使用することで、処理を高速化できます。

特に大きなビット幅を使用したい場合...

正規化やオーバーフロー/アンダーフローの修正を実装することを忘れないでください。

于 2013-08-23T08:27:49.957 に答える