2

假设我要计算以下内容：

A/Z

其中A长度为 128 位，长度Z为 64 位。A存储在 2 个 64 位寄存器中，因为系统的寄存器最多可以存储 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

所以 i0 只是在 z0 是 2 的幂的情况下增加，而 i1 只是从除法中计算出的余数。

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

这里测试了 8bit 代码：

//---------------------------------------------------------------------------
// 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 位除法（虽然结果不是完全的，但不是任意的，而是两个mod z0值的组合）。我设法避免了长除数（对于 16 位：8 位是最坏的情况 7）迭代。但是，我的直觉告诉我，应该使用一些我现在不知道或想不到的模块化数学身份来更简单地计算它。这使得这种划分相对缓慢。

于 2013-10-15T12:17:37.367 回答
0

解决此类问题的正确方法是回归基础：

  • 将最重要的寄存器除以分母
  • 计算商Q和余数R
  • 定义一个新的临时寄存器，最好与其他两个相同的长度
  • 其余的应该占据临时寄存器中的最高有效位
  • 将较低有效寄存器向右移动包含 i 的相同数量的位R ，并将结果添加到临时寄存器。
  • 返回第 1 步

除法之后，所得的余数必须转换为double，除以分母，然后加到商。

于 2013-10-18T11:05:21.953 回答