2012-12-17 13 views
19

Addition hält die assoziative Eigenschaft:Sind Fließkommaoperationen in C assoziativ? mathematisch

(a + b) + c = a + (b + c) 

Im allgemeinen Fall, diese Eigenschaft nicht für Gleitkommazahlen hält, weil sie Werte in einer endlichen Genauigkeit darstellen.

Darf ein Compiler die obige Ersetzung vornehmen, wenn er Maschinencode aus einem C-Programm als Teil einer Optimierung generiert? Wo sagt es genau in der C-Norm?

+1

Für mindestens Multiplikation, schau hier: http://StackOverflow.com/Questions/6430448/Why-doesnt-Gcc-optimize-aaaaaa-to-aaaaaa –

Antwort

12

Der Compiler darf keine "Optimierungen" durchführen, die zu einem anderen berechneten Wert führen als der nach der abstrakten Maschinensemantik berechnete Wert.

5.1.2.3 Programmausführung

[# 1] Die semantischen Beschreibungen in dieser Internationalen Norm beschreiben das Verhalten einer abstrakten Maschine in die Fragen der Optimierung nicht relevant sind.

[# 3] In der abstrakten Maschine werden alle Ausdrücke wie in der Semantik angegeben ausgewertet.

[# 13] BEISPIEL 5 Umlagerung für Gleitkommaausdrücke ist oft aufgrund von Einschränkungen in der Genauigkeit als Bereich eingeschränkt. Die Implementierung kann die mathematischen assoziativen Regeln für Addition oder Multiplikation, noch die distributive Regel nicht anwenden, wegen Rundungsfehler, auch in Abwesenheit von Überlauf und Unterlauf.

In Ihrem Beispiel:

(a + b) + c 

oder auch ohne Klammern:

a + b + c 

wir haben

+ 
/\ 
    + c 
/\ 
a b 

und der Compiler wird benötigt, um Code zu generieren, als ob a wird mitsummiertund das Ergebnis wird mit c summiert.

+0

Korrekte Theorie. Die Anwendung, die Sie mit nach Hause nehmen sollten, ist: Stellen Sie fest, in welcher Reihenfolge Ihre Operationen ausgeführt werden sollen (zB wenn Sie klein oder klein, groß oder groß summieren wollen), setzen Sie Klammern, um die Paranoia zu befriedigen, und Sie können sich keine Gedanken mehr darüber machen Neuordnung. –

+0

Beachten Sie jedoch, dass die Rangfolge des Operators zwar eindeutig definiert ist, die Reihenfolge der Auswertung der Unterausdrücke jedoch nicht festgelegt ist. Mit anderen Worten, das Programm kann diesen binären Baum von rechts nach links oder von links nach rechts auswerten und muss diese Reihenfolge nicht einmal in einer konsistenten Weise einhalten, noch muss er es dokumentieren. Wenn entweder a, b oder c Nebenwirkungen enthielten, die das Ergebnis beeinflussten, wäre der Code problematisch. Sagen wir zum Beispiel, dass c eine Funktion ist, die a modifiziert: dann könnten wir das Ergebnis nicht wissen. – Lundin

5

Fließkomma-Multiplikation in C ist nicht assoziativ.

In C, Floating point multiplication is not associative. 

Einige Beweise ist mit diesem C-Code:

drei zufällige Float-Werte auswählen.
Überprüfen Sie, ob a*(b*c) ist immer ungleich (a*b)*c

#include<stdio.h> 
#include<time.h> 
#include<stdlib.h> 
using namespace std; 
int main() { 
    int counter = 0; 
    srand(time(NULL)); 
    while(counter++ < 10){ 
     float a = rand()/100000; 
     float b = rand()/100000; 
     float c = rand()/100000; 

     if (a*(b*c) != (a*b)*c){ 
      printf("Not equal\n"); 
     } 
    } 
    printf("DONE"); 
    return 0; 
} 

Das Programm druckt:

Not equal 
Not equal 
Not equal 
Not equal 
DONE 
RUN FINISHED; exit value 0; real time: 10ms; user: 0ms; system: 0ms 

Fazit:

Für meinen Test wurden drei zufällig Gleitkomma-Multiplikationswerte ausgewählt sind assoziativ etwa 70% der Zeit.

+0

Das OP fragte, ob der Compiler * float-Operationen als assoziativ annehmen würde, wenn er Optimierungen vornimmt. Ihm ist klar bewusst, dass sie es tatsächlich nicht sind. –

+0

Ja, aber es ist immer schön, ein Beispiel zu sehen, das die Theorie bestätigt. –

Verwandte Themen