Soll ich Multiplikation oder Division verwenden?

Hier ist eine dumme lustige Frage:

Angenommen, wir müssen eine einfache Operation ausführen, bei der wir die Hälfte des Werts einer Variablen benötigen. Es gibt normalerweise zwei Möglichkeiten, dies zu tun:

y = x / 2.0;
// or...
y = x * 0.5;

Angenommen, wir verwenden die mit der Sprache gelieferten Standardoperatoren. Welche hat eine bessere Leistung?

Ich vermute, Multiplikation ist normalerweise besser, also versuche ich, mich beim Codieren daran zu halten, aber ich möchte dies bestätigen.

Obwohl ich persönlich an der Antwort für Python 2.4-2.5 interessiert bin , können Sie auch eine Antwort für andere Sprachen posten! Und wenn Sie möchten, können Sie auch andere ausgefallenere Methoden (wie die Verwendung von bitweisen Verschiebungsoperatoren) veröffentlichen.

Python:

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0'
real    0m26.676s
user    0m25.154s
sys     0m0.076s

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5'
real    0m17.932s
user    0m16.481s
sys     0m0.048s

Die Multiplikation ist 33% schneller

Lua:

time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m7.956s
user    0m7.332s
sys     0m0.032s

time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m7.997s
user    0m7.516s
sys     0m0.036s

=> kein wirklicher Unterschied

LuaJIT:

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m1.921s
user    0m1.668s
sys     0m0.004s

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m1.843s
user    0m1.676s
sys     0m0.000s

=> es ist nur 5% schneller

Schlussfolgerungen: In Python ist das Multiplizieren schneller als das Teilen. Wenn Sie sich jedoch mit fortgeschritteneren VMs oder JITs der CPU nähern, verschwindet der Vorteil. Es ist durchaus möglich, dass eine zukünftige Python-VM dies irrelevant macht

Verwenden Sie immer das, was am klarsten ist. Alles andere, was Sie tun, ist, den Compiler zu überlisten. Wenn der Compiler überhaupt intelligent ist, wird er das Beste tun, um das Ergebnis zu optimieren, aber nichts kann den nächsten dazu bringen, Sie nicht für Ihre beschissene Bitshifting-Lösung zu hassen (ich liebe Bit-Manipulation übrigens, es macht Spaß. Aber Spaß! = Lesbar )

Vorzeitige Optimierung ist die Wurzel allen Übels. Denken Sie immer an die drei Optimierungsregeln!

1. Nicht optimieren.
2. Wenn Sie ein Experte sind, lesen Sie Regel 1

3. Wenn Sie ein Experte sind und die Notwendigkeit rechtfertigen können, gehen Sie wie folgt vor:

   • Code es nicht optimiert
   • Bestimmen, wie schnell "Schnell genug" ist - Beachten Sie, welche Benutzeranforderung / Story diese Metrik erfordert.
   • Schreiben Sie einen Geschwindigkeitstest
   • Vorhandenen Code testen - Wenn er schnell genug ist, sind Sie fertig.
   • Rekodiere es optimiert
   • Testen Sie den optimierten Code. WENN es nicht der Metrik entspricht, werfen Sie es weg und behalten Sie das Original.
   • Wenn es den Test erfüllt, behalten Sie den Originalcode als Kommentar bei

Dinge wie das Entfernen innerer Schleifen, wenn sie nicht benötigt werden, oder das Auswählen einer verknüpften Liste über einem Array für eine Einfügesortierung sind keine Optimierungen, sondern nur Programmieren.

Ich denke, das wird so pingelig, dass Sie besser tun sollten, was auch immer den Code lesbarer macht. Ich bezweifle, dass irgendjemand den Unterschied jemals bemerken wird, es sei denn, Sie führen die Operationen tausende, wenn nicht millionenfach durch.

Wenn Sie wirklich die Wahl treffen müssen, ist Benchmarking der einzige Weg. Finden Sie heraus, welche Funktionen Ihnen Probleme bereiten, finden Sie heraus, wo in der Funktion die Probleme auftreten, und beheben Sie diese Abschnitte. Ich bezweifle jedoch immer noch, dass eine einzige mathematische Operation (selbst eine, die viele, viele Male wiederholt wurde) eine Ursache für einen Engpass sein würde.

Die Multiplikation ist schneller, die Division genauer. Sie verlieren etwas an Präzision, wenn Ihre Zahl keine Zweierpotenz ist:

y = x / 3.0;
y = x * 0.333333;  // how many 3's should there be, and how will the compiler round?

Selbst wenn Sie den Compiler die invertierte Konstante mit perfekter Genauigkeit herausfinden lassen, kann die Antwort dennoch unterschiedlich sein.

x = 100.0;
x / 3.0 == x * (1.0/3.0)  // is false in the test I just performed

Das Geschwindigkeitsproblem spielt wahrscheinlich nur in C / C ++ - oder JIT-Sprachen eine Rolle, und selbst dann nur, wenn sich die Operation in einer Schleife mit einem Engpass befindet.

Wenn Sie Ihren Code optimieren möchten, aber dennoch klar sind, versuchen Sie Folgendes:

y = x * (1.0 / 2.0);

Der Compiler sollte in der Lage sein, die Teilung zur Kompilierungszeit durchzuführen, damit Sie zur Laufzeit eine Multiplikation erhalten. Ich würde erwarten, dass die Präzision die gleiche ist wie in dery = x / 2.0 Fall.

Wo dies von Bedeutung sein kann, befindet sich ein LOT in eingebetteten Prozessoren, in denen eine Gleitkommaemulation erforderlich ist, um die Gleitkomma-Arithmetik zu berechnen.

Ich werde nur etwas für die Option "Andere Sprachen" hinzufügen.
C: Da dies nur eine akademische Übung ist, die wirklich keinen Unterschied macht, dachte ich, ich würde etwas anderes beitragen.

Ich habe ohne Optimierungen zur Montage kompiliert und mir das Ergebnis angesehen.
Der Code:

int main() {

    volatile int a;
    volatile int b;

    asm("## 5/2\n");
    a = 5;
    a = a / 2;

    asm("## 5*0.5");
    b = 5;
    b = b * 0.5;

    asm("## done");

    return a + b;

}

zusammengestellt mit gcc tdiv.c -O1 -o tdiv.s -S

die Division durch 2:

movl    $5, -4(%ebp)
movl    -4(%ebp), %eax
movl    %eax, %edx
shrl    $31, %edx
addl    %edx, %eax
sarl    %eax
movl    %eax, -4(%ebp)

und die Multiplikation mit 0,5:

movl    $5, -8(%ebp)
movl    -8(%ebp), %eax
pushl   %eax
fildl   (%esp)
leal    4(%esp), %esp
fmuls   LC0
fnstcw  -10(%ebp)
movzwl  -10(%ebp), %eax
orw $3072, %ax
movw    %ax, -12(%ebp)
fldcw   -12(%ebp)
fistpl  -16(%ebp)
fldcw   -10(%ebp)
movl    -16(%ebp), %eax
movl    %eax, -8(%ebp)

Als ich diese ints jedoch in ändertedouble s (was Python wahrscheinlich tun würde), bekam ich Folgendes:

Aufteilung:

flds    LC0
fstl    -8(%ebp)
fldl    -8(%ebp)
flds    LC1
fmul    %st, %st(1)
fxch    %st(1)
fstpl   -8(%ebp)
fxch    %st(1)

Multiplikation:

fstpl   -16(%ebp)
fldl    -16(%ebp)
fmulp   %st, %st(1)
fstpl   -16(%ebp)

Ich habe keinen dieser Codes bewertet, aber wenn Sie den Code untersuchen, können Sie feststellen, dass die Division durch 2 bei Verwendung von ganzen Zahlen kürzer ist als die Multiplikation mit 2. Bei der Verwendung von Doubles ist die Multiplikation kürzer, da der Compiler die Gleitkomma-Opcodes des Prozessors verwendet wahrscheinlich schneller laufen (aber eigentlich weiß ich es nicht) als sie nicht für den gleichen Vorgang zu verwenden. Letztendlich hat diese Antwort gezeigt, dass die Leistung der Multiplikation mit 0,5 gegenüber der Division durch 2 von der Implementierung der Sprache und der Plattform abhängt, auf der sie ausgeführt wird. Letztendlich ist der Unterschied vernachlässigbar und sollte Sie sich so gut wie nie Sorgen machen, außer in Bezug auf die Lesbarkeit.

Als Randnotiz können Sie sehen, dass in meinem Programm main()zurückkehrt a + b. Wenn ich das flüchtige Schlüsselwort wegnehme, werden Sie nie erraten, wie die Assembly aussieht (mit Ausnahme des Programm-Setups):

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

es hat sowohl die Division, Multiplikation als auch Addition in einer einzigen Anweisung durchgeführt! Natürlich müssen Sie sich darüber keine Sorgen machen, wenn der Optimierer respektabel ist.

Entschuldigung für die zu lange Antwort.

Erstens, wenn Sie nicht in C oder ASSEMBLY arbeiten, befinden Sie sich wahrscheinlich in einer höheren Sprache, in der Speicherstillstände und allgemeine Anrufkosten den Unterschied zwischen Multiplizieren und Teilen bis zur Irrelevanz in den Schatten stellen. Wählen Sie also einfach aus, was in diesem Fall besser liest.

Wenn Sie von einem sehr hohen Niveau sprechen, wird es für alles, wofür Sie es wahrscheinlich verwenden, nicht messbar langsamer sein. Sie werden in anderen Antworten sehen, dass Menschen eine Million multiplizieren / dividieren müssen, um einen Unterschied zwischen den beiden im Millisekundenbereich zu messen.

Wenn Sie immer noch neugierig sind, unter dem Gesichtspunkt der Optimierung auf niedriger Ebene:

Divide hat tendenziell eine deutlich längere Pipeline als Multiplikation. Dies bedeutet, dass es länger dauert, bis das Ergebnis angezeigt wird. Wenn Sie den Prozessor jedoch mit nicht abhängigen Aufgaben beschäftigen können, kostet Sie dies nicht mehr als eine Multiplikation.

Wie lange der Pipelineunterschied ist, hängt vollständig von der Hardware ab. Die letzte Hardware, die ich verwendet habe, war ungefähr 9 Zyklen für eine FPU-Multiplikation und 50 Zyklen für eine FPU-Teilung. Hört sich viel an, aber dann würden Sie 1000 Zyklen für einen Speicherfehler verlieren, so dass die Dinge relativiert werden können.

Eine Analogie besteht darin, einen Kuchen in eine Mikrowelle zu stellen, während Sie eine Fernsehsendung ansehen. Die Gesamtzeit, die Sie von der TV-Show entfernt haben, ist, wie lange es gedauert hat, sie in die Mikrowelle zu stellen und aus der Mikrowelle zu nehmen. Den Rest Ihrer Zeit haben Sie noch die TV-Show gesehen. Wenn der Kuchen also 10 Minuten statt 1 Minute gekocht hat, hat er Ihre Fernsehzeit nicht mehr verbraucht.

In der Praxis müssen Sie Pipelines, Cache, Verzweigungsstillstände, Vorhersagen außerhalb der Reihenfolge und Pipeline-Abhängigkeiten verstehen, wenn Sie sich um den Unterschied zwischen Multiplizieren und Teilen kümmern möchten. Wenn dies nicht so klingt, als wollten Sie mit dieser Frage beginnen, besteht die richtige Antwort darin, den Unterschied zwischen den beiden zu ignorieren.

Vor vielen (vielen) Jahren war es absolut wichtig, Teilungen zu vermeiden und immer Multiplikationen zu verwenden, aber damals waren Gedächtnistreffer weniger relevant und Teilungen viel schlimmer. Heutzutage bewerte ich die Lesbarkeit höher, aber wenn es keinen Unterschied in der Lesbarkeit gibt, halte ich es für eine gute Angewohnheit, sich für Multiplikationen zu entscheiden.

Schreiben Sie, was klarer ist, und geben Sie Ihre Absicht an.

Nachdem Ihr Programm funktioniert hat, finden Sie heraus, was langsam ist, und beschleunigen Sie dies.

Mach es nicht umgekehrt.

Mach was du brauchst. Denken Sie zuerst an Ihren Leser. Machen Sie sich keine Sorgen um die Leistung, bis Sie sicher sind, dass Sie ein Leistungsproblem haben.

Lassen Sie den Compiler die Leistung für Sie erledigen.

Wenn Sie mit Ganzzahlen oder Nicht-Gleitkommatypen arbeiten, vergessen Sie nicht Ihre Bitverschiebungsoperatoren: << >>

    int y = 10;
    y = y >> 1;
    Console.WriteLine("value halved: " + y);
    y = y << 1;
    Console.WriteLine("now value doubled: " + y);

Tatsächlich gibt es einen guten Grund dafür, dass die Faustmultiplikation in der Regel schneller ist als die Division. Die Gleitkommadivision in der Hardware erfolgt entweder mit Verschiebungs- und bedingten Subtraktionsalgorithmen ("lange Division" mit Binärzahlen) oder - heutzutage wahrscheinlicher - mit Iterationen wie der von Goldschmidt Algorithmus. Das Verschieben und Subtrahieren erfordert mindestens einen Zyklus pro Bit Genauigkeit (die Iterationen sind nahezu unmöglich zu parallelisieren, ebenso wie das Verschieben und Addieren der Multiplikation), und iterative Algorithmen führen mindestens eine Multiplikation pro Iteration durch oder eher als vernünftig. Die Pedanterie von "Code, was am klarsten ist" ist absolut wahr, aber alle drei sind so gut lesbar, dass die Pedanterie in diesem Fall nur pedantisch ist.. In beiden Fällen ist es sehr wahrscheinlich, dass die Division mehr Zyklen benötigt. Dies berücksichtigt natürlich keine Macken bei Compilern, Datenverschiebungen oder Präzision. Im Großen und Ganzen eine innere Schleife in einem zeitkritischen Teil eines Programms zu codieren schreiben,0.5 * x1.0/2.0 * xx / 2.0

Ich habe immer gelernt, dass Multiplikation effizienter ist.

Die Multiplikation ist normalerweise schneller - sicherlich nie langsamer. Wenn es jedoch nicht geschwindigkeitskritisch ist, schreiben Sie, was am klarsten ist.

Die Gleitkommadivision ist (im Allgemeinen) besonders langsam. Während die Gleitkommamultiplikation ebenfalls relativ langsam ist, ist sie wahrscheinlich schneller als die Gleitkommadivision.

Aber ich bin eher geneigt zu antworten, "es ist nicht wirklich wichtig", es sei denn, die Profilerstellung hat gezeigt, dass Division ein bisschen Engpass gegenüber Multiplikation ist. Ich vermute jedoch, dass die Wahl zwischen Multiplikation und Division keinen großen Einfluss auf die Leistung Ihrer Anwendung haben wird.

Dies wird eher zu einer Frage, wenn Sie in Assembly oder vielleicht in C programmieren. Ich denke, dass bei den meisten modernen Sprachen eine solche Optimierung für mich durchgeführt wird.

Seien Sie vorsichtig, wenn Sie davon ausgehen, dass Multiplikation in der Regel besser ist. Deshalb versuche ich, mich beim Codieren daran zu halten.

Im Zusammenhang mit dieser speziellen Frage bedeutet besser hier "schneller". Welches ist nicht sehr nützlich.

Über Geschwindigkeit nachzudenken kann ein schwerwiegender Fehler sein. Die spezifische algebraische Form der Berechnung hat tiefgreifende Auswirkungen auf Fehler.

Siehe Gleitkomma-Arithmetik mit Fehleranalyse . Siehe Grundlegende Probleme bei der Gleitkomma-Arithmetik und Fehleranalyse .

Während einige Gleitkommawerte genau sind, sind die meisten Gleitkommawerte eine Annäherung. Sie sind ein idealer Wert plus ein Fehler. Jede Operation gilt für den Idealwert und den Fehlerwert.

Die größten Probleme ergeben sich aus dem Versuch, zwei nahezu gleiche Zahlen zu manipulieren. Die am weitesten rechts stehenden Bits (die Fehlerbits) dominieren die Ergebnisse.

>>> for i in range(7):
...     a=1/(10.0**i)
...     b=(1/10.0)**i
...     print i, a, b, a-b
... 
0 1.0 1.0 0.0
1 0.1 0.1 0.0
2 0.01 0.01 -1.73472347598e-18
3 0.001 0.001 -2.16840434497e-19
4 0.0001 0.0001 -1.35525271561e-20
5 1e-05 1e-05 -1.69406589451e-21
6 1e-06 1e-06 -4.23516473627e-22

In diesem Beispiel können Sie sehen, dass die Differenz zwischen nahezu gleichen Zahlen, wenn die Werte kleiner werden, Ergebnisse ungleich Null erzeugt, bei denen die richtige Antwort Null ist.

Ich habe irgendwo gelesen, dass die Multiplikation in C / C ++ effizienter ist. Keine Ahnung bezüglich interpretierter Sprachen - der Unterschied ist wahrscheinlich aufgrund des anderen Overheads vernachlässigbar.

Es sei denn, es wird zu einem Problem, bleiben Sie bei dem, was wartbarer / lesbarer ist - ich hasse es, wenn Leute mir das sagen, aber es ist so wahr.

Ich würde die Multiplikation im Allgemeinen vorschlagen, da Sie die Zyklen nicht damit verbringen müssen, sicherzustellen, dass Ihr Divisor nicht 0 ist. Dies gilt natürlich nicht, wenn Ihr Divisor eine Konstante ist.

Java Android, profiliert auf Samsung GT-S5830

public void Mutiplication()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a *= 0.5f;
    }
}
public void Division()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a /= 2.0f;
    }
}

Ergebnisse?

Multiplications():   time/call: 1524.375 ms
Division():          time/call: 1220.003 ms

Die Division ist ungefähr 20% schneller als die Multiplikation (!)

Wie bei den Posts Nr. 24 (Multiplikation ist schneller) und Nr. 30 - aber manchmal sind beide genauso einfach zu verstehen:

1*1e-6F;

1/1e6F;

~ Ich finde beide genauso einfach zu lesen und muss sie milliardenfach wiederholen. Es ist daher nützlich zu wissen, dass die Multiplikation normalerweise schneller ist.

Es gibt einen Unterschied, der jedoch vom Compiler abhängig ist. Zuerst habe ich auf vs2003 (c ++) keinen signifikanten Unterschied für Doppeltypen (64-Bit-Gleitkomma) festgestellt. Als ich die Tests jedoch erneut auf vs2010 durchführte, stellte ich einen großen Unterschied fest, bis zu Faktor 4 schneller für Multiplikationen. Wenn man dies aufspürt, scheint es, dass vs2003 und vs2010 unterschiedliche fpu-Codes generieren.

Auf einem Pentium 4, 2,8 GHz, vs2003:

• Multiplikation: 8.09
• Abteilung: 7,97

Auf einem Xeon W3530, vs2003:

• Multiplikation: 4.68
• Abteilung: 4.64

Auf einem Xeon W3530, vs2010:

• Multiplikation: 5.33
• Abteilung: 21.05

Es scheint, dass im Vergleich zu 2003 eine Division in einer Schleife (der Divisor wurde also mehrmals verwendet) in eine Multiplikation mit der Inversen übersetzt wurde. In vs2010 wird diese Optimierung nicht mehr angewendet (ich nehme an, weil es zwischen den beiden Methoden leicht unterschiedliche Ergebnisse gibt). Beachten Sie auch, dass die CPU Divisionen schneller ausführt, sobald Ihr Zähler 0.0 ist. Ich kenne den genauen Algorithmus, der im Chip fest verdrahtet ist, nicht, aber vielleicht ist er zahlenabhängig.

Edit 18-03-2013: die Beobachtung für vs2010

Hier ist eine dumme lustige Antwort:

x / 2.0 ist nicht gleichbedeutend mit x * 0,5

Angenommen, Sie haben diese Methode am 22. Oktober 2008 geschrieben.

double half(double x) => x / 2.0;

Jetzt, 10 Jahre später, erfahren Sie, dass Sie diesen Code optimieren können. Auf die Methode wird in Ihrer Anwendung in Hunderten von Formeln verwiesen. Sie ändern es also und erleben eine bemerkenswerte Leistungsverbesserung von 5%.

double half(double x) => x * 0.5;

War es die richtige Entscheidung, den Code zu ändern? In der Mathematik sind die beiden Ausdrücke tatsächlich gleichwertig. In der Informatik gilt das nicht immer. Weitere Informationen finden Sie unter Minimieren der Auswirkungen von Genauigkeitsproblemen . Wenn Ihre berechneten Werte - irgendwann - mit anderen Werten verglichen werden, ändern Sie das Ergebnis von Kantenfällen. Z.B:

double quantize(double x)
{
    if (half(x) > threshold))
        return 1;
    else
        return -1;
}

Fazit ist; Wenn Sie sich mit einem der beiden zufrieden gegeben haben, bleiben Sie dabei!

Wenn wir davon ausgehen, dass eine Add / Subtrack-Operation 1 kostet, dann multiplizieren Sie 5 und teilen Sie die Kosten auf etwa 20.

Nach einer so langen und interessanten Diskussion hier ist meine Meinung dazu: Es gibt keine endgültige Antwort auf diese Frage. Wie einige Leute betonten , hängt es sowohl von der Hardware (vgl. Piotrk und gast128 ) als auch vom Compiler (vgl. @ Javiers Tests) ab. Wenn die Geschwindigkeit nicht kritisch ist und Ihre Anwendung keine großen Datenmengen in Echtzeit verarbeiten muss, können Sie sich für Klarheit mithilfe einer Division entscheiden. Wenn Verarbeitungsgeschwindigkeit oder Prozessorlast ein Problem darstellen, ist die Multiplikation möglicherweise die sicherste. Wenn Sie nicht genau wissen, auf welcher Plattform Ihre Anwendung bereitgestellt wird, ist der Benchmark bedeutungslos. Und für die Klarheit des Codes würde ein einziger Kommentar die Arbeit erledigen!

Technisch gibt es keine Division, es gibt nur eine Multiplikation mit inversen Elementen. Zum Beispiel dividieren Sie nie durch 2, sondern multiplizieren mit 0,5.

'Division' - machen wir uns etwas vor, dass es für eine Sekunde existiert - ist immer schwieriger als die Multiplikation, denn um xdurch yeine zu 'dividieren', muss zuerst der Wert y^{-1}so berechnet werden , dass y*y^{-1} = 1dann die Multiplikation durchgeführt wird x*y^{-1}. Wenn Sie bereits wissen , y^{-1}dann die Berechnung nicht aus ymuss eine Optimierung sein.