¿Existe alguna alternativa al uso % (módulo) en C/C++?

StackOverflow https://stackoverflow.com/questions/48053

  •  09-06-2019
  •  | 
  •  

Pregunta

Una vez leí en alguna parte que el operador de módulo es ineficiente en pequeños dispositivos integrados, como microcontroladores de 8 bits, que no tienen instrucciones de división de enteros.Quizás alguien pueda confirmar esto, pero pensé que la diferencia es entre 5 y 10 veces más lenta que con una operación de división de números enteros.

¿Hay otra forma de hacer esto además de mantener una variable de contador y desbordarla manualmente a 0 en el punto de modificación?

const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}

frente a:

La forma en que lo estoy haciendo actualmente:

const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
    if(fizzcount >= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}
¿Fue útil?

Solución

Ah, los placeres de la aritmética bit a bit.Un efecto secundario de muchas rutinas de división es el módulo, por lo que en algunos casos la división debería ser más rápida que el módulo.Me interesa ver de qué fuente obtuviste esta información.Los procesadores con multiplicadores tienen rutinas de división interesantes usando el multiplicador, pero puedes pasar del resultado de la división al módulo con sólo otros dos pasos (multiplicar y restar), por lo que sigue siendo comparable.Si el procesador tiene una rutina de división incorporada, probablemente verá que también proporciona el resto.

Aun así, existe una pequeña rama de la teoría de números dedicada a Aritmética modular lo cual requiere estudio si realmente desea comprender cómo optimizar una operación de módulo.La aritmática modular, por ejemplo, es muy útil para generar cuadrados magicos.

Entonces, en ese sentido, aquí hay un aspecto de muy bajo nivel en las matemáticas del módulo para ver un ejemplo de x, que debería mostrarle lo simple que se puede comparar con la división:

Tal vez una mejor manera de pensar sobre el problema es en términos de bases numéricas y aritmética de módulo.Por ejemplo, su objetivo es calcular Dow Mod 7, donde Dow es la representación de 16 bits del día de la semana.Puedes escribir esto como:

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

Expresado de esta manera, puede calcular por separado el resultado del Módulo 7 para los bytes altos y bajos.Multiplique el resultado para el alto por 4 y agréguelo a la baja y finalmente calcule el módulo de resultados 7.

La calculación del resultado del Mod 7 de un número de 8 bits se puede realizar de manera similar.Puedes escribir un número de 8 bits en octal así:

  X = a*64 + b*8 + c

Donde a, b y c son números de 3 bits.

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

desde 64%7 = 8%7 = 1

Por supuesto, a, b y c son

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

El mayor valor posible para a+b+c es 7+7+3 = 17.Entonces, necesitarás un paso octal más.La versión C completa (no probada) podría escribirse como:

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

Pasé unos momentos escribiendo una versión PIC.La implementación real es ligeramente diferente a la descrita anteriormente

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

Aquí hay una pequeña rutina para probar el algoritmo.

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

Finalmente, para el resultado de 16 bits (que no he probado), podría escribir:

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

Scott

Otros consejos

Si está calculando un número mod con una potencia de dos, puede usar el operador and bit a bit.Simplemente resta uno del segundo número.Por ejemplo:

x % 8 == x & 7
x % 256 == x & 255

Algunas advertencias:

  1. Este solo funciona si el segundo número es una potencia de dos.
  2. Sólo es equivalente si el módulo es siempre positivo.Los estándares C y C++ no especifican el signo del módulo cuando el primer número es negativo (hasta C++ 11, que hace garantizará que será negativo, que es lo que la mayoría de los compiladores ya estaban haciendo).Un poco a poco y elimina el bit de signo, por lo que siempre será positivo (es decir,es un verdadero módulo, no un resto).Sin embargo, parece que eso es lo que quieres.
  3. Probablemente su compilador ya haga esto cuando puede, por lo que en la mayoría de los casos no vale la pena hacerlo manualmente.

La mayor parte del tiempo hay una sobrecarga al usar módulos que no son potencias de 2.Esto es independientemente del procesador, ya que (AFAIK) incluso los procesadores con operadores de módulo son algunos ciclos más lentos para las operaciones de división que para las de máscara.

En la mayoría de los casos, esta no es una optimización que valga la pena considerar y ciertamente no vale la pena calcular su propia operación abreviada (especialmente si todavía implica dividir o multiplicar).

Sin embargo, una regla general es seleccionar tamaños de matriz, etc.ser potencias de 2.

Entonces, si calcula el día de la semana, también puede usar %7, independientemente de si establece un búfer circular de alrededor de 100 entradas ...¿Por qué no hacerlo 128?Luego puede escribir % 128 y la mayoría (todos) los compiladores harán esto & 0x7F

A menos que realmente necesite un alto rendimiento en múltiples plataformas integradas, ¡no cambie la forma de codificar por razones de rendimiento hasta que cree el perfil!

El código que se escribe de manera incómoda para optimizar el rendimiento es difícil de depurar y de mantener.Escriba un caso de prueba y perfilelo en su objetivo.Una vez que conozca el costo real del módulo, decida si vale la pena codificar la solución alternativa.

@Matthew tiene razón.Prueba esto:

int main() {
  int i;
  for(i = 0; i<=1024; i++) {
    if (!(i & 0xFF)) printf("& i = %d\n", i);
    if (!(i % 0x100)) printf("mod i = %d\n", i);
  }
}

x%y == (x-(x/y)*y)

Espero que esto ayude.

En el mundo integrado, las operaciones del "módulo" que debe hacer a menudo son las que se descomponen bien en operaciones de bits que puede hacer con '&' y '|' y a veces '>>'.

¿Tiene acceso a algún hardware programable en el dispositivo integrado?¿Te gustan los contadores y cosas así?Si es así, es posible que puedas escribir una unidad de modificación basada en hardware, en lugar de utilizar el % simulado.(Lo hice una vez en VHDL.Aunque no estoy seguro si todavía tengo el código).

Eso sí, dijiste que la división era entre 5 y 10 veces más rápida.¿Has considerado hacer una división, multiplicación y resta para simular el mod?(Editar:Entendí mal la publicación original.Pensé que era extraño que la división fuera más rápida que la modificación, son la misma operación).

Sin embargo, en su caso específico, está buscando un mod de 6.6 = 2*3.Por lo tanto, QUIZÁS podría obtener algunas pequeñas ganancias si primero verificara si el bit menos significativo era 0.Algo como:

if((!(x & 1)) && (x % 3))
{
    print("Fizz\n");
}

Sin embargo, si haces eso, te recomiendo que confirmes que obtienes ganancias, ¡bien para los perfiladores!Y haciendo algunos comentarios.De lo contrario, me sentiría mal por el próximo tipo que tenga que mirar el código.

Realmente deberías verificar el dispositivo integrado que necesitas.Todo el lenguaje ensamblador que he visto (x86, 68000) implementa el módulo mediante una división.

En realidad, la operación de ensamblaje de división devuelve el resultado de la división y el resto en dos registros diferentes.

No es que esto sea necesariamente mejor, pero podría tener un bucle interno que siempre llegue hasta FIZZ y un bucle externo que lo repita todo un número determinado de veces.Entonces quizás tengas que aplicar un caso especial en los últimos pasos si MAXCOUNT no es divisible por FIZZ.

Dicho esto, sugeriría investigar un poco y elaborar perfiles de rendimiento en las plataformas previstas para tener una idea clara de las limitaciones de rendimiento a las que se enfrenta.Es posible que haya lugares mucho más productivos donde dedicar su esfuerzo de optimización.

@Jeff V:¡Veo un problema con eso!(Más allá de eso, su código original buscaba un mod 6 y ahora esencialmente está buscando un mod 8).¡Sigues haciendo un +1 extra!Esperemos que su compilador lo optimice, pero ¿por qué no comenzar la prueba en 2 e ir a MAXCOUNT inclusive?Finalmente, devuelve verdadero cada vez que (x+1) NO es divisible por 8.¿Es eso lo que quieres?(Supongo que sí, pero sólo quiero confirmarlo).

Para el módulo 6 puedes cambiar el código Python a C/C++:

def mod6(number):
    while number > 7:
        number = (number >> 3 << 1) + (number & 0x7)
    if number > 5:
        number -= 6
    return number

La declaración impresa tomará órdenes de magnitud más largas que incluso la implementación más lenta del operador de módulo.Básicamente, el comentario "lento en algunos sistemas" debería ser "lento en todos los sistemas".

Además, los dos fragmentos de código proporcionados no hacen lo mismo.En el segundo, la línea

if(fizzcount >= FIZZ)

siempre es falso, por lo que "FIZZ " nunca se imprime.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top