Je ne demande pas comment fonctionne le concept mathématique de module, ou comment 20 % 3 == 2 Je comprends cela bien. Je suis plus curieux de savoir comment le compilateur / interpréteur détermine cela. Je peux penser à une manière très naïve de le faire, comme ceci:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (évidemment, cela nécessite quelques cas de plus car a peut être plus petit que b, mais vous voyez lidée.) Mais cela aurait de sérieux problèmes de performances. Jai rassemblé du C ++ pour tester lefficacité des deux modules et ma fonction naïve.
#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"; } et le résultat est:
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. Le Lopérateur de module variait de 4 000 à 70 000 nanosecondes. Ma fonction gagnait toujours sur les petits nombres, mais prenait environ 2 secondes sur le grand nombre. Puisque lopérateur de module est tellement plus cohérent, je suppose quil compare le nombre au niveau du bit.
Alors, comment fonctionne lopérateur de module? Je peux penser à des cas qui seraient très faciles à déterminer. Par exemple, avec le mod 2, vous pouvez simplement regarder dernier octet. Ou avec le mod 4, vous pouvez regarder lavant-dernier b yte. Mais tous les nombres nont pas un modèle aussi simple.
Commentaires
Réponse
Presque tous les processeurs ont une seule instruction qui retournera le module dune valeur. Par exemple, considérez ce programme:
int main() { int i = 10; return i % 3; } Si je compile ceci sur ma machine Intel OS X en utilisant g ++ -S, le résultat sera un passe-partout et ceci:
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 Le module réel se produit avec cette instruction: idivl %ecx. Lorsque cette instruction sexécute, le quotient sera placé dans %eax et le reste sera placé dans %edx.
Puisque vraiment, cela signifie que lopération % ne prendra que quelques cycles dhorloge, dont lessentiel consiste à déplacer les données dans le bon registre. Notez également quavec Intel au moins, la même opération trouve à la fois le quotient et le reste, donc en référence à votre commentaire, / et % prendre exactement le même temps. Cest la même opération. La seule chose qui change est de quel registre le compilateur obtient les résultats.
Avec nimporte quel processeur créé au cours des deux dernières décennies, vous pouvez supposer que toute opération mathématique de base (y compris des choses qui ressemblent à des fonctions de bibliothèque comme sqrt ou cos) est en fait une seule instruction machine et ne prend généralement que quelques cycles dhorloge au maximum.
[UPDATE]
Comme les gens lont noté dans les commentaires, pour voir quelque chose se rapprochant dun timing correct, vous besoin de supprimer la sortie de la section chronométrée comme ceci:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Mais même cela nest probablement pas précis car la granularité réelle des horaires peut dépasser ce que vous êtes essayer de chronométrer. Au lieu de cela, vous voudrez peut-être faire ceci:
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; Puis divisez votre timing par 1 000 000. (Ce sera légèrement élevé car il inclut le temps nécessaire pour une affectation, une comparaison et un incrément.) Sur ma machine, cela donne un temps de 5 nanosecondes.
Commentaires
- Vraiment? On ma dit que sqrt est une instruction très lente.
- Voir stackoverflow.com / questions / 7724061 / …
- @StevenBurnap cette réponse est un peu dépassée, basée sur larchitecture de lannée 2011. Daprès Agner Fog ‘, qui est mise à jour au moins une fois par an , instructions Haswell SSE2 SQRTSS / SQRTPS (flottant 32 bits, avec 23 bits de signification) a une latence de 11 cycles, SQRTSD / SQRTPD (flottant 64 bits) a une latence de 16 cycles. Ces instructions sont les plus précises, cest-à-dire non des variantes dapproximation rapide. Cest en effet beaucoup plus lent dans les anciennes architectures. Gardez également à lesprit que lappel de
std::sqrt()entraîne un appel de bibliothèque dans la plupart des compilateurs C ++. - Les compilateurs peuvent en outre appliquer loptimisation de la réduction de la force pour des cas particuliers. Par exemple, x% 2 pourrait être optimisé pour un masque de bits si ‘ est plus rapide sur une architecture spécifique.
- @rwong Jaurais pensé que
std:sqrtserait généralement en ligne (et utiliserait lassemblage en ligne.) Mais je ‘ nai jamais vérifié.
IDIV, qui effectuent une division entière, stockent également le reste dans un registre). Demandez-vous comment le matériel fait-il?cout <<la plupart des opérations. Je doute que vous puissiez réellement mesurer le temps quil faut au processeur pour faire20 % 3même si le compilateur na ‘ pas le faire au moment de la compilation de toute façon .