Mam taki problem.
Mam 4 liczby 64-bitowe bez znaku (a, b, c, d). Chciałbym wykonać takie porównanie:
ab < cd
przy czym w ogóle nie interesuje wynik tych iloczynów. Chcę tylko sprawdzić ten warunek. Program ma działać w środowisku 32-bitowym. Jakieś pomysły?
Arytmetyka duzych liczb albo rozbicie tych liczba na jakies male i mnozenie kazdej przez to samo, a potem porownywanie, poza tym nic innego nie da rady, poniewaz liczba 32-bitowa jest przechowywana w jednym rejestrze, a 64 bitowa w dwoch, np EDX:EAX, a nie ma mozliwosci jakiegos bezposredniego przechowania takiej liczby, wiec nie porownasz normalnie tego na x86;
Pomyślmy, czy to nie będzie tak, że starczy porównać sumę logarytmów tych liczb? log(a)+log(b) < log(c)+log(d). Jak przekombinowałem to sorry, trochę styrany jestem.
@t0m_k, weź Ty nie przeginaj z niskopoziomowością i nie wtrącaj assemblera tam, gdzie nie jest jego miejsce?
t0m_k-tmp napisał(a)
poza tym nic innego nie da rady, poniewaz liczba 32-bitowa jest przechowywana w jednym rejestrze, a 64 bitowa w dwoch, np EDX:EAX, a nie ma mozliwosci jakiegos bezposredniego przechowania takiej liczby, wiec nie porownasz normalnie tego na x86;
Jak to nie porównam? Załóżmy że mamy jedną liczbę w EDX:EAX, a drugą w ECX:EBX. Teraz porównujemy EDX z ECX, a jeśli są równe to porównujemy EAX z EBX.
@Świętowit: Jesli mowimy o bezposrednim pomnozeniu tych liczb w if'ie i porownaniu to jak najbardziej jest jego miejsce.
@Azarien: Tak, ale on chce porownac liczby EDX:EAX razy ECX:EBX przykladowo z EDI:ESI razy EBP:ESP, wiec nie da rady tego zrobic na x86 normalnie, ani tego na stos nie odlozy przy takim mnozeniu w if'ach, ani to do rejestrow nie wejdzie, poniewaz w przypadku mnozenia w if'ie przewaznie jedna liczba jest kopiowana do rejestru, wykonywane jest MUL/IMUl, a wynik na koncu jest kopiowany z powrotem do pamieci.
...bez znaku...
ab < cd | /b
a< (c*d)/b | /d
a/d < c/b
t0m_k-tmp napisał(a)
ani tego na stos nie odlozy przy takim mnozeniu w if'ach
Niby dlaczego?
Dobra, to jeszcze jedna istotna rzecz, której nie napisałem. Rozwiązanie powinno by niezawodne.
Tzn zamiana na zmienny przecinek może spowodować błędy przy zaokrągleniach, więc takie coś odpada.
Azarien: Przy probie przypisania do zmiennej lokalnej liczby 64-bitowej ta liczba jest rozwalana na dwie i te dwie sa wrzucane na stos, ale nie przy mnozeniu bez przypisania wyniku:
#include <stdio.h>
int main()
{
long long a, b;
a = 0xDEADBEEFA;
b = 0xDEADBEEFA;
if(a * b > b *a)
printf("a\n");
return 0;
}
W takim przypadku nie dosc, ze bedzie warning rzucony, bo za duze liczby ida do zmiennych to jeszcze gcc na przyklad w ogóle pomija if'a :D
.text:0040131A mov [ebp+var_8], 0EADBEEFAh
.text:00401321 mov [ebp+var_4], 0Dh
.text:00401328 mov [ebp+var_10], 0EADBEEFAh
.text:0040132F mov [ebp+var_C], 0Dh
.text:00401336 mov eax, 0
.text:0040133B leave
.text:0040133C retn
.text:0040133C sub_4012F0 endp
Na stos rowniez nie pojdzie dlatego, ze wynik mnozenia nie jest zapisywany do pamieci, wiec kompilator bedzie to probowal dac do rejestru, bo niby dlaczego mialby wrzucac to na stos w takim przypadku ?
t0m_k-tmp napisał(a)
Na stos rowniez nie pojdzie dlatego, ze wynik mnozenia nie jest zapisywany do pamieci, wiec kompilator bedzie to probowal dac do rejestru, bo niby dlaczego mialby wrzucac to na stos w takim przypadku ?
To było w kontekście asemblera. A tam sobie wrzucasz na stos co ci się podoba.
Tak czy inaczej, czy w asm czy w C, trzeba kombinować.
@Azarien: troche sie nie zrozumielismy, mi caly czas chodzi o to, ze na stos wrzucisz gora dword'y, ile ich bedzie to juz inna sprawa oraz chodzi mi o to, ze ten wynik dopoki nie bedzie zapisany do zmiennej to nie trafi na stos, poniewaz musialaby byc wczesniej dodatkowo pamiec na to zaalokowana, a ze mnozenia pamieci z pamiecia nie wykonasz to te dwie liczby trafiaja do rejestrow, zostaje wykonane mnozenie oraz znowu do rejestrow, a do pamieci tylko wtedy, gdy nastapi przypisanie, wiec taki obrot spraw wyklucza operacje na liczbach 128-bitowych na tej architekturze
flabra dobrze do tego podszedł:
typedef unsigned long long int uint64;
bool isAbLessBc(uint64 a, uint64 b, uint64 c, uint64 d) {
if (b==0 || a==0) {
return c!=0 && d!=0;
}
if (c==0 || d==0) {
return false;
}
uint64 x = a/d;
uint64 y = c/b;
if (x<y)
return true;
if (x>y)
return false;
return (a%d)*b<(c%b)*d;
}
t0m_k-tmp napisał(a)
@Azarien: troche sie nie zrozumielismy, mi caly czas chodzi o to, ze na stos wrzucisz gora dword'y, [CIACH!] wiec taki obrot spraw wyklucza operacje na liczbach 128-bitowych na tej architekturze
Znacznie komplikuje, ale nie wyklucza.
@up: tak, dlatego tez napisalem w pierwszym poscie, ze mozna wykorzystac arytmetyke na duzych liczbach, albo rozbic je na mniejsze, nie napisalem tylko o tym co Świętowit i Flabra przedstawili, ale akurat ten post, ktory zacytowales odnosil sie bezposrednio do porownania w if'ie takim jak na przykladzie ;p
@MarekR22: takie rozwiązanie nie przejdzie, gdyż dla "dużych" d działanie a%d będzie równe a
Jeżeli to dla liczb dodatnich
, i zamiast mnożenia dostajemy dzielenie, które na pewno nie wykracza poza zakres – trzeba tylko uważać na zera w mianownikach. Zostaje do rozwiązania kwestia porównania, bo porównywać trzeba najpierw wynik dzielenia całkowitego, a gdy liczby będą równe, to decyduje porównanie reszt z dzielenia.
edit: widzę że kol. flabra już na to wpadł, ale został niesłusznie zgaszony: liczby zmiennoprzecinkowe nie będą potrzebne.
też mi się tak wydawało, ale jednak Karolaq zauważył, wystarczy że c i b są bardzo duże a a i d tylko nieco mniejsze od nich, to okazuje się, że takie dzielenie nic nie daje, bo problem z resztami jest identyczny z pierwotnym problemem.
Chyba, że (ale nadal nie jestem przekonany, że jest ok):
bool isAbLessBc(uint64 a, uint64 b, uint64 c, uint64 d) {
if (b==0 || a==0) {
return c!=0 && d!=0;
}
if (c==0 || d==0) {
return false;
}
if (c<d) {
swap(c,d);
}
if (a<b) {
swap(a,b);
}
uint64 x = a/d;
uint64 y = c/b;
if (x<y)
return true;
if (x>y)
return false;
return (a%d)*b<(c%b)*d;
}
dobra, dam konkretny przykład:
uint64 a=18446744073709551612LLU,c=18446744073709551613LLU, x=18446744073709551615LLU;
printf(isAbLessBc(a,x,c,x) ? "tak" : "nie");
wiadomo że floating point odpada, wiadomo, że działamy na integerach rzędu 64 albo 128.
to czemu nie wziąć vlong, bigint, etc ? czemu sie czochrać o jeża..?
karolaq - mam nadzieje, ze postac ax <? cx to tylko taki pechowy przyklad, a nie objawiona wlasnie wlasciwa konstrukcja zadania?
MarekR22 napisał(a)
też mi się tak wydawało, ale jednak Karolaq zauważył, wystarczy że c i b są bardzo duże a a i d tylko nieco mniejsze od nich, to okazuje się, że takie dzielenie nic nie daje, bo problem z resztami jest identyczny z pierwotnym problemem.
Nie jest, bo ani dzielenie, ani reszta z dzielenia nigdy nie przekroczy 64 bitów.
quetzalcoatl napisał(a)
wiadomo że floating point odpada, wiadomo, że działamy na integerach rzędu 64 albo 128.
to czemu nie wziąć vlong, bigint, etc ? czemu sie czochrać o jeża..?karolaq - mam nadzieje, ze postac ax <? cx to tylko taki pechowy przyklad, a nie objawiona wlasnie wlasciwa konstrukcja zadania?
nie no, z tym ze b=d t o tylko taki przykład. chodziło mi tylko o wskazanie przypadków, gdzie ten algorytm nie działa.
Oczywiście nie byłoby problemu z napisaniem własnej klasy do obsługi dużych liczb czy ewentualnie skorzystać z istniejącej. Ale mi zależy na szybkości - jak największej. Algorytm i tak będę implementował w assemblerze zapewne.
Wymyśliłem coś takiego:
mamy 2 liczby 64-bitowe. A i B.
Każda z tych liczba składa się z części starszej i młodszej (AH i AL - BH i BL)
AB=(AH<<32 + AL)(BH<<32 + BL)=(AHBH)<<64 + (AHBL+ALBH)<<32 + ALBL
Wynik jest 128 bitowy. Porównanie wyników mnożenia nie robi problemu, więc skupię się na samym mnożeniu:
128 bitów wyniku można podzielić na 3 części:
W0 - młodsza część (64 bity)
W1 - środkowa część (64 bity)
W2 - starsza część (64 bity)
W0 = W1=W2=0
W0 = ALBL
W1 += BLAH+BHAL
W2 += AHBH
i trzeba tutaj jeszcze uwzględnić przeniesienia. Zauważyłem jeden przypadek przeniesienia, tj jednorazowo W2 może być zwiększone o 1. Ale mam pewne wątpliwości czy to jedyna taka możliwość.
Jak w asm będziesz implementować to spróbuj tego:
movdqa/movdqu xmm0,qword ptr A
movdqa/movdqu xmm1,qword ptr B
movdqa/movdqu xmm2,qword ptr C
movdqa/movdqu xmm3,qword ptr D
mulsd xmm0,xmm1
mulsd xmm2,xmm3
cmpsd xmm0,xmm2
Jestem świeżo po formacie więc to jest tak na sucho ale powinno działać - jak nie to motyw z dzieleniem już na pewno powinien ruszyć
niestety nie mogę używać SSE2 i nowszych
t0m_k-tmp napisał(a)
W takim przypadku nie dosc, ze bedzie warning rzucony, bo za duze liczby ida do zmiennych to jeszcze gcc na przyklad w ogóle pomija if'a :D
nie bedzie warninga, a to ze pomija if'a to tzw. optymalizacja.
bzdura, gcc obsluguje inty 64 bitowe (ma takowe rozszerzenie). Poprawnie obsluguje te liczby.
int main()
{
long long a, b;
// 1234123412341234
a = 0x1000000000000000LL;
b = 0x00000000000000AALL;
return (a * b)&0xFF;
}
i wynik:
movl $0, -24(%ebp)
movl $268435456, -20(%ebp)
movl $170, -16(%ebp)
movl $0, -12(%ebp)
movl -20(%ebp), %eax
movl %eax, %ecx
imull -16(%ebp), %ecx
movl -12(%ebp), %eax
imull -24(%ebp), %eax
addl %eax, %ecx
movl -16(%ebp), %eax
mull -24(%ebp)
addl %edx, %ecx
movl %ecx, %edx
andl $255, %eax
addl $20, %esp
popl %ecx
popl %ebp
leal -4(%ecx), %esp
ret
Zadna bzdura ;]
Ten ponizszy przyklad troche miesza, a nie o to mi chodzilo, ale przyjrzyj sie dokladnie na dissasmie co sie wyprawia z wynikiem mnozenia dwoch liczb 64bit:
main:
push ebp
mov ebp, esp
and esp, -16
sub esp, 32
mov DWORD PTR [esp+24], 0
mov DWORD PTR [esp+28], 268435456
mov DWORD PTR [esp+16], 286331153
mov DWORD PTR [esp+20], 286331153
mov eax, DWORD PTR [esp+28]
mov ecx, eax
imul ecx, DWORD PTR [esp+16]
mov eax, DWORD PTR [esp+20]
imul eax, DWORD PTR [esp+24]
add ecx, eax ; tu
mov eax, DWORD PTR [esp+16]
mul DWORD PTR [esp+24]
add ecx, edx ; tu
mov edx, ecx ; i tu
cmp edx, DWORD PTR [esp+20]
jl .L2
cmp edx, DWORD PTR [esp+20]
jg .L5
cmp eax, DWORD PTR [esp+16]
jbe .L2
.L5:
mov ecx, OFFSET FLAT:.LC0
mov eax, DWORD PTR [esp+24]
mov edx, DWORD PTR [esp+28]
mov DWORD PTR [esp+4], eax
mov DWORD PTR [esp+8], edx
mov DWORD PTR [esp], ecx
call printf
.L2:
mov eax, 0
leave
ret
Czyli wynik mamy modulo 2^64, ale pod warunkiem, że starsze słowo któregoś z czynników jest zerem.
Zamiast kombinować trzeba to zrobić na silę (mam nadzieje, że się nie pomyliłem z obliczaniem przeniesienia i nadmiaru z mnożenia):
typedef unsigned long long int ullint;
void multiply(ullint a, ullint b, ullint *rh, ullint *rl)
{
assert(rh);
assert(rl);
register ullint la = a & 0xFFFFFFFF;
register ullint ha = a >> 32;
register ullint lb = b & 0xFFFFFFFF;
register ullint hb = b >> 32;
register ullint resultH = ha * hb;
register ullint resultL = ha*lb;
resultH += resultL >> 32;
resultL&=0xFFFFFFFF;
resultL +=ha*la;
resultH += resultL >> 32;
resultL&=0xFFFFFFFF;
register ullint resultL2 = la*lb;
resultL+= resultL2 >> 32;
resultL2&=0xFFFFFFFF;
resultH += resultL >> 32;
resultL&=0xFFFFFFFF;
resultL = resultL<<32 + resultL2;
*rh = resultH;
*rl = resultL;
}
int compMultip(ullint a, ullint b, ullint c, ullint d)
{
ullint lowLeft, hiLeft, lowRight, hiRight,
multiply(a, b, &hiLeft, &lowLeft);
multiply(c, d, &hiRight, &lowRight);
if(hiLeft<hiRight) {
return -1;
}
if(hiLeft>hiRight) {
return 1;
}
if(lowLeft<lowRight) {
return -1;
}
if(lowLeft>lowRight) {
return 1;
}
return 0;
}
Jeśli preferujesz w asemblerze to skonwertowanie tego nie powinno być dla ciebie kłopotem.