फ़्लोटिंग पॉइंट गुणा बनाम दोहराव जोड़ा

Question

N एक संकलित समय हस्ताक्षरित पूर्णांक बनें।

जीसीसी

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

बस a*N अनुकूलन कर सकते हैं। यह समझा जा सकता है क्योंकि मॉड्यूलर अंकगणित कहते हैं (a%k + b%k)%k = (a+b)%k।

हालांकि जीसीसी a*(float)N को

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

का अनुकूलन नहीं होंगे।

लेकिन सहयोगी गणित का उपयोग करके उदा। -Ofast मैंने पाया कि जीसीसी log2(N) चरणों के क्रम में इसे कम कर सकता है। N=8 के लिए E.g यह तीन जोड़ों में योग कर सकता है।

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

हालांकि N=16 जीसीसी के बाद कुछ बिंदु N-1 रकम कर वापस चला जाता है।

मेरा सवाल यह है कि जीसीसी -Ofast के साथ क्यों नहीं करता है?

O(N) या O(Log(N)) होने के बजाय यह O(1) हो सकता है। चूंकि N संकलन समय पर ज्ञात है, यह निर्धारित करना संभव है कि N एक फ्लोट में फिट बैठता है या नहीं। और यहां तक ​​कि अगर N एक फ्लोट के लिए बहुत बड़ा है तो यह sum =a*(float)(N & 0x0000ffff) + a*(float)(N & ffff0000) कर सकता है। असल में, मैंने सटीकता की जांच करने के लिए थोड़ा परीक्षण किया और a*(float)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); 
} 

परिणाम 61848396.000000 52707136.000000 52707136.000000 जो दिखाता है कि गुणा और Kahan summation ही परिणाम है जो मुझे लगता है कि पता चलता है कि गुणा सरल राशि से अधिक सटीक है है।

Answer 1

वहाँ

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

और

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

के बीच कुछ मौलिक अंतर राशि FLT_EPSILON दृष्टिकोण जब * हैं मूल्य से भी बड़ा, बार-बार योग नो-सेशन की ओर जाता है। तो एन के किसी भी बड़े मूल्य के परिणामस्वरूप बार-बार अतिरिक्त योग के लिए कोई बदलाव नहीं होगा। गुणा विकल्प के लिए, ऑपरेशन के लिए नो-ऑप होने के परिणामस्वरूप परिणाम (मान * एन) FLT_EPSILON * होना चाहिए।

तो संकलक अनुकूलन नहीं कर सकता है, क्योंकि यह नहीं बता सकता कि आप सही व्यवहार (जहां गुणा बेहतर है), या लागू व्यवहार, जहां योग का स्तर अतिरिक्त के परिणाम को प्रभावित करता है।