🚀 go-pugleaf

On Friday, October 7, 2016 at 3:50:57 PM UTC+2, Borneq wrote:
> Mam liczby bez znaku, licznik się przekręca gdy po dodawaniu wynik 
> będzie mniejszy, ale od czego?
> x = a
> x += b
> i teraz przekręcenie gdy a+b<a, ale czy tu nie ma symetrii i nie należy 
> porównywać z b?
> A coś takiego:
> x = a+b

W przypadku przekręcenia wynik będzie wynosił

a+b-2^64

Możęsz sobie sprawdzić, zę to ejst liczba mniejsza zarowno od a, jak i od b. 

a+b -2^64 ?< a
Kasujemy a, przesuwamy stałą na drugą stronę
b ?< 2^64 
Co jest oczywiście prawdą. 

Powtórz rachunek dla b.


Ja bym zadał inne pytanie, czy kompilator wpadnie na to,
by skorzystać z flagi przeniesienia? 

pzdr
bartekltg

W dniu 07.10.2016 o 16:58, bartekltg pisze:
> a+b-2^64
>
> Możęsz sobie sprawdzić, zę to ejst liczba mniejsza zarowno od a, jak i od b.
>
> a+b -2^64 ?< a
> Kasujemy a, przesuwamy stałą na drugą stronę
> b ?< 2^64
> Co jest oczywiście prawdą.
>
> Powtórz rachunek dla b.

czyli
if (wynik<a) przeniesienie=1;
if (wynik<b) przeniesienie=1;
te dwa będą dobre a dla jednego było by źle
W źródłach GMP, w mini-gmp.c w funkcji a raczej makro gmp_umul_ppmm jest:
#define gmp_umul_ppmm(w1, w0, u, v)			\
   do {							\
     mp_limb_t __x0, __x1, __x2, __x3;			\
     unsigned __ul, __vl, __uh, __vh;			\
     mp_limb_t __u = (u), __v = (v);			\
							\
     __ul = __u & GMP_LLIMB_MASK;			\
     __uh = __u >> (GMP_LIMB_BITS / 2);			\
     __vl = __v & GMP_LLIMB_MASK;			\
     __vh = __v >> (GMP_LIMB_BITS / 2);			\
							\
     __x0 = (mp_limb_t) __ul * __vl;			\
     __x1 = (mp_limb_t) __ul * __vh;			\
     __x2 = (mp_limb_t) __uh * __vl;			\
     __x3 = (mp_limb_t) __uh * __vh;			\
							\
     __x1 += __x0 >> (GMP_LIMB_BITS / 2);/* this can't give carry */\
     __x1 += __x2;		/* but this indeed can */\
     if (__x1 < __x2)		/* did we get it? */	\
       __x3 += GMP_HLIMB_BIT;	/* yes, add it in the proper pos. *\
							\
     (w1) = __x3 + (__x1 >> (GMP_LIMB_BITS / 2));	\
     (w0) = (__x1 << (GMP_LIMB_BITS / 2)) + (__x0 & GMP_LLIMB_MASK)\
   } while (0)

jaśniej przerobione w funkcji :
void mulTwoLimbsGMP(limb_t a, limb_t b, limb_t &p, limb_t &c)
{	
	limb_t A = a & hlimbMask;
	limb_t B = a >> hlimbBits;
	limb_t C = b & hlimbMask;
	limb_t D = b >> hlimbBits;

	limb_t AC = A * C;
	limb_t AD = A * D;
	limb_t BC = B * C;
	limb_t BD = B * D;

	limb_t AC_AD_BC = AD + (AC >> hlimbBits) + BC;
	if (AC_AD_BC < BC)
	{
		assert(AD + (AC >> hlimbBits) >= BC);
		BD += hlimbBit;		
	}
	c = BD + (AC_AD_BC >> hlimbBits);
	p = (AC_AD_BC << hlimbBits) + (AC & hlimbMask);
}
Skąd wiadomo że AD + (AC >> hlimbBits) nie spowoduje Carry, ale dodanie 
BC tak, i tylko sprawdzanie z BC, a nie zawsze assert(AD + (AC >> 
hlimbBits) >= BC) - i przeciwny assert też nie zawsze, dla:

typedef uint8_t limb_t;
const int limbBits = sizeof(limb_t)*8;
const int hlimbBits = limbBits / 2;
const limb_t hlimbBit = 1 << hlimbBits;
const limb_t hlimbMask = (1 << hlimbBits) - 1;

a mimo tego, jest to sprawdzenie i działa dla 256x256 możliwości

On Friday, October 7, 2016 at 5:51:16 PM UTC+2, Borneq wrote:
> W dniu 07.10.2016 o 16:58, bartekltg pisze:
> > a+b-2^64
> >
> > Możęsz sobie sprawdzić, zę to ejst liczba mniejsza zarowno od a, jak i od b.
> >
> > a+b -2^64 ?< a
> > Kasujemy a, przesuwamy stałą na drugą stronę
> > b ?< 2^64
> > Co jest oczywiście prawdą.
> >
> > Powtórz rachunek dla b.
> 
> czyli
> if (wynik<a) przeniesienie=1;
> if (wynik<b) przeniesienie=1;


> te dwa będą dobre a dla jednego było by źle

Nic nie rozumiem. 

W poprzednim poście dałem Ci _dowód_, że wystarczy jeden
z tych testów, wszystko jedno który. 


pzdr
bartekltg

W dniu 07.10.2016 o 18:05, bartekltg pisze:
> Nic nie rozumiem.
>
> W poprzednim poście dałem Ci _dowód_, że wystarczy jeden
> z tych testów, wszystko jedno który.

To weźmy kod
if (test1) pisz("Carry");else pisz("nie Carry");
if (test2) pisz("Carry");else pisz("nie Carry");

Czyli jednocześnie będą pisać "Carry" albo "nie Carry"?