No estoy preguntando cómo funciona el concepto matemático de módulo, o cómo 20 % 3 == 2 entiendo esto bien. Tengo más curiosidad por saber cómo el compilador / intérprete determina esto. Puedo pensar en una forma muy ingenua de hacerlo, así:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (obviamente, esto necesita algunos casos más porque a puede ser más pequeño que b, pero entiendes la idea). Pero esto tendría serios problemas de rendimiento. Reuní algo de C ++ para probar la eficiencia de ambos módulos operador y mi función ingenua.
#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"; } y el resultado es:
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. El El operador de módulo varió de 4,000 a 70,000 nanosegundos. Mi función siempre ganó en los números pequeños, pero tomó alrededor de 2 segundos en el número grande. Dado que el operador de módulo es mucho más consistente, supongo que compara el número en un nivel bit a bit.
Entonces, ¿cómo funciona el operador de módulo? Puedo pensar en algunos casos que serían muy fáciles de determinar. Por ejemplo, con el mod 2, puedes mirar el mismo último byte. O con el mod 4 puedes mirar desde el penúltimo b yte. Pero no todos los números tienen un patrón tan simple.
Comentarios
Respuesta
Casi todas las CPU tienen una sola instrucción que devolverá el módulo de un valor. Por ejemplo, considere este programa:
int main() { int i = 10; return i % 3; } Si compilo esto en mi máquina Intel OS X usando g ++ -S, el resultado será un texto repetitivo y esto:
movl $3, %eax movl $0, -4(%rbp) movl $10, -8(%rbp) movl -8(%rbp), %ecx movl %eax, -12(%rbp) ## 4-byte Spill movl %ecx, %eax cltd movl -12(%rbp), %ecx ## 4-byte Reload idivl %ecx movl %edx, %eax El módulo real ocurre con esta instrucción: idivl %ecx. Cuando se ejecuta esta instrucción, el cociente se colocará en %eax y el resto se colocará en %edx.
Dado que en realidad, esto significa que la operación % solo tomará unos pocos ciclos de reloj, la mayor parte de los cuales en realidad está moviendo los datos al registro correcto. También tenga en cuenta que con Intel al menos, la misma operación encuentra tanto el cociente como el resto, por lo que en referencia a su comentario, / y % tomar exactamente el mismo tiempo. Es la misma operación. Lo único que cambia es de qué registro obtiene el compilador los resultados.
Con cualquier CPU realizada en las últimas dos décadas, puede suponer que cualquier operación matemática básica (incluidas las cosas que parecen funciones de biblioteca como sqrt o cos) es en realidad una sola instrucción de máquina y generalmente solo toma unos pocos ciclos de reloj como máximo.
[ACTUALIZACIÓN]
Como la gente ha señalado en los comentarios, para ver algo que se acerca al momento correcto, necesita eliminar la salida de la sección cronometrada de esta manera:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Pero incluso eso probablemente no sea exacto, ya que la granularidad real de los tiempos puede exceder lo que está tratando de cronometrar. En su lugar, es posible que desee hacer esto:
int i=0; int x; auto start = Clock::now(); for(i=0;i<1000000;i++) x = i % 3; auto end = Clock::now(); cout << i << endl; Luego, divida su tiempo entre 1,000,000. (Esto será un poco alto ya que incluye el tiempo necesario para una tarea, una comparación y un incremento). En mi máquina, esto da un tiempo de 5 nanosegundos.
Comentarios
std::sqrt() incurre en una llamada a la biblioteca en la mayoría de los compiladores de C ++. std:sqrt normalmente estaría en línea (y usaría ensamblaje en línea). Pero ‘ nunca lo he verificado.
DIVyIDIV, que realizan la división de enteros, también almacenan el resto en un registro). ¿Está preguntando cómo funciona el hardware ?cout <<la mayoría de las operaciones. Dudo que puedas medir el tiempo que le toma al procesador20 % 3incluso si el compilador no ‘ lo hizo en tiempo de compilación de todos modos .