La forma más optimizada para calcular el módulo en C

He minimizado el costo de cálculo del módulo en C. digo que tengo un número x y n es el número que dividirá x

cuando n == 65536 (que resulta ser 2 ^ 16):

mod = x% n (11 instrucciones de assembly producidas por GCC) o
mod = x & 0xffff que es igual a mod = x & 65535 (4 instrucciones de assembly)

Entonces, GCC no lo optimiza en esta medida.

En mi caso, n no es x ^ (int) pero es el número primo más grande menor que 2 ^ 16, que es 65521

como mostré para n == 2 ^ 16, las operaciones bit a bit pueden optimizar el cálculo. ¿Qué operaciones de bits puedo realizar cuando n == 65521 para calcular el módulo?

Primero, asegúrese de que está viendo el código optimizado antes de llegar a una conclusión sobre lo que GCC está produciendo (y asegúrese de que esta expresión en particular realmente necesita ser optimizada). Finalmente, no cuente las instrucciones para sacar sus conclusiones; es posible que se espere que una secuencia de 11 instrucciones se desempeñe mejor que una secuencia más corta que incluya una instrucción div.

Además, no puede concluir que debido a que x mod 65536 puede calcularse con una máscara de bits simple, cualquier operación de mod puede implementarse de esa manera. Considere cuán fácil es dividir entre 10 en decimal y no dividir por un número arbitrario.

Con todo eso fuera del camino, puedes usar algunas de las técnicas de “número mágico” del libro Henry Warren’s Hacker’s Delight:

Hay un capítulo adicional en el sitio web que contiene “dos métodos para calcular el rest de la división sin calcular el cociente”, que puede encontrar de alguna utilidad. La primera técnica se aplica solo a un conjunto limitado de divisores, por lo que no funcionará para su instancia en particular. En realidad no he leído el capítulo en línea, por lo que no sé exactamente cuán aplicable podría ser la otra técnica para usted.

x mod 65536 solo es equivalente a x & 0xffff si x no está firmado: para x firmado, da un resultado incorrecto para números negativos. Para x sin signo, gcc realmente optimiza x % 65536 a nivel de bits y con 65535 (incluso en -O0, en mis pruebas).

Debido a que 65521 no es una potencia de 2, x mod 65521 no se puede calcular de manera tan simple. gcc 4.3.2 en -O3 lo calcula utilizando x - (x / 65521) * 65521 ; la división de enteros por una constante se realiza mediante la multiplicación de enteros por una constante relacionada.

Si no tiene que reducir completamente sus enteros módulo 65521, entonces puede usar el hecho de que 65521 está cerca de 2 ** 16. Es decir, si x es un int sin signo que desea reducir, puede hacer lo siguiente:

 unsigned int low = x &0xffff; unsigned int hi = (x >> 16); x = low + 15 * hi; 

Esto utiliza ese 2 ** 16% 65521 == 15. Tenga en cuenta que esto no es una reducción total. Es decir, comenzando con una entrada de 32 bits, solo se garantiza que el resultado es a lo sumo 20 bits y que, por supuesto, es congruente con el módulo de entrada 65521.

Este truco se puede utilizar en aplicaciones en las que hay muchas operaciones que deben reducirse en módulo a la misma constante, y donde los resultados intermedios no tienen que ser el elemento más pequeño en su clase de residuos.

Por ejemplo, una aplicación es la implementación de Adler-32, que utiliza el módulo 65521. Esta función hash realiza muchas operaciones con un módulo 65521. Para implementarla de manera eficiente, solo se harían reducciones modulares después de un número de adiciones cuidadosamente calculado. Una reducción mostrada como anteriormente es suficiente y solo el cálculo del hash necesitará una operación de módulo completo.

La operación bitwise solo funciona bien si el divisor tiene la forma 2^n . En el caso general, no hay tal operación de bit a bit.

Si la constante con la que desea tomar el módulo se conoce en tiempo de comstackción y tiene un comstackdor decente (por ejemplo, gcc), por lo general es mejor dejar que el comstackdor haga su magia. Solo declara el modulo const.

Si no conoce la constante en el momento de la comstackción, pero tomará, digamos, mil millones de módulos con el mismo número, entonces use este http://libdivide.com/

Como enfoque cuando tratamos con potencias de 2, puede considerarse este (principalmente con sabor a C):

 . . #define THE_DIVISOR 0x8U; /* The modulo value (POWER OF 2). */ . . uint8 CheckIfModulo(const sint32 TheDividend) { uint8 RetVal = 1; /* TheDividend is not modulus THE_DIVISOR. */ if (0 == (TheDividend & (THE_DIVISOR - 1))) { /* code if modulo is satisfied */ RetVal = 0; /* TheDividend IS modulus THE_DIVISOR. */ } else { /* code if modulo is NOT satisfied */ } return RetVal; } 

Si x es un índice creciente, y se sabe que el incremento i es menor que n (por ejemplo, cuando se itera sobre una matriz circular de longitud n ), evite el módulo por completo. Un bucle va

 x += i; if (x >= n) x -= n; 

es mucho más rápido que

 x = (x + i) % n; 

que desafortunadamente encuentras en muchos libros de texto …

Si realmente necesita una expresión (por ejemplo, porque la está usando en una statement for ), puede usar el feo pero eficiente

 x = x + (x+i < n ? i : in) 

idiv – división entera

La instrucción idiv divide el contenido del entero EDX: EAX de 64 bits (construido mediante la visualización de EDX como los cuatro bytes más significativos y EAX como los cuatro bytes menos significativos) por el valor del operando especificado. El cociente de la división se almacena en EAX, mientras que el rest se coloca en EDX .

fuente: http://www.cs.virginia.edu/~evans/cs216/guides/x86.html

Implementación de menor costo del módulo en C


¿Qué hay de la implementación de MOD de la siguiente manera:

Para encontrar: y = X mod n

 y = X-(X/n)*n 

(Suponiendo que tanto X como n son enteros)

NOTA: Para la optimización del nivel de ensamblaje, use iDiv como se explica anteriormente por Krystian.