multiplication en virgule flottante vs addition répétée

Question

Soit N être un entier non signé au moment de la compilation.

GCC peut optimiser

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

pour simplement a*N . Cela peut être compris puisque l'arithmétique modulaire dit (a%k + b%k)%k = (a+b)%k .

Cependant, GCC n'optimisera pas

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

à a*(float)N .

Mais en utilisant les mathématiques associatives avec, par exemple. -Ofast J'ai découvert que GCC peut réduire ceci dans l'ordre log2(N) étapes. Par exemple, pour N=8 il peut faire la somme en trois additions.

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

Bien que quelque temps après N=16 Le CCG reprend ses activités N-1 des sommes.

*Ma question est de savoir pourquoi GCC ne fait pas `a(float)Ncon-Ofast` ?**

Au lieu d'être O(N) o O(Log(N)) cela pourrait être simplement O(1) . Puisque N est connu au moment de la compilation, il est possible de déterminer si N s'insère dans un flotteur. Et même si N est trop grand pour un flotteur, il pourrait faire sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000) . En fait, j'ai fait un petit test pour vérifier la précision et a*(float)N est de toute façon plus précise (voir le code et les résultats ci-dessous).

//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);
}

Le résultat est 61848396.000000 52707136.000000 52707136.000000 ce qui montre que la multiplication et la Résumé de Kahan ont le même résultat, ce qui montre, je pense, que la multiplication est plus précise que la simple somme.

Answer 1

Il existe des différences fondamentales entre

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

y

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

Lorsque la somme s'approche de FLT_EPSILON * plus grande que la valeur, la somme répétée tend vers un no-op. Ainsi, toute grande valeur de N n'entraînerait aucun changement de la somme pour l'addition répétée. Pour le choix de la multiplication, le résultat (valeur * N) doit être FLT_EPSILON * plus petit que la somme pour que l'opération soit sans effet.

Le compilateur ne peut donc pas effectuer l'optimisation, car il ne peut pas dire si vous vouliez le comportement exact (où multiplier est meilleur), ou le comportement implémenté, où l'échelle de la somme affecte le résultat de l'addition.