Aufwand eines Vergleichs



  • Hallo!

    Der Titel sagt eigentlich alles.
    Wie ist der Rechenaufwand eines Vergleichs - z.Bsp if(fabs(x < TOL), wenn ich den Betrag mit einer vorgegebenen Toleranz vergleiche - im Vergleich zu Multiplikation/Division und Addition/Subtraktion einzuschätzen. Diese Unterteilung habe ich vorgenommen, da ich in einem Numerik Buch gelesen habe, dass Mult/Div bedeutend mehr Aufwand mit sich bringt als Add/Subtraktion.

    Danke im Vorhinein für Antworten oder Anmerkungen!

    Stefan


  • Mod

    Kommt drauf an.

    Da die genannten Methoden aber grundverschiedene semantische Bedeutung haben, ist mir nicht schlüssig, was ein Laufzeitvergleich bringen soll. Man muss doch sowieso das nehmen, was man von der Logik her braucht, und hat diesbezüglich keine andere Wahl.



  • stekuntze schrieb:

    Hallo!

    Der Titel sagt eigentlich alles.
    Wie ist der Rechenaufwand eines Vergleichs - z.Bsp if(fabs(x < TOL), wenn ich den Betrag mit einer vorgegebenen Toleranz vergleiche - im Vergleich zu Multiplikation/Division und Addition/Subtraktion einzuschätzen. Diese Unterteilung habe ich vorgenommen, da ich in einem Numerik Buch gelesen habe, dass Mult/Div bedeutend mehr Aufwand mit sich bringt als Add/Subtraktion.

    Danke im Vorhinein für Antworten oder Anmerkungen!

    Stefan

    Vergleiche auf > und < werden bei numerischen Typen intern immer als Subtraktion ausgeführt. Jedenfalls ist mir keine andere Methode bekannt. Das geschieht für mehrere Bits in einem Takt mit so einer Schaltung: https://en.wikipedia.org/wiki/Adder_(electronics).

    Bei Real-Variablen ist da etwas komplexer, aber letztlich auch eine Subtraktion.



  • stekuntze schrieb:

    ...da ich in einem Numerik Buch gelesen habe, dass Mult/Div bedeutend mehr Aufwand mit sich bringt als Add/Subtraktion.

    Normal schon, aber es gibt tolle Tricks um Mult/Div zu beschleunigen. Z.B. mit ner Kombination aus Shift und Add. Bei Zweierpotenzen ja sowieso, da ist 1 mal Linksschieben *2 und 1*Rechtsschieben /2. Also z.B ist x*17 = (x<<4)+x. Aber das ist noch trivial. Da gibt es viel schönere Sachen, gerade für BigIntegers (Montgomery-Multiplikation, usw).



  • stekuntze schrieb:

    Wie ist der Rechenaufwand eines Vergleichs - z.Bsp if(fabs(x < TOL), wenn ich den Betrag mit einer vorgegebenen Toleranz vergleiche - im Vergleich zu Multiplikation/Division und Addition/Subtraktion einzuschätzen. Diese Unterteilung habe ich vorgenommen, da ich in einem Numerik Buch gelesen habe, dass Mult/Div bedeutend mehr Aufwand mit sich bringt als Add/Subtraktion.

    Der Vergleich an sich ist nicht sonderlich hoch, aber das damit verbundene branching, falls es zufaellig ist, kann weit mehr kosten, weil die CPU eine pipeline hat.


Anmelden zum Antworten