Ist die Multiplikation zweier Zahlen ein konstanter Zeitalgorithmus?

Question

Angenommen, ich schreibe,

int a = 111; 
int b = 509; 
int c = a * b; 

Also, was ist die Zeit, Komplexität 'a * b' zu berechnen? Wie wird die Multiplikation ausgeführt?

Answer 1

diese Funktion Kompilieren:

int f(int a, int b) { 
    return a * b; 
} 

Mit gcc -O3 -march=native -m64 -fomit-frame-pointer -S gibt mir die folgende Montage:

f: 
    movl %ecx, %eax 
    imull %edx, %eax 
    ret 

Der erste Befehl (movl) lädt das erste Argument, der zweite Befehl (imull) lädt die zweite Argument und multipliziert es mit dem ersten - dann wird das Ergebnis zurückgegeben.

Die eigentliche Multiplikation erfolgt mit imull, die je nach CPU-Typ eine bestimmte Anzahl an CPU-Zyklen benötigt. Wenn Sie Agner Fog's instruction timing tables ansehen, können Sie sehen, wie viel Zeit jede Anweisung benötigt. Auf den meisten x86-Prozessoren scheint es eine kleine Konstante zu sein, aber die imul-Anweisung auf dem AMD K8 mit einem 64-Bit-Argument und Ergebnis zeigt 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 führen zu einer Latenz, die auch in Agner Fogs Tabellen zu finden ist. Es gibt noch andere Probleme wie Cache-Probleme, die das Leben zusätzlich erschweren - es ist gar nicht so einfach zu sagen, wie schnell etwas läuft, ohne es laufen zu lassen.

---

x86 ist nicht die einzige Architektur, und es ist eigentlich nicht undenkbar, da CPUs sind und Architekturen aus, dass es nicht konstante Zeit Multiplikation 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.

Answer 2

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 zusätzliche Zyklen erfordern können, um eine bestimmte Genauigkeit zu erreichen.

Sie können Schulungskosten hier für AMD, Intel, VIA erhalten: http://www.agner.org/optimize/instruction_tables.pdf

Answer 3

void myfun() 
{ 
int a = 111; 
int b = 509; 
int c = a * b; 
} 

De montieren Teil:

movl $111, -4(%ebp) 
movl $509, -8(%ebp) 
movl -4(%ebp), %eax 
imull -8(%ebp), %eax 

So wie Sie es hängt alles von imull Anweisung sehen können, insbesondere die Zyklus einer CPU holen, dekodieren und ausführen.

Answer 4

Nach Zeit Komplexität nehme ich an, Sie meinen, ob es von der Anzahl der Stellen 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 gibt, dies zu tun, ist eine einfache/primitive Methode, die Multiplikation mit der binary adder/subtractor Schaltung zu implementieren. Die Multiplikation von a * b addiert sich zu 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.

Answer 5

In Ihrem Beispiel der Compiler die Multiplikation und Ihr Code würde wie

int c = 56499; 

tun würde aussehen Wenn Sie Ihr Beispiel wie

int c = a * 509; 

dann der Compiler neu schreiben können entscheiden, ob Sie die geändert Ihre Code wie

int c = a * (512 - 2 - 1); 
int c = (a << 9) - (a << 1) - a; 

Ich sagte vielleicht, weil der Compiler die Kosten vergleichen wird Verwenden Sie das Hemd zu den Kosten einer Multiplikation und wählen Sie die beste Option. 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 verwenden die mathematischen Routinen mit beliebiger Genauigkeit zwischen O (n^2) und O (n log n) Zeit, wobei n die Zahl 32 ist -Bit Teile benötigt, um die Zahlen zu halten.