Не могу сделать ценность распространяться через нести
Создание небольшого класса C++ большой точности, и все, кажется, работает достойно, но добавьте, если я добавлю 0xffffffff и 0x04 вместе, я получу 0xffff0003, когда я должен получить 0x0100000003. Вот функция с проблемой:
mpfl operator+(const mpfl &lhs, const mpfl &rhs)
{
unsigned long i;
mpfl ret(0);
mpfl trhs(rhs);
for (i = lhs.nbytes; i >= 0; i--)
{
if (
(unsigned short)lhs.data[i].data + (unsigned short)trhs.data[i].data
> (unsigned short)255
) {
if (i > 0)
{
ret.data[i].carry = 1;
ret.data[0].carry = 0;
}
else
{
ret.data[0].carry = 1;
}
}
else
ret.data[i].carry = 0;
ret.data[i].data = lhs.data[i].data + trhs.data[i].data;
if (i < lhs.nbytes)
{
if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1)
increment(&trhs, i + 1);
ret.data[i].data += ret.data[i + 1].carry;
}
if (i == 0) break;
}
return ret;
}
Вот ссылки на полный исходный код (github сделал это проще, так как его много)
1 ответ
Решение
Ваш код очень грязный для меня. Я делал (долго)num классов много раз до этого (плавающий, фиксированный,uint,templated,...), так что вот несколько советов:
Попробуйте настроить архитектуру ALU, аналогичную реальной реализации HW.
Большинство алгоритмов написаны для такой среды. Это очистит и ускорит ваш код. В некоторых случаях я использую asm для этого, но если вы хотите не зависеть от процессора, вы можете использовать мой класс
Источник ALU в C++:
//--------------------------------------------------------------------------- //--- ALU32 class 2.00 ------------------------------------------------------ //--------------------------------------------------------------------------- #ifndef _ALU32_h #define _ALU32_h //--------------------------------------------------------------------------- #define _ALU32_no_asm //--------------------------------------------------------------------------- class ALU32 { public: BYTE cy; ALU32() { cy=0; } void sar(DWORD &c); // msb -> [msb...lsb] -> cy shift arithmetic right void shl(DWORD &c); // cy <- [msb...lsb] <- 0 shift left void shr(DWORD &c); // 0 -> [msb...lsb] -> cy shift right void rcl(DWORD &c); // cy <- [msb...lsb] <- cy shift through carry left void rcr(DWORD &c); // cy -> [msb...lsb] -> cy shift through carry lright void inc(DWORD &c); void dec(DWORD &c); void add(DWORD &c,DWORD a,DWORD b); void sub(DWORD &c,DWORD a,DWORD b); void adc(DWORD &c,DWORD a,DWORD b); void sbc(DWORD &c,DWORD a,DWORD b); void mul(DWORD &ch,DWORD &cl,DWORD a,DWORD b); // (ch,cl) = a*b void div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b); // c = a/b d =a%b }; //--------------------------------------------------------------------------- void ALU32::inc(DWORD &c) { if (c==0xFFFFFFFF) cy=1; else cy=0; c++; } void ALU32::dec(DWORD &c) { if (c==0x00000000) cy=1; else cy=0; c--; } //--------------------------------------------------------------------------- void ALU32::sar(DWORD &c) { cy=c&1; c=((c>>1)&0x7FFFFFFF)|(c&0x800000000); } //--------------------------------------------------------------------------- void ALU32::shl(DWORD &c) { cy=c>>31; c=(c<<1)&0xFFFFFFFE; } //--------------------------------------------------------------------------- void ALU32::shr(DWORD &c) { cy=c&1; c=(c>>1)&0x7FFFFFFF; } //--------------------------------------------------------------------------- void ALU32::rcl(DWORD &c) { DWORD cy0=cy; cy=c>>31; c=((c<<1)&0xFFFFFFFE)|cy0; } //--------------------------------------------------------------------------- void ALU32::rcr(DWORD &c) { DWORD cy0=cy; cy=c&1; c=((c>>1)&0x7FFFFFFF)|(cy0<<31); } //--------------------------------------------------------------------------- void ALU32::add(DWORD &c,DWORD a,DWORD b) { c=a+b; cy=DWORD(((a &1)+(b &1) )>> 1); cy=DWORD(((a>>1)+(b>>1)+cy)>>31); } //--------------------------------------------------------------------------- void ALU32::sub(DWORD &c,DWORD a,DWORD b) { c=a-b; if (a<b) cy=1; else cy=0; } //--------------------------------------------------------------------------- void ALU32::adc(DWORD &c,DWORD a,DWORD b) { c=a+b+cy; cy=DWORD(((a &1)+(b &1)+cy)>> 1); cy=DWORD(((a>>1)+(b>>1)+cy)>>31); } //--------------------------------------------------------------------------- void ALU32::sbc(DWORD &c,DWORD a,DWORD 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 ALU32::mul(DWORD &ch,DWORD &cl,DWORD a,DWORD b) { #ifdef _ALU32_no_asm const int _h=1; // this is MSW,LSW order platform dependent So swap 0,1 if your platform is different const int _l=0; union _u { DWORD u32; WORD u16[2]; } u; DWORD al,ah,bl,bh; DWORD c0,c1,c2,c3; // separate 2^16 base digits u.u32=a; al=u.u16[_l]; ah=u.u16[_h]; u.u32=b; bl=u.u16[_l]; bh=u.u16[_h]; // multiplication (al+ah<<1)*(bl+bh<<1) = al*bl + al*bh<<1 + ah*bl<<1 + ah*bh<<2 c0=(al*bl); c1=(al*bh)+(ah*bl); c2=(ah*bh); c3= 0; // propagate 2^16 overflows (backward to avoid overflow) c3+=c2>>16; c2&=0x0000FFFF; c2+=c1>>16; c1&=0x0000FFFF; c1+=c0>>16; c0&=0x0000FFFF; // propagate 2^16 overflows (normaly to recover from secondary overflow) c2+=c1>>16; c1&=0x0000FFFF; c3+=c2>>16; c2&=0x0000FFFF; // (c3,c2,c1,c0) >> _fx32_fract_bits u.u16[_l]=c0; u.u16[_h]=c1; c0=u.u32; u.u16[_l]=c2; u.u16[_h]=c3; c1=u.u32; ch=c1; cl=c0; #else DWORD _a,_b,_cl,_ch; _a=a; _b=b; asm { mov eax,_a mov ebx,_b mul ebx // H(edx),L(eax) = eax * ebx mov _cl,eax mov _ch,edx } cl=_cl; ch=_ch; #endif } //--------------------------------------------------------------------------- void ALU32::div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b) { #ifdef _ALU32_no_asm DWORD ch,cl,bh,bl,h,l,mh,ml; int e; // edge cases if (!b ){ c=0xFFFFFFFF; d=0xFFFFFFFF; cy=1; return; } if (!ah){ c=al/b; d=al%b; cy=0; return; } // align a,b for binary long division m is the shifted mask of b lsb for (bl=b,bh=0,mh=0,ml=1;bh<0x80000000;) { e=0; if (ah>bh) e=+1; // e = cmp a,b {-1,0,+1} else if (ah<bh) e=-1; else if (al>bl) e=+1; else if (al<bl) e=-1; if (e<=0) break; // a<=b ? shl(bl); rcl(bh); // b<<=1 shl(ml); rcl(mh); // m<<=1 } // binary long division for (ch=0,cl=0;;) { sub(l,al,bl); // a-b sbc(h,ah,bh); if (cy) // a<b ? { if (ml==1) break; shr(mh); rcr(ml); // m>>=1 shr(bh); rcr(bl); // b>>=1 continue; } al=l; ah=h; // a>=b ? add(cl,cl,ml); // c+=m adc(ch,ch,mh); } cy=0; c=cl; d=al; if ((ch)||(ah)) cy=1; // overflow #else DWORD _al,_ah,_b,_c,_d; _al=al; _ah=ah; _b=b; asm { mov eax,_al mov edx,_ah mov ebx,_b div ebx mov _c,eax // eax = H(edx),L(eax) / ebx mov _d,edx // edx = H(edx),L(eax) % ebx } c=_c; d=_d; #endif } //--------------------------------------------------------------------------- #endif //---------------------------------------------------------------------------mulа такжеdivпереключаются между быстрой сборкой процессора и медленной реализацией C++ с помощью#define _ALU32_no_asmDWORD32 битunsigned intи может быть определено какtypedef unsigned __int32 DWORD;
Так что теперь, если вы хотите добавить два массива (фиксированный размер N)
Это можно сделать так:
ALU32 alu; DWORD a[N],b[N],c[N]; // a[0] is LSB and a[N-1] is MSB alu.add(c[0],a[0],b[0]); for (int i=1;i<N;i++) alu.adc(c[i],a[i],b[i]); // here c[] = a[] + b[]Хорошая идея - использовать самую большую базу для улучшения скорости. Если вам все еще нужен 8-битный ALU, его также можно легко переписать и даже упростить благодаря прямому доступу к переносу. Вы можете использовать 16 или 32-битные переменные и извлечь
9thнемного как нести непосредственно из под-результатов (похоже, что вы делаете это).Ваша проблема (скопировано из комментария)
Держу пари, что ваша проблема здесь:
if (i<lhs.nbytes) { if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1) increment(&trhs, i + 1); ret.data[i].data += ret.data[i + 1].carry; }Керри следует применять всегда, но в первый раз (вы делаете это всегда, но в последний раз). Это также показывает другую возможность, как хранится ваш номер?
data[0]такое LSB или MSB (младший / старший значащий бит / байт...)?
Вы должны начать добавлять с младших цифр
- так что либо вы просто подаете заявление нести другой путь
- или вы добавляете цифры от старшей к младшей
но будки неверны.
PS. в случае, если вам нужно 32 бит умножения в стиле ALU без asm в чистом C/C++ смотрите по этой ссылке (но после последнего обновления здесь код, который уже содержит такие mul,div):