parametros - ¿Hay alguna alternativa al uso de%(módulo) en C/C++?

mod en dev c++

Question

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

¿Hay otra forma de hacer esto que no sea mantener una variable de contador y desbordamiento manual 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
}

vs:

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

Answer 1

¿Tiene acceso a cualquier hardware programable en el dispositivo incorporado? ¿Como contadores y tal? Si es así, es posible que pueda escribir una unidad de modulación basada en hardware, en lugar de usar el% simulado. (Lo hice una vez en VHDL. No estoy seguro de si todavía tengo el código).

Eso sí, dijiste que la división era 5-10 veces más rápida. ¿Has considerado hacer una división, multiplicación y sustracción 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 mod, son la misma operación).

En su caso específico, sin embargo, está buscando un mod de 6. 6 = 2 * 3. Por lo tanto, podría obtener algunas pequeñas ganancias si primero verificara si el bit menos significativo fuera 0. Algo como:

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

Sin embargo, si haces eso, te recomiendo confirmar que obtienes ganancias, yay para los perfiladores. Y haciendo algunos comentarios. Me sentiría mal por el siguiente tipo que tiene que mirar el código de otra manera.

Answer 2

@Jeff V: ¡Veo un problema con eso! (Más allá de eso, tu código original estaba buscando un mod 6 y ahora esencialmente estás buscando un mod 8). ¡Sigues haciendo un +1 extra! Esperemos que su compilador optimice eso, pero ¿por qué no simplemente probar el inicio en 2 e ir a MAXCOUNT inclusive? Finalmente, regresas cierto cada vez que (x + 1) NO es divisible entre 8. ¿Eso es lo que quieres? (Supongo que sí, pero solo quiero confirmarlo)

Answer 3

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

Answer 4

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

El código que se escribe torpemente para optimizar el rendimiento es difícil de depurar y difícil de mantener. Escribe un caso de prueba y perfúlalo en tu objetivo. Una vez que conozca el costo real del módulo, entonces decida si vale la pena codificar la solución alternativa.

Answer 5

Ah, las alegrías 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 en realidad debería ser más rápida que el módulo. Me interesa ver la fuente de donde obtuviste esta información. Los procesadores con multiplicadores tienen rutinas de división interesantes que usan el multiplicador, pero puede obtener desde el resultado de la división hasta el módulo con solo dos pasos más (multiplicar y restar), por lo que todavía es comparable. Si el procesador tiene una rutina de división incorporada, probablemente verá que también proporciona el resto.

Aún así, hay una pequeña rama de teoría de números dedicada a la Aritmética Modular que requiere estudio si realmente quieres entender cómo optimizar una operación de módulo. El aritmático modular, por ejemplo, es muy útil para generar cuadrados mágicos .

Entonces, en ese sentido, aquí hay un análisis de nivel muy bajo de la matemática del módulo para un ejemplo de x, que debería mostrar qué tan simple se puede comparar con la división:

Quizás una mejor manera de pensar sobre el problema sea en términos de número de bases y aritmética de módulo. Por ejemplo, su objetivo es calcular el 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 alto y bajo. Multiplique el resultado por el alto por 4 y agréguelo al valor bajo y luego calcule el resultado del módulo 7.

La computación del resultado del mod 7 de un número de 8 bits se puede realizar de forma similar. Puede escribir un número de 8 bits en octal como sigue:

  X = a*64 + b*8 + c

Donde a, byc 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 el 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 de 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 rutina de liitle 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

Answer 6

Deberías comprobar realmente el dispositivo integrado que necesitas. Todo el lenguaje ensamblador que he visto (x86, 68000) implementa el módulo usando 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.

Answer 7

En el mundo integrado, las operaciones de "módulo" que necesita hacer son a menudo las que se dividen fácilmente en operaciones de bits que puede hacer con ''&'' y ''|'' y a veces ''>>''.

Answer 8

Hay una sobrecarga en el uso del módulo que no son potencias de 2. Esto es independientemente del procesador como (AFAIK) incluso los procesadores con operadores de módulo son unos ciclos más lentos para dividir en oposición a las operaciones 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 de acceso directo (especialmente si aún implica dividir o multiplicar).

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

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

Answer 9

La instrucción de impresión tomará órdenes de magnitud mayor que incluso la implementación más lenta del operador de módulo. Entonces, 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 / n" nunca se imprime.

Answer 10

No es que esto sea necesariamente mejor, pero podrías tener un bucle interno que siempre sube a FIZZ, y un bucle externo que lo repite todo un cierto número de veces. Quizás haya llegado a un caso especial los últimos pasos si MAXCOUNT no es divisible por FIZZ.

Dicho esto, sugeriría investigar y perfilar el rendimiento en las plataformas para obtener una idea clara de las limitaciones de rendimiento que tiene. Puede haber lugares mucho más productivos para gastar su esfuerzo de optimización.

Answer 11

Si está calculando un número mod de alguna potencia de dos, puede usar el bit-wise y el operador. Solo resta uno del segundo número. Por ejemplo:

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

Algunas advertencias:

1. Esto solo funciona si el segundo número es una potencia de dos.
2. Es solo 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, lo que sí garantiza que será negativo, que es lo que la mayoría de los compiladores ya estaban haciendo). Un poco sabio y se deshace del bit de signo, por lo que siempre será positivo (es decir, es un verdadero módulo, no un residuo). Sin embargo, parece que eso es lo que quieres de todos modos.
3. Tu compilador probablemente ya hace esto cuando puede, por lo que en la mayoría de los casos no vale la pena hacerlo manualmente.

Answer 12

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

Espero que esto ayude.