moltiplicazione in virgola mobile contro aggiunta ripetuta

Question

Sia N un intero senza segno di tempo di compilazione.

GCC può ottimizzare

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

semplicemente a*N. Questo può essere compreso dal momento che l'aritmetica modulare dice (a%k + b%k)%k = (a+b)%k.

Tuttavia GCC non ottimizzerà

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

al a*(float)N.

Ma utilizzando la matematica associativa con ad es. -Ofast Ho scoperto che GCC può ridurre questo in ordine ai passi log2(N). E.g per N=8 può fare la somma in tre aggiunte.

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

Anche se un certo punto dopo N=16 GCC torna a fare N-1 somme.

La mia domanda è perché GCC non fa a*(float)N con -Ofast?

Invece di essere O(N) o O(Log(N)) potrebbe essere semplicemente O(1). Poiché lo N è noto al momento della compilazione, è possibile determinare se N si adatta a un valore float. E anche se N è troppo grande per un float, potrebbe fare sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000). In effetti, ho fatto un piccolo test per verificare la precisione e lo a*(float)N è più preciso in ogni caso (vedi il codice e i risultati sotto).

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

Il risultato è 61848396.000000 52707136.000000 52707136.000000 che dimostra che la moltiplicazione e la Kahan summation hanno lo stesso risultato che ritengo mostra che la moltiplicazione è più accurata rispetto alla semplice somma.

Answer 1

Ci sono alcuni differenza fondamentale tra

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

e

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

Quando la somma avvicina FLT_EPSILON * maggiore valore, la somma ripetuta tende verso una no-op. Quindi qualsiasi grande valore di N, non comporterebbe alcun cambiamento in somma per aggiunte ripetute. Per la scelta della moltiplicazione, il risultato (valore * N) deve essere FLT_EPSILON * minore della somma per l'operazione per avere un no-op.

Quindi il compilatore non può effettuare l'ottimizzazione, perché non può stabilire se si desidera il comportamento esatto (dove moltiplicare è migliore) o il comportamento implementato, in cui la scala della somma influisce sul risultato dell'aggiunta.