Existe alguma alternativa para usar% (módulo) em C/C++?
https://stackoverflow.com/questions/48053
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Li em algum lugar uma vez que o operador de módulo é ineficiente em pequenos dispositivos incorporados, como microcontroladores de 8 bits, que não possuem instruções de divisão inteira.Talvez alguém possa confirmar isso, mas pensei que a diferença fosse 5 a 10 vezes mais lenta do que com uma operação de divisão inteira.
Existe outra maneira de fazer isso além de manter uma variável de contador e transbordar manualmente para 0 no ponto mod?
const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}
contra:
A maneira como estou fazendo atualmente:
const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
if(fizzcount >= FIZZ)
{
print("Fizz\n");
fizzcount = 0;
}
}
Solução
Ah, as alegrias da aritmética bit a bit.Um efeito colateral de muitas rotinas de divisão é o módulo - portanto, em alguns casos, a divisão deve ser realmente mais rápida que o módulo.Estou interessado em ver a fonte de onde você obteve essas informações.Processadores com multiplicadores têm rotinas de divisão interessantes usando o multiplicador, mas você pode passar do resultado da divisão ao módulo com apenas mais duas etapas (multiplicar e subtrair), para que ainda seja comparável.Se o processador tiver uma rotina de divisão integrada, você provavelmente verá que ele também fornece o restante.
Ainda assim, existe um pequeno ramo da teoria dos números dedicado a Aritmética Modular o que requer estudo se você realmente deseja entender como otimizar uma operação de módulo.A aritmática modular, por exemplo, é muito útil para gerar quadrados mágicos.
Então, nesse sentido, aqui está um aparência de nível muito baixo na matemática do módulo para obter um exemplo de x, que deve mostrar como isso pode ser simples comparado à divisão:
Talvez uma maneira melhor de pensar sobre o problema seja em termos de bases de números e aritmética de módulo.Por exemplo, seu objetivo é calcular o Dow Mod 7, onde a Dow é a representação de 16 bits do dia da semana.Você pode escrever isso 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
Expressa dessa maneira, você pode calcular separadamente o resultado do Modulo 7 para os bytes altos e baixos.Multiplique o resultado da alta por 4 e adicione -o à baixa e, finalmente, calcule o Módulo 7 de resultado.
A computação do resultado MOD 7 de um número de 8 bits pode ser realizada de maneira semelhante.Você pode escrever um número de 8 bits em octal assim:
X = a*64 + b*8 + c
Onde a, b e c são 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
É claro que a, b e c são
c = X & 7
b = (X>>3) & 7
a = (X>>6) & 7 // (actually, a is only 2-bits).
O maior valor possível para a+b+c é 7+7+3 = 17.Então, você precisará de mais uma etapa octal.A versão completa (não testada) C poderia ser escrita 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;
}
Passei alguns momentos escrevendo uma versão PIC.A implementação real é um pouco diferente da descrita acima
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
Aqui está uma pequena rotina para testar o 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 o resultado de 16 bits (que não testei), você pode escrever:
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
Scott
Outras dicas
Se você estiver calculando um mod numérico com alguma potência de dois, poderá usar o operador bit a bit e.Basta subtrair um do segundo número.Por exemplo:
x % 8 == x & 7
x % 256 == x & 255
Algumas advertências:
- Esse só funciona se o segundo número for uma potência de dois.
- Só é equivalente se o módulo for sempre positivo.Os padrões C e C++ não especificam o sinal do módulo quando o primeiro número é negativo (até C++ 11, que faz garanto que será negativo, que é o que a maioria dos compiladores já estava fazendo).Um bit a bit e elimina o bit de sinal, então sempre será positivo (ou seja,é um módulo verdadeiro, não um resto).Parece que é isso que você quer de qualquer maneira.
- Seu compilador provavelmente já faz isso quando pode, então na maioria dos casos não vale a pena fazer isso manualmente.
Na maioria das vezes, há uma sobrecarga no uso de módulos que não são potências de 2.Isso independentemente do processador, pois (AFAIK), mesmo os processadores com operadores de módulo são alguns ciclos mais lentos para divisão em oposição às operações de máscara.
Na maioria dos casos, esta não é uma otimização que valha a pena considerar e certamente não vale a pena calcular sua própria operação de atalho (especialmente se ainda envolver divisão ou multiplicação).
No entanto, uma regra prática é selecionar tamanhos de array, etc.ser potências de 2.
Portanto, se calcular o dia da semana, também poderá usar %7, independentemente de configurar um tampão circular de cerca de 100 entradas ...por que não fazer 128.Você pode então escrever% 128 e a maioria (todos) os compiladores farão isso & 0x7F
A menos que você realmente precise de alto desempenho em múltiplas plataformas incorporadas, não altere a forma como você codifica por motivos de desempenho até criar o perfil!
O código escrito de maneira inadequada para otimizar o desempenho é difícil de depurar e manter.Escreva um caso de teste e crie um perfil dele em seu destino.Depois de saber o custo real do módulo, decida se vale a pena codificar a solução alternativa.
@ Mateus está certo.Experimente isto:
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 isto ajude.
No mundo incorporado, as operações de "módulo" que você precisa fazer são frequentemente as que dividem muito bem em operações que você pode fazer com '&' e '|' ' E às vezes '>>'.
Você tem acesso a algum hardware programável no dispositivo incorporado?Como contadores e tal?Nesse caso, você poderá escrever uma unidade mod baseada em hardware, em vez de usar% simulado.(Eu fiz isso uma vez em VHDL.Não tenho certeza se ainda tenho o código.)
Veja bem, você disse que a divisão era 5 a 10 vezes mais rápida.Você já pensou em fazer divisão, multiplicação e subtração para simular o mod?(Editar:Não entendi a postagem original.Achei estranho que a divisão fosse mais rápida que o mod, eles são a mesma operação.)
No seu caso específico, porém, você está verificando um mod de 6.6 = 2*3.Então você TALVEZ poderia obter alguns pequenos ganhos se primeiro verificasse se o bit menos significativo era 0.Algo como:
if((!(x & 1)) && (x % 3))
{
print("Fizz\n");
}
Se você fizer isso, recomendo confirmar se você obtém algum ganho, oba para os criadores de perfil.E fazendo alguns comentários.Eu me sentiria mal pelo próximo cara que tivesse que olhar o código de outra forma.
Você realmente deve verificar o dispositivo incorporado de que precisa.Toda a linguagem assembly que vi (x86, 68000) implementa o módulo usando uma divisão.
Na verdade, a operação de montagem da divisão retorna o resultado da divisão e o restante em dois registros diferentes.
Não que isso seja necessariamente melhor, mas você poderia ter um loop interno que sempre vai até FIZZ e um loop externo que repete tudo um certo número de vezes.Talvez você tenha que passar por um caso especial nas etapas finais se MAXCOUNT não for divisível igualmente por FIZZ.
Dito isso, sugiro fazer algumas pesquisas e criar perfis de desempenho nas plataformas pretendidas para ter uma ideia clara das restrições de desempenho que você enfrenta.Pode haver lugares muito mais produtivos para gastar seu esforço de otimização.
@Jeff V:Vejo um problema nisso!(Além disso, seu código original estava procurando um mod 6 e agora você está essencialmente procurando um mod 8).Você continua fazendo um +1 extra!Esperamos que seu compilador otimize isso, mas por que não apenas o teste começa em 2 e vai para MAXCOUNT inclusive?Finalmente, você retorna verdadeiro sempre que (x+1) NÃO é divisível por 8.É isso que você quer?(Presumo que sim, mas só quero confirmar.)
Para o módulo 6 você pode alterar o código Python para C/C++:
def mod6(number):
while number > 7:
number = (number >> 3 << 1) + (number & 0x7)
if number > 5:
number -= 6
return number
A instrução print levará muito mais tempo do que a implementação mais lenta do operador de módulo.Então, basicamente, o comentário "lento em alguns sistemas" deveria ser "lento em todos os sistemas".
Além disso, os dois trechos de código fornecidos não fazem a mesma coisa.Na segunda, a linha
if(fizzcount >= FIZZ)
é sempre falso, então "FIZZ " nunca é impresso.
