Angenommen, ich schreibe
%Vor%Was ist also die zeitliche Komplexität, um 'a * b' zu berechnen? Wie wird die Multiplikation ausgeführt?
Kompilieren dieser Funktion:
%Vor% Mit gcc -O3 -march=native -m64 -fomit-frame-pointer -S bekomme ich folgende Assembly:
Der erste Befehl ( movl ) lädt das erste Argument, der zweite Befehl ( imull ) lädt das zweite Argument und multipliziert es mit dem ersten - dann wird das Ergebnis zurückgegeben.
Die eigentliche Multiplikation erfolgt mit imull , was - abhängig von Ihrem CPU-Typ - eine gewisse Anzahl an CPU-Zyklen erfordert.
Wenn Sie Agner Fogs Anweisungs-Timing-Tabellen sehen, können Sie sehen, wie viel Zeit jede Anweisung benötigt. Auf den meisten x86-Prozessoren scheint es eine kleine Konstante zu sein, jedoch zeigt der imul -Befehl auf dem AMD K8 mit einem 64-Bit-Argument und einem Ergebnis als 4-5 CPU-Zyklen. Ich weiß nicht, ob das ein Messproblem oder eine wirklich variable Zeit ist.
Beachten Sie auch, dass andere Faktoren als nur die Ausführungszeit beteiligt sind. Die Ganzzahl muss durch den Prozessor bewegt werden und an die richtige Stelle kommen, um multipliziert zu werden. All dies und andere Faktoren sorgen für eine Latenz, die auch in Agner Fogs Tabellen zu finden ist. Es gibt noch andere Probleme wie Cache-Probleme, die das Leben auch erschweren - es ist nicht so einfach zu sagen, wie schnell etwas läuft, ohne es auszuführen.
x86 ist nicht die einzige Architektur, und es ist eigentlich nicht unvorstellbar, dass es CPUs und Architekturen gibt, die eine nicht konstante Zeitmultiplikation haben. Dies ist besonders wichtig für die Kryptographie, wo Algorithmen, die Multiplikation verwenden, anfällig für Timing-Angriffe auf diese Plattformen sein können.
Die Multiplikation selbst auf den meisten gängigen Architekturen wird konstant sein. Die Zeit zum Laden von Registern kann abhängig von der Position der Variablen (L1, L2, RAM usw.) variieren, aber die Anzahl der Zyklen, die benötigt werden, ist konstant. Dies steht im Gegensatz zu Operationen wie sqrt , die möglicherweise zusätzliche Zyklen erfordern, um eine bestimmte Genauigkeit zu erreichen.
Hier erhalten Sie die Kosten für die Einführung von AMD, Intel, VIA: Ссылка
Nach der Komplexität der Zeit nehme ich an, Sie meinen, ob es von der Anzahl der Ziffern in a und b abhängt? Also, ob die Anzahl der CPU-Taktzyklen variieren würde, abhängig davon, ob Sie zB 2 * 3 oder 111 * 509 multiplizieren. Ich denke, ja, sie würden variieren und es würde davon abhängen, wie diese Architektur die Multiplikationsoperation implementiert und wie die Zwischenergebnisse gespeichert werden. Obwohl es viele Möglichkeiten geben kann, dies zu tun, ist eine einfache / primitive Methode die Multiplikation mit der Binäraddierer / Subtrahierer -Schaltung zu implementieren. Die Multiplikation von a * b addiert a zu sich selbst b mal mit n-stelligen Binäraddierern. In ähnlicher Weise ist die Division a / b die Subtraktion b von a, bis sie 0 erreicht, obwohl dies mehr Platz benötigt, um den Quotienten und den Rest zu speichern.
In Ihrem Beispiel würde der Compiler die Multiplikation durchführen und Ihr Code würde wie
aussehen %Vor%Wenn Sie Ihr Beispiel so geändert haben, dass es wie folgt aussieht
%Vor%dann könnte der Compiler MIGHT beschließen, Ihren Code wie
umzuschreiben %Vor%Ich sagte vielleicht, weil der Compiler die Kosten der Verwendung von T-Shirt mit den Kosten einer Multiplikationsanweisung vergleicht und die beste Option auswählt. Bei einer schnellen Mehrfachinstruktion bedeutet das normalerweise, dass nur 1 oder 2 Schichten schneller sind.
Wenn Ihre Zahlen zu groß sind, um in eine ganze Zahl (32 Bits) zu passen, dann ist die Genauigkeit beliebig mathematische Routinen verwenden zwischen O (n ^ 2) und O (n log n) -Zeit, wobei n die Anzahl der 32-Bit-Teile ist, die benötigt werden, um die Zahlen zu halten.