efficiente all'attuazione di pavimentata/euclidea divisione intera divisione

Question

Floored è quando il risultato è sempre pavimentata (verso -∞), non verso 0:

È possibile implementare in modo efficiente divisione intera pavimento o euclidea in C/C++?

(la soluzione più ovvia è quello di verificare il segno del dividendo)

Answer 1

Sto rivisitando questa domanda cinque anni dopo, poiché questo è rilevante anche per me. Ho eseguito alcune misurazioni delle prestazioni su due versioni pure C e due inline-assembly per x86-64, e i risultati potrebbero essere interessanti.

Le varianti testate della divisione pavimenti sono:

1. L'implementazione ho usato per qualche tempo;
2. La leggera variante su quella presentata sopra che utilizza solo una divisione;
3. Il precedente, ma implementato manualmente in inline-assembly; e
4. Una versione CMOV implementata in assembly.

Quello che segue è il mio programma di riferimento:

#include <stdio.h> 
#include <stdlib.h> 
#include <sys/time.h> 

#ifndef VARIANT 
#define VARIANT 3 
#endif 

#if VARIANT == 0 
#define floordiv(a, b) (((a) < 0)?((((a) + 1)/(b)) - 1):((a)/(b))) 
#elif VARIANT == 1 
#define floordiv(a, b) ((((a) < 0)?((a) - ((b) - 1)):(a))/(b)) 
#elif VARIANT == 2 
#define floordiv(a, b) ({         \ 
    int result;            \ 
    asm("test %%eax, %%eax; jns 1f; sub %1, %%eax;"   \ 
     "add $1, %%eax; 1: cltd; idivl %1;"     \ 
     : "=a" (result)          \ 
     : "r" (b),           \ 
      "0" (a)           \ 
     : "rdx");           \ 
    result;}) 
#elif VARIANT == 3 
#define floordiv(a, b) ({           \ 
    int result;              \ 
    asm("mov %%eax, %%edx; sub %1, %%edx; add $1, %%edx;"   \ 
     "test %%eax, %%eax; cmovs %%edx, %%eax; cltd;"    \ 
     "idivl %1;"             \ 
     : "=a" (result)            \ 
     : "r" (b),             \ 
      "0" (a)             \ 
     : "rdx");             \ 
    result;}) 
#endif 

double ntime(void) 
{ 
    struct timeval tv; 

    gettimeofday(&tv, NULL); 
    return(tv.tv_sec + (((double)tv.tv_usec)/1000000.0)); 
} 

void timediv(int n, int *p, int *q, int *r) 
{ 
    int i; 

    for(i = 0; i < n; i++) 
     r[i] = floordiv(p[i], q[i]); 
} 

int main(int argc, char **argv) 
{ 
    int n, i, *q, *p, *r; 
    double st; 

    n = 10000000; 
    p = malloc(sizeof(*p) * n); 
    q = malloc(sizeof(*q) * n); 
    r = malloc(sizeof(*r) * n); 
    for(i = 0; i < n; i++) { 
     p[i] = (rand() % 1000000) - 500000; 
     q[i] = (rand() % 1000000) + 1; 
    } 

    st = ntime(); 
    for(i = 0; i < 100; i++) 
     timediv(n, p, q, r); 
    printf("%g\n", ntime() - st); 
    return(0); 
} 

ho compilato questo con gcc -march=native -Ofast usando GCC 4.9.2, ed i risultati, il mio core i5-2400, sono stati i seguenti. I risultati sono abbastanza riproducibili da una corsa all'altra - atterrano sempre nello stesso ordine, almeno.

• Variante 0: 7.21 secondi
• Variante 1: 7,26 secondi
• Variante 2: 6.73 secondi
• Variante 3: 4.32 secondi

Così l'attuazione CMOV soffia gli altri fuori l'acqua, almeno. Ciò che mi sorprende è che la variante 2 out-fa la sua versione in puro C (variante 1) con un margine abbastanza ampio. Avrei pensato che il compilatore dovesse essere in grado di emettere codice almeno efficiente quanto il mio.

Qui ci sono alcune altre piattaforme, per il confronto:

AMD Athlon 64 X2 4200+, GCC 4.7.2:

• Variante 0: 26.33 secondi
• Variante 1: 25,38 secondi
• Variante 2: 25.19 secondi
• Variante 3: 22.39 secondi

Xeon E3-1271 v3, GCC 4.9.2:

• Variante 0: 5.95 secondi
• Variante 1: 5,62 secondi
• Variante 2: 5.40 secondi
• Variante 3: 3,44 secondi

Answer 2

Dal IEEE-754 specifica rotonda verso -inf come una delle modalità di arrotondamento richieste immagino che la risposta alla tua domanda è sì. Ma forse puoi spiegare se vuoi sapere come si implementerebbe la procedura se uno stava scrivendo il compilatore, o per sapere come usare un particolare compilatore per eseguire l'operazione?

Answer 3

È possibile implementare in modo efficiente la divisione di interi o floored euclidian in C/C++?

Sì.

(la soluzione più ovvia è quello di verificare il segno del dividendo)

Sono completamente d'accordo, e avrebbero trovato difficile credere esiste un'alternativa che è significativamente più veloce.

Answer 4

Potrebbe essere più efficiente trovare un ramo libero per correggere il risultato in base al segno, poiché i rami sono costosi.

Vedere pagina 20ff di Chapter 2 in Hacker's Delight su come accedere al segno.

Answer 5

Ho scritto un programma di test al benchmark le idee presentate qui:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <windows.h> 

#define N 10000000 
#define M 100 

int dividends[N], divisors[N], results[N]; 

__forceinline int floordiv_signcheck(int a, int b) 
{ 
    return (a<0 ? a-(b-1) : a)/b; 
} 

__forceinline int floordiv_signcheck2(int a, int b) 
{ 
    return (a - (a<0 ? b-1 : 0))/b; 
} 

__forceinline int floordiv_signmultiply(int a, int b) 
{ 
    return (a + (a>>(sizeof(a)*8-1))*(b-1))/b; 
} 

__forceinline int floordiv_floatingpoint(int a, int b) 
{ 
    // I imagine that the call to floor can be replaced to a cast 
    // if you can get FPU rounding control to work (I couldn't). 
    return floor((double)a/b); 
} 

void main() 
{ 
    for (int i=0; i<N; i++) 
    { 
     dividends[i] = rand(); 
     do 
      divisors[i] = rand(); 
     while (divisors[i]==0); 
    } 

    LARGE_INTEGER t0, t1; 

    QueryPerformanceCounter(&t0); 
    for (int j=0; j<M; j++) 
     for (int i=0; i<N; i++) 
      results[i] = floordiv_signcheck(dividends[i], divisors[i]); 
    QueryPerformanceCounter(&t1); 
    printf("signcheck : %9llu\n", t1.QuadPart-t0.QuadPart); 

    QueryPerformanceCounter(&t0); 
    for (int j=0; j<M; j++) 
     for (int i=0; i<N; i++) 
      results[i] = floordiv_signcheck2(dividends[i], divisors[i]); 
    QueryPerformanceCounter(&t1); 
    printf("signcheck2 : %9llu\n", t1.QuadPart-t0.QuadPart); 

    QueryPerformanceCounter(&t0); 
    for (int j=0; j<M; j++) 
     for (int i=0; i<N; i++) 
      results[i] = floordiv_signmultiply(dividends[i], divisors[i]); 
    QueryPerformanceCounter(&t1); 
    printf("signmultiply : %9llu\n", t1.QuadPart-t0.QuadPart); 

    QueryPerformanceCounter(&t0); 
    for (int j=0; j<M; j++) 
     for (int i=0; i<N; i++) 
      results[i] = floordiv_floatingpoint(dividends[i], divisors[i]); 
    QueryPerformanceCounter(&t1); 
    printf("floatingpoint: %9llu\n", t1.QuadPart-t0.QuadPart); 
} 

Risultati:

signcheck : 61458768 
signcheck2 : 61284370 
signmultiply : 61625076 
floatingpoint: 287315364 

Così, secondo i miei risultati, controllando il segno è il più veloce:

(a - (a<0 ? b-1 : 0))/b 

Answer 6

Solo una nota: l'istruzione x86 sar esegue la divisione floored quando si tratta di poteri di due.