Gleitkommamultiplikation vs. wiederholte Addition

Lesezeit: 4 Minuten

Benutzeravatar von Z boson
Z-Boson

Lassen N eine vorzeichenlose Ganzzahl zur Kompilierzeit sein.

GCC kann optimieren

unsigned sum = 0;
for(unsigned i=0; i<N; i++) sum += a; // a is an unsigned integer   

zu einfach a*N. Dies kann verstanden werden, da die modulare Arithmetik sagt (a%k + b%k)%k = (a+b)%k.

GCC wird jedoch nicht optimiert

float sum = 0;
for(unsigned i=0; i<N; i++) sum += a;  // a is a float

zu a*(float)N.

Aber durch die Verwendung von assoziativer Mathematik mit zB -Ofast Ich entdeckte, dass GCC dies in Ordnung reduzieren kann log2(N) Schritte. Bsp für N=8 es kann die Summe in drei Additionen machen.

sum = a + a
sum = sum + sum // (a + a) + (a + a)
sum = sum + sum // ((a + a) + (a + a)) + ((a + a) + (a + a))

Obwohl irgendwann danach N=16 GCC geht zurück zum Tun N-1 Summen.

Meine Frage ist, warum GCC nicht funktioniert a*(float)N mit -Ofast?

Anstatt zu sein O(N) oder O(Log(N)) es könnte einfach sein O(1). Seit N zur Kompilierzeit bekannt ist, ist es möglich festzustellen, ob N passt in einen Schwimmer. Und selbst wenn N ist zu groß für einen Schwimmer, den es tun könnte sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000). Tatsächlich habe ich einen kleinen Test gemacht, um die Genauigkeit zu überprüfen und a*(float)N ist sowieso genauer (siehe Code und Ergebnisse unten).

//gcc -O3 foo.c
//don't use -Ofast or -ffast-math or -fassociative-math
#include <stdio.h>   
float sumf(float a, int n)
{
  float sum = 0;
  for(int i=0; i<n; i++) sum += a;
  return sum;
}

float sumf_kahan(float a, int n)
{
  float sum = 0;
  float c = 0;
  for(int i=0; i<n; i++) {
    float y = a - c;
    float t = sum + y;
    c = (t -sum) - y;
    sum = t;
  }
  return sum;
}  

float mulf(float a, int n)
{
  return a*n;
}  

int main(void)
{
  int n = 1<<24;
  float a = 3.14159;
  float t1 = sumf(a,n);
  float t2 = sumf_kahan(a,n);
  float t3 = mulf(a,n);
  printf("%f %f %f\n",t1,t2,t3);
}

Das Ergebnis ist 61848396.000000 52707136.000000 52707136.000000 was zeigt, dass Multiplikation und die Kahan-Summe haben das gleiche Ergebnis, was meiner Meinung nach zeigt, dass die Multiplikation genauer ist als die einfache Summe.

  • Haben Sie darüber nachgedacht, dass drei Additionsoperationen möglicherweise schneller sind als eine Fließkomma-Multiplikation? Dies würde damit übereinstimmen, dass es bei N = 16 auf eine fp-Multiplikation zurückschaltet.

    – Bob

    15. Oktober 2015 um 15:29 Uhr


  • Es führt keine Optimierung durch, weil die Optimierung nicht gültig ist; im Allgemeinen führt es zu einem anderen Ergebnis. Gleitkomma-Arithmetik gehorcht nicht den üblichen normalen arithmetischen Eigenschaften, die Sie erwarten, wie Assoziativität oder das Distributivgesetz. Multiplikation ist keine wiederholte Addition.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    15. Oktober 2015 um 15:40 Uhr

  • @R..: Er verwendet (implizit). -ffast-math die tut erlauben diese Art von Optimierungen. stackoverflow.com/questions/7420665/…

    – Karoly Horvath

    15. Oktober 2015 um 15:42 Uhr


  • Wenn -Ofast impliziert -ffast-mathdann mischt sich diese Frage -ffast-math und Kahan-Summierung, die kein gutes Rezept ist (Kahan-Summierung ist das prototypische Beispiel für Code, der nicht mit nicht konformen Optimierungen kompiliert werden darf).

    – Pascal Cuoq

    15. Oktober 2015 um 23:50 Uhr

  • @Zboson: Es ist höchst nicht offensichtlich (sogar Kahan war schockiert, als ich ihm diese Tatsache erzählte, obwohl er sofort verstand, warum es wahr war, als ich es ihm sagte). Der einfachste Weg, um zu sehen, dass es wahr ist, besteht wahrscheinlich darin, die Rundung für alle möglichen nachgestellten Bitmuster von x gründlich zu überprüfen, wenn Sie neugierig sind. Ein tieferer Beweis kann wahrscheinlich erreicht werden, indem man beweist, dass (2^n – 1)x + x = 2^nx ist, wenn 2^n-1 darstellbar ist, und dann beachtet, dass x + x + x = 3x. Die Eigenschaft gilt für 2, 3, 4 und 5; 6 ist das erste n, für das es fehlschlägt.

    – Stefan Kanon

    16. Oktober 2015 um 13:58 Uhr


Es gibt einige grundlegende Unterschiede zwischen

 float funct( int N, float sum )
 {
     float value = 10.0;
     for( i = 0; i < N ;i ++ ) {
         sum += value;
     }
     return sum;
 }

und

float funct( int N, float sum )
{
    float value = 10.0;
    sum += value * N;
    return sum;
}

Wenn sich die Summe FLT_EPSILON * größer als der Wert nähert, tendiert die wiederholte Summe zu einem No-Op. Jeder große Wert von N würde also bei wiederholter Addition zu keiner Änderung der Summe führen. Für die Multiplikationsauswahl muss das Ergebnis (Wert * N) FLT_EPSILON * kleiner als Summe sein, damit die Operation keine Operation hat.

Der Compiler kann also keine Optimierung vornehmen, da er nicht sagen kann, ob Sie das genaue Verhalten (wobei multiplizieren besser ist) oder das implementierte Verhalten wollten, bei dem die Summenskalierung das Ergebnis der Addition beeinflusst.

1401630cookie-checkGleitkommamultiplikation vs. wiederholte Addition

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy