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

residuo de una division en c++

Question

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 montaje producidas por GCC) o
mod = x & 0xffff que es igual a mod = x & 65535 (4 instrucciones de montaje)

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?

Answer 1

Implementación de menor costo de 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.

Answer 2

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

Answer 3

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

Answer 4

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 se puede calcular 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:

• http://www.hackersdelight.org/
• http://www.hackersdelight.org/magic.htm

Hay un capítulo adicional en el sitio web que contiene "dos métodos para calcular el resto 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.

Answer 5

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 declaración for ), puede usar el feo pero eficiente

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

Answer 6

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

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

Answer 7

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 resto se coloca en EDX .

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

Answer 8

r 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 como se muestra arriba es suficiente y solo el cálculo del hash necesitará una operación de módulo completo.

Answer 9

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.