Warum ist Multiplizieren billiger als Dividieren?

Question

Ich schrieb vor kurzem eine Vector 3-Klasse, und ich legte meine normalize() -Funktion für die Überprüfung an einen Freund. Er sagte, es sei gut, aber ich solle mich mit dem Kehrwert multiplizieren, wo es möglich sei, weil "Multiplizieren ist billiger als Dividieren" in der CPU-Zeit.

Meine Frage ist einfach, warum ist das?

Answer 1

Denken Sie über Elementaroperationen nach, die die Hardware leichter implementieren kann - addieren, subtrahieren, verschieben, vergleichen. Die Multiplikation selbst in einer trivialen Anordnung erfordert weniger solche elementaren Schritte - und sie bietet fortschrittliche Algorithmen, die noch schneller sind - siehe zum Beispiel here ... aber die Hardware nutzt diese im Allgemeinen nicht aus (außer vielleicht extrem spezialisierte Hardware). Zum Beispiel, wie die Wikipedia-URL sagt, "Toom-Cook kann eine Größe N gewürfelte Multiplikation für die Kosten von fünf Größe-N-Multiplikationen tun" - das ist ziemlich schnell für sehr große Zahlen (Fürers Algorithmus, eine ziemlich neue Entwicklung, kann Θ(n ln(n) 2Θ(ln*(n))) - wieder, siehe die Wikipedia-Seite und Links davon.

Division ist nur intrinsisch langsamer, als - wieder - per wikipedia; selbst die besten Algorithmen (von denen einige in HW implementiert sind, nur weil sie nirgendwo so hoch entwickelt und komplex sind wie die besten Algorithmen zur Multiplikation ;-) können den Multiplikatoren nicht das Wasser reichen.

Nur um das Problem mit nicht so großen Zahlen zu quantifizieren, hier sind einige Ergebnisse mit gmpy, eine einfach zu bedienende Python-Wrapper um GMP, die tendenziell ziemlich gute Implementierungen von Arithmetik, obwohl nicht unbedingt die neuesten haben und-größte Keuchen. Auf einem langsamen (erste Generation ;-) Macbook Pro:

$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib' 
1000000 loops, best of 3: 0.186 usec per loop 
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b' 
1000000 loops, best of 3: 0.276 usec per loop 

Wie Sie selbst bei dieser geringen Größe (Anzahl der Bits in den Zahlen) zu sehen, und mit Bibliotheken optimiert, indem genau die gleiche Geschwindigkeit besessenen Menschen Multiplikation mit dem Kehrwert kann 1/3 der Zeit, die die Division benötigt, einsparen.

Es kann nur in seltenen Fällen, dass diese wenigen Nanosekunden sind ein Leben oder Tod Thema, aber, wenn sie sind, und natürlich, wenn Sie sich teilen wiederholt um den gleichen Wert (um die 1.0/b zu amortisieren weg Operation!), dann kann dieses Wissen ein Lebensretter sein.

(Much in der gleichen Ader - x*x wird oft Zeit im Vergleich zu x**2 [in Sprachen, die einen ** „erhöhen, um Macht“ Operator, wie Python und Fortran haben] speichern - und Horner-scheme für Polynomberechnung Fall vorziehen zu wiederholten Raise-to-Power-Operationen! -).

Answer 2

Die CPU-Operation für (float) Division ist viel komplizierter als Multiplikation. Die CPU muss mehr tun. Ich bin weit davon entfernt, über Hardware Bescheid zu wissen, aber Sie können eine Menge Informationen über die gemeinsame Implementierung von Abteilungen finden (basierend auf newton-raphson Algorithmen zum Beispiel).

Ich würde auch darauf achten, immer die Multiplikation der reziproken anstelle der Division zu verwenden, um CPU-Leistung zu gewinnen: sie geben möglicherweise nicht genau die gleichen Ergebnisse. Dies kann abhängig von Ihrer Anwendung sein oder nicht.

Answer 3

Wenn Sie an die Grundschule denken, erinnern Sie sich, dass die Multiplikation schwieriger war als die Addition und die Division schwieriger als die Multiplikation war. Die Dinge sind nicht anders für die CPU.

Erinnern Sie sich auch daran, dass die Berechnung des Reziproken eine Division beinhaltet. Wenn Sie also das Reziproke nicht einmal berechnen und dreimal verwenden, sehen Sie keine Beschleunigung.