कौन सा फ़्लोटिंग-पॉइंट तुलना अधिक सटीक है, और क्यों?

Question

मैं वर्ग जड़ों की गणना के लिए न्यूटन विधि के विभिन्न कार्यान्वयन के साथ प्रयोग कर रहा हूं। एल्गोरिदम को समाप्त करने का एक महत्वपूर्ण निर्णय है।

जाहिर है यह क्योंकि x के बड़े मूल्यों के लिए है, जहां yx के वर्गमूल के मौजूदा अनुमान है y*y और x के बीच पूर्ण अंतर का उपयोग करने से काम नहीं चलेगा यह पर्याप्त के साथ अपने वर्गमूल प्रतिनिधित्व करने के लिए संभव नहीं हो सकता परिशुद्धता।

तो मुझे एक सापेक्ष मानदंडों का उपयोग करना चाहिए। Naively मैं इस तरह कुछ इस्तेमाल किया होगा:

static int sqrt_good_enough(float x, float y) { 
    return fabsf(y*y - x)/x < EPS; 
} 

और यह बहुत अच्छी तरह से काम करता प्रतीत होता है। लेकिन हाल ही में मैं Kernighan और Plauger के प्रोग्रामिंग शैली के तत्वों पढ़ना शुरू किया है और वे अध्याय 1 में एक ही एल्गोरिथ्म, जिसका समापन मापदंड, सी में अनुवाद के लिए एक फोरट्रान कार्यक्रम देने के लिए, होगा:

static int sqrt_good_enough(float x, float y) { 
    return fabsf(x/y - y) < EPS * y; 
} 

दोनों गणितीय रूप से समकक्ष हैं, लेकिन क्या एक दूसरे के ऊपर एक रूप पसंद करने का कोई कारण है?

Answer 1

दोनों वास्तव में गणितीय रूप से सटीक नहीं हैं, जब तक कि आप पहले के लिए fabsf (y * y - x)/(y * y) < ईपीएस लिखते हैं। (मेरी मूल टिप्पणी में टाइपो के लिए खेद है)

लेकिन मुझे लगता है कि मुख्य बिंदु यह अभिव्यक्ति है कि न्यूटन पुनरावृत्ति में वाई की गणना के लिए अभिव्यक्ति को अपने फॉर्मूला से मेल करें। उदाहरण के लिए यदि आपका वाई सूत्र y = (y + x/y)/2 है, तो आपको कर्निगन और प्लॉगर की शैली का उपयोग करना चाहिए। यदि यह y = (y * y + x)/(2 * y) है तो आपको (y * y - x)/(y * y) < ईपीएस का उपयोग करना चाहिए।

आम तौर पर समाप्ति मानदंड होना चाहिए कि पेट (वाई (एन + 1) - वाई (एन)) काफी छोटा है (यानी वाई (एन + 1) * ईपीएस से छोटा)। यही कारण है कि दो अभिव्यक्तियों का मिलान होना चाहिए। यदि वे बिल्कुल मेल नहीं खाते हैं, तो यह संभव है कि समाप्ति परीक्षण निर्णय लेता है कि अवशिष्ट पर्याप्त छोटा नहीं है जबकि वाई (एन) में अंतर अलग-अलग स्केलिंग के कारण फ्लोटिंग पॉइंट त्रुटि से छोटा है। नतीजा एक अनंत लूप होगा क्योंकि वाई (एन) ने बदलना बंद कर दिया है और समाप्ति मानदंड कभी पूरा नहीं हुआ है।

उदाहरण के लिए निम्नलिखित मैटलैब कोड बिल्कुल वैसा ही न्यूटन solver अपना पहला उदाहरण के रूप में है, लेकिन यह हमेशा के लिए चलाता है:

x = 6.800000000000002 
yprev = 0 
y = 2 
while abs(y*y - x) > eps*abs(y*y) 
    yprev = y; 
    y = 0.5*(y + x/y); 
end 

सी इसके बारे में/C++ संस्करण एक ही समस्या है।

Answer 2

वे अभी भी समकक्ष नहीं हैं; नीचे एक गणितीय रूप से fabsf(y*y - x)/(y*y) < EPS के बराबर है। समस्या जो मैं आपके साथ देखता हूं वह यह है कि यदि y*y अतिप्रवाह (संभवतः xFLT_MAX और y अनचाहे रूप से चुना गया है), तो समाप्ति कभी नहीं हो सकती है। निम्नलिखित बातचीत डबल्स का उपयोग करती है।

>>> import math 
>>> x = (2.0 - 2.0 ** -52) * 2.0 ** 1023 
>>> y = x/math.sqrt(x) 
>>> y * y - x 
inf 
>>> y == 0.5 * (y + x/y) 
True 

संपादित करें: के रूप में एक टिप्पणी (अब नष्ट कर दिया) ने बताया, यह भी यात्रा और समाप्ति परीक्षण के बीच संचालन साझा करने के लिए अच्छा है।

EDIT2: दोनों में शायद असामान्य x के साथ समस्याएं हैं। professionals दोनों चरम सीमाओं की जटिलताओं से बचने के लिए x सामान्यीकृत करें।