假设我要计算以下内容:
A/Z
其中A
长度为 128 位,长度Z
为 64 位。A
存储在 2 个 64 位寄存器中,因为系统的寄存器最多可以存储 64 位。计算结果的有效方法是什么?
PS:我已经通过使用 CSD 表示解决了类似的乘法问题。但是,这需要1/Z
先计算。
假设我要计算以下内容:
A/Z
其中A
长度为 128 位,长度Z
为 64 位。A
存储在 2 个 64 位寄存器中,因为系统的寄存器最多可以存储 64 位。计算结果的有效方法是什么?
PS:我已经通过使用 CSD 表示解决了类似的乘法问题。但是,这需要1/Z
先计算。
[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)迭代。但是,我的直觉告诉我,应该使用一些我现在不知道或想不到的模块化数学身份来更简单地计算它。这使得这种划分相对缓慢。
解决此类问题的正确方法是回归基础:
Q
和余数R
R
,并将结果添加到临时寄存器。除法之后,所得的余数必须转换为double
,除以分母,然后加到商。