Isabella, parte de este gran staff, nos hizo el favor de escribir este artículo porque conoce muy bien dicho tema.
Solución:
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 debería ser más rápida que el módulo. Me interesa saber de qué fuente obtuviste esta información. Los procesadores con multiplicadores tienen rutinas de división interesantes que usan el multiplicador, pero puede pasar del resultado de la división al módulo con solo otros dos pasos (multiplicar y restar), por lo que aún 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 la teoría de números dedicada a la aritmética modular que 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 mágicos.
Entonces, en ese sentido, aquí hay una mirada de muy bajo nivel a las matemáticas del módulo para un ejemplo de x, que debería mostrarle cuán simple puede ser en comparación con la división:
Quizás una mejor manera de pensar en 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 alto y bajo. Multiplica el resultado del máximo por 4 y súmalo al mínimo y finalmente calcula el resultado módulo 7.
El cálculo del resultado mod 7 de un número de 8 bits se puede realizar de manera similar. Puede 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
ya que 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 así:
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ías escribir:
uint16 Mod7Word(uint16 X)
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
scott
Si está calculando un número mod 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:
- Esta solo funciona si el segundo número es una potencia de dos.
- Solo 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 lo hace garantía de que será negativo, que es lo que la mayoría de los compiladores ya estaban haciendo). A bit-wise y se deshace del bit de signo, por lo que siempre será positivo (es decir, es un true módulo, no un resto). Sin embargo, parece que eso es lo que quieres.
- Su compilador probablemente ya hace esto cuando puede, por lo que en la mayoría de los casos no vale la pena hacerlo manualmente.
Hay una sobrecarga la mayor parte del tiempo en el uso de 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 en comparación con las operaciones de máscara.
Para 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 atajo (especialmente si todavía implica dividir o multiplicar).
Sin embargo, una regla general es seleccionar array tamaños, etc. para ser potencias de 2.
así que si calcula el día de la semana, también puede usar %7 independientemente de si configura 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
Aquí puedes ver las reseñas y valoraciones de los usuarios
Recuerda que tienes la capacidad de decir .