programacion - punto flotante plc

multiplicación de coma flotante vs adición repetida

Question

Deje N ser un entero sin signo de tiempo de compilación.

GCC puede optimizar

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

simplemente a*N Esto se puede entender dado que la aritmética modular dice (a%k + b%k)%k = (a+b)%k .

Sin embargo, GCC no optimizará

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

a a*(float)N

Pero al usar matemática asociativa con, por ejemplo, " -Ofast " descubrí que GCC puede reducir esto en orden log2(N) pasos. Por ejemplo, para N=8 puede hacer la suma en tres adiciones.

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

Aunque en algún momento después de N=16 GCC vuelve a hacer sumas N-1 .

Mi pregunta es por qué GCC no hace a*(float)N con -Ofast ?

En lugar de ser O(N) u O(Log(N)) podría ser simplemente O(1) . Como se conoce N en el momento de la compilación, es posible determinar si N cabe en un flotador. E incluso si N es demasiado grande para un flotante, puede hacer sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000) . De hecho, hice una pequeña prueba para verificar la precisión y a*(float)N es más preciso de todos modos (consulte el código y los resultados a continuación).

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

El resultado es 61848396.000000 52707136.000000 52707136.000000 que muestra que la multiplicación y la suma de Kahan tienen el mismo resultado, que creo que muestra que la multiplicación es más precisa que la suma simple.

Answer 1

Hay alguna diferencia fundamental 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;
}

Cuando la suma se acerca a FLT_EPSILON * mayor que el valor, la suma repetida tiende hacia un no-op. Por lo tanto, cualquier valor grande de N daría como resultado ningún cambio en la suma para la suma repetida. Para la opción de multiplicación, el resultado (valor * N) debe ser FLT_EPSILON * más pequeño que la suma para que la operación no funcione.

Por lo tanto, el compilador no puede realizar la optimización porque no puede determinar si usted quería el comportamiento exacto (donde multiplicar es mejor) o el comportamiento implementado, donde la escala de suma afecta el resultado de la suma.