Ist Gleitkommaaddition und -multiplikation assoziativ?

Ich hatte ein Problem, als ich drei Gleitkommawerte addierte und sie mit 1 verglich.

cout << ((0.7 + 0.2 + 0.1)==1)<<endl;     //output is 0
cout << ((0.7 + 0.1 + 0.2)==1)<<endl;     //output is 1

Warum sollten diese Werte anders ausfallen?

Gleitkommaaddition ist nicht notwendigerweise assoziativ. Wenn Sie die Reihenfolge ändern, in der Sie Dinge addieren, kann dies das Ergebnis verändern.

Das Standardpapier zu diesem Thema ist Was jeder Informatiker über Gleitkommaarithmetik wissen sollte. Es gibt folgendes Beispiel:

Eine weitere Grauzone betrifft die Interpretation von Klammern. Aufgrund von Rundungsfehlern gelten die assoziativen Gesetze der Algebra nicht unbedingt für Gleitkommazahlen. Zum Beispiel hat der Ausdruck (x+y)+z eine völlig andere Antwort als x+(y+z), wenn x = 1e30, y = -1e30 und z = 1 (es ist 1 im ersten Fall, 0 im zweiten). ).

Was bei derzeit beliebten Maschinen und Software wahrscheinlich ist, ist:

Der Compiler codiert .7 als 0x1.6666666666666p-1 (dies ist die hexadezimale Zahl 1.6666666666666 multipliziert mit 2 hoch -1), .2 als 0x1.999999999999ap-3 und .1 als 0x1.999999999999ap-4. Jede davon ist die in Fließkomma darstellbare Zahl, die der von Ihnen geschriebenen Dezimalzahl am nächsten kommt.

Beachten Sie, dass jede dieser hexadezimalen Gleitkommakonstanten genau 53 Bit in ihrer Signifikande hat (der „Bruch“-Teil, oft fälschlicherweise als Mantisse bezeichnet). Die Hexadezimalzahl für den Signifikanten hat eine „1“ und dreizehn weitere Hexadezimalziffern (jeweils vier Bits, insgesamt 52, 53 einschließlich der „1“), was der IEEE-754-Standard für 64-Bit-Binärfloating vorsieht. Punktzahlen.

Lassen Sie uns die Zahlen für addieren .7 und .2: 0x1.6666666666666p-1 und 0x1.999999999999ap-3. Skaliere zuerst den Exponenten der zweiten Zahl so, dass er mit der ersten übereinstimmt. Dazu multiplizieren wir den Exponenten mit 4 (ändern „p-3“ zu „p-1“) und multiplizieren die Mantisse mit 1/4, was 0x0,66666666666668p-1 ergibt. Fügen Sie dann 0x1.6666666666666p-1 und 0x0.66666666666668p-1 hinzu, was 0x1.ccccccccccccc8p-1 ergibt. Beachten Sie, dass diese Zahl mehr als 53 Bits in der Mantisse hat: Die „8“ ist die 14. Stelle nach dem Punkt. Fließkomma kann mit so vielen Bits kein Ergebnis zurückgeben, daher muss es auf die nächste darstellbare Zahl gerundet werden. In diesem Fall gibt es zwei Zahlen, die gleich nahe beieinander liegen, 0x1.cccccccccccccp-1 und 0x1.ccccccccccccdp-1. Bei Gleichstand wird die Zahl mit einer Null im untersten Bit der Mantisse verwendet. “c” ist gerade und “d” ist ungerade, also wird “c” verwendet. Das Endergebnis der Addition ist 0x1.cccccccccccccp-1.

Fügen Sie als Nächstes die Nummer für hinzu .1 (0x1.999999999999ap-4) dazu. Auch hier skalieren wir, damit die Exponenten übereinstimmen, also wird 0x1.999999999999ap-4 zu 0x.33333333333334p-1. Fügen Sie das dann zu 0x1.cccccccccccccp-1 hinzu, was 0x1.fffffffffffff4p-1 ergibt. Das Runden auf 53 Bit ergibt 0x1.ffffffffffffp-1, und das ist das Endergebnis von .7+.2+.1.

Jetzt bedenke .7+.1+.2. Zum .7+.1, fügen Sie 0x1.6666666666666p-1 und 0x1.999999999999ap-4 hinzu. Denken Sie daran, dass letzteres auf 0x.33333333333334p-1 skaliert ist. Dann ist die genaue Summe 0x1.99999999999994p-1. Das Runden auf 53 Bit ergibt 0x1.9999999999999p-1.

Fügen Sie dann die Zahl für hinzu .2 (0x1.999999999999ap-3), die auf 0x0.66666666666668p-1 skaliert ist. Die genaue Summe ist 0x2.00000000000008p-1. Gleitkommazahlen werden immer so skaliert, dass sie mit 1 beginnen (mit Ausnahme von Sonderfällen: Null, Unendlich und sehr kleine Zahlen am unteren Ende des darstellbaren Bereichs), also passen wir dies auf 0x1.00000000000004p0 an. Schließlich runden wir auf 53 Bit, was 0x1.0000000000000p0 ergibt.

Aufgrund von Fehlern, die beim Runden auftreten, .7+.2+.1 gibt 0x1.fffffffffffffp-1 (sehr geringfügig kleiner als 1) zurück, und .7+.1+.2 gibt 0x1.0000000000000p0 (genau 1) zurück.

Gleitkommamultiplikation ist in C oder C++ nicht assoziativ.

Nachweisen:

#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;
}

In diesem Programm, etwa 30 % der Zeit, (a*b)*c ist ungleich zu a*(b*c).

Weder Addition noch Multiplikation sind mit IEEE 743-Zahlen mit doppelter Genauigkeit (64 Bit) assoziativ. Hier sind jeweils Beispiele (evaluiert mit Python 3.9.7):

>>> (.1 + .2) + .3
0.6000000000000001
>>> .1 + (.2 + .3)
0.6

>>> (.1 * .2) * .3
0.006000000000000001
>>> .1 * (.2 * .3)
0.006

Ähnliche Antwort wie die von Eric, aber zur Ergänzung und mit Python.

import random

random.seed(0)
n = 1000
a = [random.random() for i in range(n)]
b = [random.random() for i in range(n)]
c = [random.random() for i in range(n)]

sum(1 if (a[i] + b[i]) + c[i] != a[i] + (b[i] + c[i]) else 0 for i in range(n))