/euclidiana número entero división de la división

Question

Floored de manera eficiente la implementación de solado es cuando el resultado siempre se redondea hacia abajo (hacia -∞), no hacia 0:

¿Es posible aplicar de manera eficiente división entera con suelo o euclidiana en C/C++?

(la solución obvia es comprobar la señal del dividendo)

Answer 1

Volveré a esta cuestión cinco años después, ya que esto también es relevante para mí. Hice algunas mediciones de rendimiento en dos versiones de C puro y dos versiones de ensamblaje en línea para x86-64, y los resultados pueden ser interesantes.

Las variantes ensayadas de división con suelo son:

1. La implementación He estado usando desde hace algún tiempo;
2. La pequeña variante de la presentada arriba que solo usa una división;
3. La anterior, pero implementada a mano en ensamblaje en línea; y
4. A CMOV versión implementada en el ensamblaje.

La siguiente es mi programa de referencia:

#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); 
} 

Compilé esto con gcc -march=native -Ofast usando GCC 4.9.2, y los resultados, en mi Core i5-2400, fueron los siguientes. Los resultados son bastante reproducibles de ejecución a ejecución: siempre aterrizan en el mismo orden, al menos.

• variante 0: 7.21 segundos
• Variante 1: 7,26 segundos
• Variante 2: 6,73 segundos
• Variante 3: 4,32 segundos

Así que la aplicación CMOV sopla los otros fuera de el agua, al menos. Lo que me sorprende es que la variante 2 supera su versión de C puro (variante 1) por un margen bastante amplio. Pensé que el compilador debería poder emitir un código al menos tan eficiente como el mío.

Aquí hay algunas otras plataformas, para la comparación:

AMD Athlon 64 X2 4200+, GCC 4.7.2:

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

v3

Xeon E3-1271, GCC 4.9.2:

• Variant 0: 5.95 segundos
• Variante 1: 5,62 segundos
• Variante 2: 5,40 segundos
• Variante 3: 3,44 segundos

Answer 2

Desde IEEE-754 especifica vuelta hacia -inf como uno de los modos de redondeo requeridas Imagino que la respuesta a su pregunta es sí. Pero quizás pueda explicar si desea saber cómo se implementaría el procedimiento si se estuviera escribiendo el compilador, o si se sabe cómo usar un compilador particular para realizar la operación.

Answer 3

¿Es posible implementar eficientemente la división de enteros con piso o euclidiano en C/C++?

Sí.

(la solución obvia es comprobar la señal del dividendo)

estoy completamente de acuerdo, y podría encontrar difícil de creer que existe una alternativa que es significativamente más rápido.

Answer 4

Podría ser más eficiente crear algo libre de ramas para corregir el resultado en función del signo, ya que las ramas son caras.

Consulte la página 20ff de Chapter 2 en Hacker's Delight sobre cómo acceder al letrero.

Answer 5

He escrito un programa de prueba de referencia para las ideas presentadas aquí:

#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); 
} 

Resultados:

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

Así, de acuerdo con mis resultados, comprobando el signo es el más rápido:

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

Answer 6

Solo una nota: la instrucción x86 sar realiza una gran división cuando se trata de poderes de dos.