[c/asm] Optymalizacja dzielenia calkowitego z zaokrąglaniem

0

Jedną z kluczowych operacji w moim algorytmie jest dzielenie. Dzielę 2 dodatnie liczby int i w wyniku chcę uzyskać liczbę int, która jest wynikiem dzielenia zaokrąglonym do najbliższej liczby całkowitej.
Zastanawiam się jakby to zapisać, aby operacja wykonała się najszybciej. Załóżmy, że chcę otrzymać c=a/b.
Jedyne pomysły jak na razie to:

1) dokładny

c = a / b;
if((a%b) <= (b/2)) c++;

2) prawdopodobnie szybszy, ale nie wiem, czy błędy zaokrągleń mi nie namieszają :/

c = (int) floor((float)a/b + 0.5);

Asm'a nie znam, może on pomoże ?

0
c = ( a + (b>>1)) / b;

Z tymże dla a<0 może być troszkę inaczej:

c = ( a - (b>>1)) / b;
0

div bx ; AX = (DX:AX div BX),
; DX = (DX:AX mod BX)
div edi ; EAX = (EDX:EAX div EDI),
; EDX = (EDX:EAX mod EDI)

... czyli jakos tak to wychodzi ...

int fdiv(unsigned long long dzielna,unsigned dzielnik){
  asm{
    mov edx,[dzielna+4]  // zaladuj spod adresu+4 4 bajty
    mov eax,[dzielna] // zaladuj spod adresu 4 bajty
    div [dzielnik] // podziel
    cmp edx,0  //sprawdz czy restza ==0
    je end // jesli tak skocz do end
    inc eax // eax++
   end: 
    mov [dzielnik],eax // wrzuc do zmiennej rejestr eax
  }
  return dzielnik;
}
0

A jest może taka instrukcja jak 'div', tylko działająca szybciej, na mniejszej ilości bitów ?
Bo tu widzę dzieli 64 bity przez 32. Mi wystarczy 32 przez 16.

0

mysle ze div bedzie sie wykonywalo tak samo szybko/wolno niezaleznie od rozmiaru argumentu. tak czy siak z tego co jest napisane wyzej wynika, ze mozna swobodnie uzywac go do dzialan 16bitowych, po prostu jako argument div podaj nie 32 a 16 bitow

div bx ; AX = (DX:AX div BX),
; DX = (DX:AX mod BX)
div edi ; EAX = (EDX:EAX div EDI),
; EDX = (EDX:EAX mod EDI)

... czyli jakos tak to wychodzi ...

int fdiv(unsigned dzielna,unsigned short dzielnik){
  asm{
    mov dx,[word ptr dzielna+2]  // wczesniej powinno byc 'dword ptr'
    mov ax,[word ptr dzielna]
    div [dzielnik]
    cmp dx,0
    je end
    inc ax
   end: 
    mov [dzielnik],ax
  }
  return dzielnik;
}

a jesli nie chcesz starszych 4/2 bajtow ladowac do e/dx to uzyj zamiast mov: xor dx,dx lub xor edx,edx, ewentualnie zaladuj 0: mov edx.0 lub mov dx,0

0

Flabra, dokładnie nie chodziło o zaokrąglanie w górę tylko do najbliższej całkowitej, czyli trzeba porównać resztę z dzielenia z połową dzielnika. Bazując na twoim kodzie naskrobałem to co poniżej. Skoro dzielenie tak samo szybko się wykonuje to korzystam z wersji 64b/32b po prostu czyszcząc edx'a.

unsigned fdiv(unsigned dzielna, unsigned dzielnik)
{
    asm
    {
        xor edx, edx

mov eax, [dword ptr dzielna]

        mov ebx, [dword ptr dzielnik]
        div ebx
        shl edx, 1

cmp edx, ebx
jle END
inc eax

        END:
    }
}

Jednak przepis który podał MarekR22 jest lepszy, po przerobieniu na asm'a tak wygląda (znaczące różnice w instrukcjach zaznaczyłem na czerwono):

unsigned fdiv(unsigned dzielna, unsigned dzielnik)
{
    asm
    {
        xor edx, edx
        mov eax, [dword ptr dzielnik]

mov ebx, eax

        shr eax, 1

add eax, [dword ptr dzielna] div ebx
}
}



Dzięki za odpowiedzi [browar]

BTW, słówko kluczowe asm nie jest podświetlone i nie linkuje do http://4programmers.net/C/Asm, a powinno.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0