Wie funktioniert der Modul?

Ich frage nicht, wie das mathematische Konzept des Moduls funktioniert oder wie 20 % 3 == 2 Ich verstehe das gut. Ich bin neugieriger, wie der Compiler / Interpreter dies feststellt. Ich kann mir einen sehr naiven Weg vorstellen, dies so zu tun:

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

(dies erfordert natürlich einige weitere Fälle, da a kleiner als b sein kann, aber Sie haben die Idee.) Dies hätte jedoch einige schwerwiegende Leistungsprobleme zur Folge. Ich habe C ++ zusammengestellt, um die Effizienz beider Module zu testen Operator und meine naive Funktion.

#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"; } 

und die Ausgabe lautet:

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. 

Die Der Moduloperator variierte zwischen 4.000 und 70.000 Nanosekunden. Meine Funktion gewann immer bei den kleinen Zahlen, dauerte aber bei den großen Zahlen ungefähr 2 Sekunden. Da der Moduloperator so viel konsistenter ist, gehe ich davon aus, dass er die Zahl auf bitweiser Ebene vergleicht.

Wie funktioniert der Moduloperator? Ich kann mir einige Fälle vorstellen, die sehr einfach zu bestimmen wären. Mit Mod 2 können Sie beispielsweise nur die sehr genau betrachten letztes Byte. Oder mit Mod 4 kannst du dir das vorletzte ansehen b yte. Aber nicht alle Zahlen haben ein so einfaches Muster.

Kommentare

• Auf PCs erfolgt dies im Allgemeinen in Hardware (x86 DIV und IDIV Anweisungen, die eine Ganzzahldivision ausführen, speichern auch den Rest in einem Register. Fragen Sie, wie die Hardware funktioniert?
• Verwandte Lektüre: Assemblersprache – Wie wird Modulo ausgeführt?
• Die lange Division funktioniert bei Binärzahlen genauso wie bei Dezimalzahlen. Probieren Sie es aus und überlegen Sie, wie Sie es codieren könnten (Hinweis: ‚ wird viele Schichten verwenden).
• @DJMcMayhem: Ja. Manchmal muss der Compiler einige Anpassungen an den Ergebnissen vornehmen, um der Sprachspezifikation für signierte Arithmetik zu entsprechen. Im Allgemeinen ist die Geschwindigkeit der Hardwareteilung so gut, dass es besser ist, die Hardware dies anstelle der Software-Emulation tun zu lassen, wenn Sie die Eingabewerte zur Kompilierungszeit nicht kennen. Wenn der Divisor jedoch zur Kompilierungszeit bekannt ist, gibt es Tricks, die schneller ausgeführt werden können. Siehe: this und this .
• Beachten Sie, dass Sie so sind Timing-Dinge, die Sie wirklich nur messen, wie lange es dauert, cout << die meisten Operationen durchzuführen. Ich bezweifle, dass Sie tatsächlich die Zeit messen können, die der Prozessor benötigt, um 20 % 3 auszuführen, selbst wenn der Compiler ‚ dies sowieso nicht zur Kompilierungszeit getan hat .