2

次の計算をしたいとしましょう。

A/Z

長Aさは 128 ビットで、長さZは 64 ビットです。Aシステムのレジスタは最大 64 ビットを格納できるため、2 つの 64 ビット レジスタに格納されます。結果を計算する効率的な方法は何でしょうか?

PS: CSD 表現を使用して、同様の乗算の問題を解決しました。1/Zただし、これには最初 に計算が必要です。

4

2 に答える 2

0

[Edit1] 発見されたバグが修正されました

整数除算が必要だと思いますので、8ビットのアナロジーの計算は次のとおりです。

A = { a0 + (a1<<8) }
D = { d0 + (d1<<8) } ... division result
Z = { z0 }
D = (a0/z0) + ((a1*256)/z0) +                      (( (a0%z0) + ((a1*256)%z0) )/z0);
D = (a0/z0) + ((a1/z0)*256) + ((a1%z0)*(256/z0)) + (( (a0%z0) + ((a1%z0)*(256%z0)) )/z0);

項256/z0とは次の256%z0ように計算できます (C++):

    i0=0xFF/z0; if ((z0&(z0-1))==0) i0++;   // i0 = 256/z0
    i1=i0*z0; i1^=0xFF; i1++;               // i1 = 256%z0

したがって、z0 が 2 の累乗である場合、i0 は単にインクリメントされ、i1 は除算から計算された余りになります。

    a/b = d + r/b
    r = a - a*d

ここでテストされた8ビットコード：

//---------------------------------------------------------------------------
// unsigned 8 bit ALU in C++
//---------------------------------------------------------------------------
BYTE cy;                                                    // carry flag cy = { 0,1 }
void inc(BYTE &a);                                          // a++
void dec(BYTE &a);                                          // a--
void add(BYTE &c,BYTE a,BYTE b);                            // c = a+b
void adc(BYTE &c,BYTE a,BYTE b);                            // c = a+b+cy
void sub(BYTE &c,BYTE a,BYTE b);                            // c = a-b
void sbc(BYTE &c,BYTE a,BYTE b);                            // c = a-b-cy
void mul(BYTE &h,BYTE &l,BYTE a,BYTE b);                    // (h,l) = a/b
void div(BYTE &h,BYTE &l,BYTE &r,BYTE ah,BYTE al,BYTE b);   // (h,l) = (ah,al)/b ; r = (ah,al)%b
//---------------------------------------------------------------------------
void inc(BYTE &a) { if (a==0xFF) cy=1; else cy=0; a++; }
void dec(BYTE &a) { if (a==0x00) cy=1; else cy=0; a--; }
void add(BYTE &c,BYTE a,BYTE b)
    {
    c=a+b;
    cy=BYTE(((a &1)+(b &1)   )>>1);
    cy=BYTE(((a>>1)+(b>>1)+cy)>>7);
    }
void adc(BYTE &c,BYTE a,BYTE b)
    {
    c=a+b+cy;
    cy=BYTE(((a &1)+(b &1)+cy)>>1);
    cy=BYTE(((a>>1)+(b>>1)+cy)>>7);
    }
void sub(BYTE &c,BYTE a,BYTE b)
    {
    c=a-b;
    if (a<b) cy=1; else cy=0;
    }
void sbc(BYTE &c,BYTE a,BYTE b)
    {
    c=a-b-cy;
    if (cy) { if (a<=b) cy=1; else cy=0; }
    else    { if (a< b) cy=1; else cy=0; }
    }
void mul(BYTE &h,BYTE &l,BYTE a,BYTE b)
    {
    BYTE ah,al;
    h=0; l=0; ah=0; al=a;
    if ((a==0)||(b==0)) return;
    // long binary multiplication
    for (;b;b>>=1)
        {
        if (BYTE(b&1))
            {
            add(l,l,al);    // (h,l)+=(ah,al)
            adc(h,h,ah);
            }
        add(al,al,al);      // (ah,al)<<=1
        adc(ah,ah,ah);
        }
    }
void div(BYTE &d1,BYTE &d0,BYTE &r,BYTE a1,BYTE a0,BYTE z0)
    {
    //      D = (a0/z0) + ((a1*256)/z0) +                      (( (a0%z0) + ((a1*256)%z0) )/z0);
    //      D = (a0/z0) + ((a1/z0)*256) + ((a1%z0)*(256/z0)) + (( (a0%z0) + ((a1%z0)*(256%z0)) )/z0);
    // edge cases
    if (z0==0){ d0= 0; d1= 0; r=0; }
    if (z0==1){ d0=a0; d1=a1; r=0; }
    // normal division
    if (z0>=2)
        {
        BYTE i0,i1,e0,e1,f0,f1,t,dt;
        i0=0xFF/z0; if ((z0&(z0-1))==0) i0++;   // i0 = 256/z0
        i1=i0*z0; i1^=0xFF; i1++;               // i1 = 256%z0
        t=a1%z0;
        mul(e1,e0,t,i0);                        // e = (a1%z0)*(256/z0)
        mul(f1,f0,t,i1);                        // f = (a1%z0)*(256%z0)
        add(f0,f0,a0%z0);                       // f = (a0%z0) + (a1%z0)*(256%z0)
        adc(f1,f1,0);
        add(d0,a0/z0,e0);
        adc(d1,a1/z0,e1);
        // t = division of problematic term by z0
        t=0;
        for (;f1;)
            {
            dt=f1*i0;
            mul(e1,e0,dt,z0);
            sub(f0,f0,e0);
            sbc(f1,f1,e1);
            t+=dt;
            }
        if (f0>=z0) t+=f0/z0;
        // correct output
        add(d0,d0,t);
        adc(d1,d1,0);
        // remainder
        r=d0*z0;
        r=a0-r;
        }
    }
//---------------------------------------------------------------------------

8ビットALUはまったく最適化されていません。元のプロジェクトがどこにも見つからないため、今すぐテストするためにバストしました... asmで実行していると仮定して、代わりにCPU / ALU命令キャリーを使用できます。唯一の重要な機能はdiv.

ノート：

これは 8 ビットのみです。それを 64 ビットに変換するには、すべて 0xFFを0xFFFFFFFFFFFFFFFFとBYTEに変更し、データ型を に<<8変更します<<64。

除算結果は 、d0剰余d1は 内r コードでは負の値を扱いません。

悲しいことに、用語：

(( (a0%z0) + ((a1%z0)*(256%z0)) )/z0);

現在の状態では、16 ビットの除算も必要です (完全ではありませんが、結果は任意ではなく、2 つのmod z0値の合成になります)。数回の繰り返しによる長い除算をなんとか回避できました（16ビット：8ビットは最悪の場合7回です）。しかし、私の内臓は、私が知らない、または今は考えられないモジュラー数学のアイデンティティを使用して、より簡単に計算する必要があると言っています。これにより、この分割は比較的遅くなります。

于 2013-10-15T12:17:37.367 に答える
0

このような問題を解決する正しい方法は、基本に戻ることです。

  • 最上位レジスタを分母で割る
  • 商Qと残りを計算するR
  • できれば他の 2 つと同じ長さの新しい一時レジスタを定義する
  • 残りは一時レジスタの最上位ビットを占有する必要があります
  • 下位レジスタを i に含まれるビットと同じ量だけ右にシフトしR 、その結果を一時レジスタに追加します。
  • ステップ1に戻る

除算後、結果の残りを にキャストしdouble、分母で除算して商に加算する必要があります。

于 2013-10-18T11:05:21.953 に答える