डाई बेंज लेम्मा

फ्लोटिंग-पॉइंट अंकगणित में, स्टरबेंज़ लेम्मा या स्टरबेंज़्स लेम्मा एक प्रमेय देने वाली स्थिति है जिसके तहत फ़्लोटिंग-पॉइंट अंतरों की सटीक गणना की जाती है। इसका नाम पैट एच. स्टरबेंज़ के नाम पर रखा गया है, जिन्होंने 1974 में इसका एक संस्करण प्रकाशित किया था।

Sterbenz lemma — In a floating-point number system with subnormal numbers, if $x$ and $y$ are floating-point numbers such that

$${\frac {y}{2}}\leq x\leq 2y,$$

then $x-y$ is also a floating-point number. Thus, a correctly rounded floating-point subtraction

$$x\ominus y=\operatorname {fl} (x-y)=x-y$$

is computed exactly.

स्टरबेंज़ लेम्मा IEEE 754 पर लागू होता है, जो कंप्यूटर में सबसे व्यापक रूप से इस्तेमाल किया जाने वाला फ़्लोटिंग-पॉइंट नंबर सिस्टम है।

प्रमाण

होने देना $\beta$ फ़्लोटिंग-पॉइंट सिस्टम का मूलांक हो और $p$ परिशुद्धता।

पहले कई आसान मामलों पर विचार करें:

• अगर $x$ तो शून्य है $x-y=-y$, और अगर $y$ तो शून्य है $x-y=x$, इसलिए परिणाम तुच्छ है क्योंकि फ्लोटिंग-पॉइंट नेगेशन हमेशा सटीक होता है।

• अगर $x=y$ नतीजा शून्य है और इस प्रकार सटीक है।

• अगर $x<0$ तो हमारे पास भी होना चाहिए $y/2\leq x<0$ इसलिए $y<0$. इस मामले में, $x-y=-(-x--y)$, इसलिए परिणाम प्रमेय से प्रतिबंधित है $x,y\geq 0$.

• अगर $x\leq y$, हम लिख सकते हैं $x-y=-(y-x)$ साथ $x/2\leq y\leq 2x$, इसलिए परिणाम प्रमेय से प्रतिबंधित है $x\geq y$.

बाकी सबूत के लिए, मान लीजिए $0<y<x\leq 2y$ व्यापकता के नुकसान के बिना।

लिखना $x,y>0$ उनके सकारात्मक अभिन्न महत्व के संदर्भ में $s_{x},s_{y}\leq \beta ^{p}-1$ और न्यूनतम घातांक $e_{x},e_{y}$:

$${\begin{aligned}x&=s_{x}\cdot \beta ^{e_{x}-p+1}\\y&=s_{y}\cdot \beta ^{e_{y}-p+1}\end{aligned}}$$

ध्यान दें कि $x$ और $y$ अवसामान्य हो सकता है—हम नहीं मानते $s_{x},s_{y}\geq \beta ^{p-1}$.

घटाव देता है:

$${\begin{aligned}x-y&=s_{x}\cdot \beta ^{e_{x}-p+1}-s_{y}\cdot \beta ^{e_{y}-p+1}\\&=s_{x}\beta ^{e_{x}-e_{y}}\cdot \beta ^{e_{y}-p+1}-s_{y}\cdot \beta ^{e_{y}-p+1}\\&=(s_{x}\beta ^{e_{x}-e_{y}}-s_{y})\cdot \beta ^{e_{y}-p+1}.\end{aligned}}$$

होने देना $s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}$. तब से $0<y<x$ अपने पास:

• $e_{y}\leq e_{x}$, इसलिए $e_{x}-e_{y}\geq 0$, जिससे हम निष्कर्ष निकाल सकते हैं $\beta ^{e_{x}-e_{y}}$ एक पूर्णांक है और इसलिए ऐसा है $s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}$; और
• $x-y>0$, इसलिए $s'>0$.

आगे, चूंकि $x\leq 2y$, अपने पास $x-y\leq y$, ताकि

$$s'\cdot \beta ^{e_{y}-p+1}=x-y\leq y=s_{y}\cdot \beta ^{e_{y}-p+1}$$

जिसका तात्पर्य है

$$0<s'\leq s_{y}\leq \beta ^{p}-1.$$

इस तरह

$$x-y=s'\cdot \beta ^{e_{y}-p+1},\quad {\text{for}}\quad 0<s'\leq \beta ^{p}-1,$$

इसलिए $x-y$ फ्लोटिंग-पॉइंट नंबर है। ◻

नोट: भले ही $x$ और $y$ सामान्य हैं, अर्थात्, $s_{x},s_{y}\geq \beta ^{p-1}$, हम यह सिद्ध नहीं कर सकते $s'\geq \beta ^{p-1}$ और इसलिए यह साबित नहीं कर सकता $x-y$ भी सामान्य है। उदाहरण के लिए, दो सबसे छोटी सकारात्मक सामान्य फ़्लोटिंग-पॉइंट संख्याओं का अंतर $x=(\beta ^{p-1}+1)\cdot \beta ^{e_{\mathrm {min} }-p+1}$ और $y=\beta ^{p-1}\cdot \beta ^{e_{\mathrm {min} }-p+1}$ है $x-y=1\cdot \beta ^{e_{\mathrm {min} }-p+1}$ जो अनिवार्य रूप से असामान्य है। असामान्य संख्या के बिना फ़्लोटिंग-पॉइंट नंबर सिस्टम में, जैसे मानक क्रमिक अंडरफ़्लो के बजाय गैर-मानक फ्लश-टू-ज़ीरो मोड में सीपीयू, स्टरबेंज़ लेम्मा लागू नहीं होता है।

विनाशकारी रद्दीकरण से संबंध

स्टरबेंज़ लेम्मा को विनाशकारी रद्दीकरण की घटना से अलग किया जा सकता है:

• स्टरबेंज लेम्मा का दावा है कि अगर $x$ और $y$ पर्याप्त रूप से फ़्लोटिंग-पॉइंट संख्याएँ हैं, फिर उनका अंतर $x-y$ फ्लोटिंग-पॉइंट अंकगणितीय द्वारा सटीक रूप से गणना की जाती है $x\ominus y=\operatorname {fl} (x-y)$, गोलाई की आवश्यकता नहीं है।
• विनाशकारी रद्दीकरण की घटना यह है कि यदि ${\tilde {x}}$ और ${\tilde {y}}$ सत्य संख्याओं के सन्निकटन हैं $x$ और $y$- सन्निकटन पूर्व राउंडिंग त्रुटि या श्रृंखला ट्रंकेशन से या भौतिक अनिश्चितता या किसी अन्य चीज़ से उत्पन्न होते हैं - अंतर की त्रुटि ${\tilde {x}}-{\tilde {y}}$ वांछित अंतर से $x-y$ के व्युत्क्रमानुपाती है $x-y$. इस प्रकार, करीब $x$ और $y$ हैं, और भी बुरा ${\tilde {x}}-{\tilde {y}}$ के अनुमान के रूप में हो सकता है $x-y$, भले ही घटाव की सटीक गणना की गई हो।

दूसरे शब्दों में, स्टरबेंज लेम्मा से पता चलता है कि आस-पास के फ़्लोटिंग-पॉइंट नंबरों को घटाना सटीक है, लेकिन यदि आपके पास संख्याएँ सन्निकटन हैं, तो उनका सटीक अंतर भी उन संख्याओं के अंतर से बहुत दूर हो सकता है जिन्हें आप घटाना चाहते हैं।

संख्यात्मक विश्लेषण में प्रयोग

फ्लोटिंग-पॉइंट एल्गोरिदम के संख्यात्मक विश्लेषण में त्रुटि सीमा पर प्रमेयों को साबित करने में स्टरबेंज़ लेम्मा सहायक है। उदाहरण के लिए, हीरोन का सूत्र

$$A={\sqrt {s(s-a)(s-b)(s-c)}}$$

भुजाओं की लंबाई वाले त्रिभुज के क्षेत्रफल के लिए $a$, $b$, और $c$, कहाँ $s=(a+b+c)/2$ अर्ध-परिधि है, यदि फ़्लोटिंग-पॉइंट अंकगणित में सीधे मूल्यांकन किया जाए तो लंबे संकीर्ण त्रिभुजों के लिए खराब सटीकता दे सकता है। हालाँकि, के लिए $a\geq b\geq c$, वैकल्पिक सूत्र

$$A={\frac {1}{4}}{\sqrt {{\bigl (}a+(b+c){\bigr )}{\bigl (}c-(a-b){\bigr )}{\bigl (}c+(a-b){\bigr )}{\bigl (}a+(b-c){\bigr )}}}$$

सभी इनपुट के लिए कम त्रुटि विश्लेषण (गणित) होने के लिए, स्टरबेंज़ लेम्मा की मदद से सिद्ध किया जा सकता है।