c++ - populares - hashtags twitter lista

Módulos sin firmar: enfoque alternativo?

Question

Necesito optimizar esta función realmente pequeña pero molesta.

unsigned umod(int a, unsigned b)
{
while(a < 0)
a += b;
return a % b;
}

Antes de gritar "No es necesario que lo optimice", tenga en cuenta que esta función se llama el 50% de la duración total del programa, ya que se llama 21495808 veces para el benchmark de caso de prueba más pequeño.

La función ya está siendo indicada por el compilador, por lo que no debe agregar la palabra clave en inline .

Answer 1

Aparte del ciclo while, no estoy seguro de si la operación% se puede optimizar como un todo, pero la optimización puede ocurrir en el patrón de los valores para a & b.

Si en esos 21495808 tiempos se ejecuta la operación.

Si las posibilidades de pasar un valor por a que es menor que b (a <b) es al menos la mitad de eso. Agregar la siguiente declaración definitivamente mejorará el rendimiento general de la función.

if ( abs(a) < b ) // not specifically the abs function, can be your own implementation.
return 0;
else
return a%b;

Si b es una potencia de 2 para al menos el 80% de los casos, podemos usar operadores bit a bit como en

return ( abs(a) & (b-1) );

Si se espera que los números sean algo menos que eso, se degradaría el rendimiento, ya que necesitamos verificar si b es potencia de 2 [incluso después de usar operadores bit a bit para lo mismo] para todo.

Incluso la funcionalidad para lograr abs (a) se puede optimizar utilizando operadores bit a bit, con sus propias limitaciones, pero es más rápido que verificar si a es <0.

n = (a ^ (a >> 31)) - (a >> 31); // instead of n = a < 0 ? -a : a;

Habría más cosas así, si puedes explorar.

Answer 2

Aquí hay uno que funciona en toda la gama de unsigned sin ramificación, pero usa multiplicaciones y 2 divisiones

unsigned umod(int a, unsigned b)
{
return (a>0)*a%b+(a<0)*(b-1-~a%b);
}

Answer 3

Dado que la versión de bucle parece ser bastante rápida, intentemos eliminar la división :)

unsigned umod(int a, unsigned b){
while(a>0)a-=b;
while(a<0)a+=b;
return a;
}

Answer 4

Edición portátil, todavía con una sola división, sin ramificaciones y sin multiplicación:

unsigned umod(int a, unsigned b) {
int rem = a % (int) b;
return rem + (-(rem < 0) & b);
}

Answer 5

En a % b , si alguno de los operandos unsigned está unsigned ambos se convierten en unsigned . Esto significa que si a es negativo, obtienes un valor UINT_MAX + 1 módulo en lugar de a . Si UINT_MAX+1 es divisible uniformemente por b , entonces las cosas están bien, y solo puede devolver a % b . Si no, tienes que hacer el módulo en tipo int .

unsigned int umod(int a, unsigned int b)
{
int ret;
if (a >= 0) return a % b;
if (b > INT_MAX) return a + b;
ret = a % (int)b;
if (ret < 0) ret += b;
return ret;
}

Editar : actualizado, pero debes usar la respuesta de café ya que es más simple (¿o no?). Esto está aquí para el registro.

Answer 6

En su función original, podría haber regresado después de que el ciclo while haya terminado para los números negativos, omitiendo así el mod. Esto tiene el mismo espíritu, reemplazando el bucle con un multiplicador, aunque podría hacerse para tener menos caracteres ...

unsigned int umod2(int a, unsigned int b)
{
return (a < 0) ? a + ((-a/b)+1)*b : a % b;
}

Aquí está la versión de bucle:

unsigned int umod2_works(int a, unsigned int b)
{
if (a < 0)
{
while (a < 0)
a += b;
return a;
} else {
return a % b;
}
}

Ambos han sido probados para coincidir con la función original del OP.

Answer 7

Esto debería hacerlo:

unsigned umod(int a, unsigned b)
{
if (a < 0)
{
unsigned r = (-a % b);
if (r)
return b - r;
else
return 0;
}
else
return a % b;
}

Probado para que coincida con el original. La limitación es que a > INT_MIN en máquinas complementarias 2s.

Answer 8

Esto evita el bucle:

int tmp = a % b;
if (tmp < 0) tmp += b;

Tenga en cuenta que tanto a como b deben estar firmados.

Answer 9

Mi solución preferida es modificar dos veces. No he intentado esto en C / C ++ o con unsigned, pero mis casos de prueba funcionan en Java:

((a % b) + b) % b

El beneficio no es la bifurcación y la simplicidad. El inconveniente es la doble mod. No comparé el rendimiento, pero tengo entendido que las ramificaciones perjudican el rendimiento en estos días.

Answer 10

Si a y b son mucho más pequeños que un int, entonces puedes simplemente agregar un múltiplo suficientemente grande de b a cada valor antes de modificar.

unsigned umod(int a, unsigned b)
{
return (unsigned)(a + (int)(b * 256)) % b;
}

Por supuesto, este truco no funciona si un + (b * 256) puede desbordarse, pero para muchos de los usos que puedo ver para este código, puedes estar seguro de que nunca lo hará.

Answer 11

Usando el ~ :)

unsigned umod(int a, unsigned b)
{
if (a<0) return b-1-~a%b;
return a%b;
}

El % tiene mayor prioridad que -

Si está bien devolver b en lugar de 0 cuando -a es un múltiplo de b, puedes guardar algunas operaciones

unsigned umod(int a, unsigned b)
{
if (a<0) return b - (-a % b);
return a%b;
}

versión ligeramente golfizada :)

unsigned umod(int a, unsigned b)
{
return(a<0)?b-(-a%b):a%b;
}

Aquí está el ensamblaje resultante

1 .globl umod3
2 .type umod3, @function
3 umod3:
4 .LFB3:
5 .cfi_startproc
6 testl %edi, %edi
7 js .L18
8 movl %edi, %eax
9 xorl %edx, %edx
10 divl %esi
11 movl %edx, %eax
12 ret
13 .p2align 4,,10
14 .p2align 3
15 .L18:
16 movl %edi, %eax
17 xorl %edx, %edx
18 negl %eax
19 divl %esi
20 subl %edx, %esi
21 movl %esi, %edx
22 movl %edx, %eax
23 ret

Answer 12

int temp;
temp= (a > 0)? ( a % b ) : b -( (-a) % b ) ;

código a continuación:

int main()
{
int a;
unsigned b;
int temp;
printf("please enter an int and a unsigned number/n");
scanf("%d",&a);
scanf("%u",&b);
modulus(a,b);
temp= (a > 0)? ( a % b ) : b -( (-a) % b ) ;
printf("/n temp is %d", temp);
return 0;
}
void modulus(int x,unsigned y)
{
int c;
if(x>0)
{
c=x%y;
printf("/n%d/n",c);}
else
{
while(x<0)
x+=y;
printf("/n%d/n",x);}
}
./a.out
please enter an int and a unsigned number
-8 3
1
temp is 1