Como funciona o módulo?

Não estou perguntando como funciona o conceito matemático de módulo ou como 20 % 3 == 2 entendo isso. Estou mais curioso para saber como o compilador / intérprete determina isso. Posso pensar em uma maneira muito ingênua de fazer isso, como:

int modulus(int a, int b) { while (a > b) { a -= b; } return a; } 

(obviamente, são necessários mais alguns casos porque a pode ser menor que b, mas você entendeu.) Mas isso teria alguns problemas sérios de desempenho. Eu juntei um pouco de C ++ para testar a eficiência de ambos os módulos operador e minha função ingênua.

#include <iostream> #include <chrono> #include <limits> #include "chrono_io" using namespace std; typedef chrono::high_resolution_clock Clock; int mod(int a, int b) { while (a > b) { a -= b; } return a; } int main() { auto start = Clock::now(); cout << 20 % 3 << endl; auto end = Clock::now(); cout << "Modulus on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << numeric_limits<int>::max() % 3 << endl; end = Clock::now(); cout << "Modulus on a large number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(20, 3) << endl; end = Clock::now(); cout << "My modulus function on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(numeric_limits<int>::max(), 3) << endl; end = Clock::now(); cout << "My modulus function on a large number took " << end - start << " seconds to calculate.\n"; } 

e a saída é:

2 Modulus on a small number took 43629 nanoseconds seconds to calculate. 1 Modulus on a large number took 5644 nanoseconds seconds to calculate. 2 My modulus function on a small number took 3682 nanoseconds seconds to calculate. 1 My modulus function on a large number took 2153824554 nanoseconds seconds to calculate. 

O O operador de módulo variou de 4.000 a 70.000 nanossegundos. Minha função sempre venceu nos números pequenos, mas levou cerca de 2 segundos no número grande. Como o operador de módulo é muito mais consistente, presumo que ele compare o número em um nível bit a bit.

Então, como funciona o operador de módulo? Posso pensar em alguns casos que seriam muito fáceis de determinar. Por exemplo, com o mod 2, você pode apenas olhar para o último byte. Ou com o mod 4 você pode olhar para o penúltimo b yte. Mas nem todos os números têm um padrão tão simples.

Comentários

• Em PCs, isso geralmente é feito em hardware (o x86 e IDIV, que realizam a divisão inteira, também armazenam o restante em um registro). Você está perguntando como o hardware faz isso?
• Leituras relacionadas: Linguagem Assembly – Como fazer Módulo?
• A divisão longa funciona da mesma forma com números binários e decimais. Experimente, depois pense em como codificá-lo (dica: você ‘ usará muitos turnos).
• @DJMcMayhem: Sim. Às vezes, o compilador precisa realizar alguns ajustes nos resultados para ficar em conformidade com a especificação da linguagem para aritmética assinada. Em geral, a velocidade da divisão do hardware é boa o suficiente para que, quando você não souber os valores de entrada no momento da compilação, seja melhor deixar o hardware fazer isso em vez da emulação do software. No entanto, se o divisor for conhecido em tempo de compilação, existem truques que podem ser executados mais rapidamente. Veja: isto e isto .
• Observe que a maneira como você estão cronometrando coisas; na verdade, você está apenas medindo o tempo que leva para cout << a maioria das operações. Duvido que você pudesse realmente medir o tempo que o processador leva para fazer 20 % 3 mesmo se o compilador não ‘ o fizesse em tempo de compilação de qualquer maneira .