Warum ist eine division teurer ist als eine Multiplikation?
Ich bin nicht wirklich versucht, etwas optimieren, aber ich erinnere mich, dies zu hören, von Programmierern die ganze Zeit, ich nahm es als eine Wahrheit. Nachdem alle Sie sollen wissen, diese Dinge.
Aber ich Frage mich, warum ist die Teilung tatsächlich langsamer als Multiplikation? Ist das nicht die division nur ein besserer Subtraktion, und Multiplikation ist ein herrliches hinaus? Mathematisch So sehe ich nicht, warum geht die eine oder andere Weise hat rechnerisch sehr unterschiedliche Kosten.
Kann jemand bitte klären Sie den Grund/Ursache dafür, so weiß ich, anstelle von dem, was ich hörte von anderen Programmierer, die ich vor der Frage was bedeutet: "da".
[citation-needed]"After all they are supposed to know this stuff."- Sie werden überrascht sein, was die meisten Leute nicht wissen.- Suchen Sie für die Abteilung ist langsamer/teurer als die Multiplikation online, und Sie werden es überall sehen. Ich glaube nicht, dass irgendjemand behauptet, es ist nicht langsamer.
- Sie haben Fragen, ein Elektronik-Ingenieur, ist es, eine Schaltung design-problem. Erstellen eines hardware-Multiplizierer ist ziemlich einfach, eine hardware-divider ist nicht. Praktische Teiler-schaltungen iterativ sind und daher länger dauern. Fragen Sie an electronics.stackexchange.com
- Wikipedia (vgl. Artikel-FLOPS) und anderen Quellen (en.community.dell.com/techcenter/high-performance-computing/w/...) verlangen, dass typische CPUs ausführen können 4 Gleitkomma-Operationen pro Taktzyklus. Dies scheint unabhängig von der Art. Daraus folgt, dass diese Aufteilung wäre so teuer/Billig wie die Multiplikation. Die ehrenamtliche Arbeit zu tun, ein benchmark?
- Kurz gesagt: quotient Schätzung und Korrektur-Schritte.
- Du hast Recht, dass die Multiplikation zerfällt in mehrere Ergänzungen und Teilung zerfällt in mehrere Subtraktionen. Der Unterschied ist, dass die Ergänzungen bei der Multiplikation parallel durchgeführt werden können, in der Erwägung, dass in der Abteilung, die Sie nicht tun können, die nächste Subtraktion bis beenden die Vorherige ein und machen Sie einen Vergleich. So ein hardware-Multiplizierer wird das ausnutzen dieser inhärenten Parallelität durch Berechnung und Summierung viele sub-Produkte, die gleichzeitig auf Kosten von erhöhten Bereich real-estate. Division nicht über diesen Luxus.
- Mehrere jsperf-benchmarks existieren, z.B. jsperf.com/multiplication-vs-division-lars Die Ergebnisse variieren von 0 Unterschied zur Multiplikation 4x so schnell. Ich Frage mich, ob javascript-Optimierung untergräbt einige der tests, indem wir bemerken, dass der berechnete Wert wird nicht verwendet (damit die "control" - test-Fall).
- Warum ist die division so viel komplexer als andere arithmetische Operationen?, Warum funktioniert die hardware-Abteilung sehr viel länger dauern als die Multiplikation?
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
CPU ALU (Arithmetisch-logische Einheit) führt algorithmen aus, wenn Sie in hardware implementiert. Klassische Multiplikationen algorithmen enthält Wallace-Baum und Dadda-tree. Weitere Informationen finden hier. Mehr ausgefeilte Techniken, die verfügbar sind in neueren Prozessoren. Im Allgemeinen Prozessoren, die sich bemühen, zu parallelisieren bit-Paare von Operationen, um die Minimierung der Taktzyklen erforderlich. Multiplikation-algorithmen parallelisiert werden können Recht effektiv (obwohl mehr transistoren erforderlich sind.).
Division algorithmen können nicht parallelisiert werden als effizient. Die effiziente Aufteilung algorithmen sind sehr Komplex (Der Pentium-FDIV-bug zeigt den Grad der Komplexität). In der Regel werden Sie benötigt mehr Taktzyklen pro bit. Wenn Sie mehr technische details, hier ist eine schöne Erklärung von Intel. Intel tatsächlich patentierte Ihrer division Algorithmus.
Der große Unterschied ist, dass in einer long-Multiplikation, die Sie gerade brauchen, um hinzuzufügen, bis eine Reihe von zahlen nach der Verlagerung und der Maskierung. In einer division mit Rest musst du testen für überlauf nach jeder Subtraktion.
Betrachten wir eine lange Multiplikation von zwei n-bit-Binär-zahlen.
Aber wenn wir genauer hinschauen, es stellt sich heraus, können wir optimieren, indem Sie mit zwei tricks (es gibt noch weitere Optimierungen, aber diese sind die wichtigsten).
So, jetzt unser Algorithmus sieht wie
In anderen Worten, wir bauen ein Multiplikator für zwei n-bit-zahlen in Zeit etwa proportional zu n (und Raum in etwa proportional zu n2). Solange die CPU-designer ist bereit, zu widmen, die Logik der Multiplikation kann fast so schnell wie die addition.
In lange Teilung, müssen wir wissen, ob jeder Subtraktion übergelaufen, bevor wir entscheiden können, welche Eingänge für den nächsten. So können wir nicht die gleichen parallising tricks wie können wir mit long-Multiplikation.
Gibt es Methoden der Teilung, die sind schneller als die lange Teilung, aber Sie sind immer noch langsamer als eine Multiplikation.