2025-11-17T19:07:12.711716

Fast Trigonometric Functions using the RLIBM Approach

Park, Nagarakatte
This paper describes our experience developing polynomial approximations for trigonometric functions that produce correctly rounded results for multiple representations and rounding modes using the RLIBM approach. A key challenge with trigonometric functions concerns range reduction with "pi", which reduces a given input in the domain of a 32-bit float to a small domain. Any rounding error in the value of "pi" is amplified during range reduction, which can result in wrong results. We describe our experience implementing fast range reduction techniques that maintain a large number of bits of "pi" both with floating-point and integer computations. The resulting implementations for trigonometric functions are fast and produce correctly rounded results for all inputs for multiple representations up to 32-bits with a single implementation.
academic

RLIBM दृष्टिकोण का उपयोग करके तीव्र त्रिकोणमितीय फलन

बुनियादी जानकारी

  • पेपर ID: 2510.13426
  • शीर्षक: RLIBM दृष्टिकोण का उपयोग करके तीव्र त्रिकोणमितीय फलन
  • लेखक: Sehyeok Park, Santosh Nagarakatte (Rutgers University)
  • वर्गीकरण: cs.PL (प्रोग्रामिंग भाषाएँ)
  • प्रकाशन सम्मेलन: अंतर्राष्ट्रीय वैज्ञानिक सॉफ्टवेयर सत्यापन कार्यशाला (VSS 2025)
  • पेपर लिंक: https://arxiv.org/abs/2510.13426

सारांश

यह पेपर RLIBM पद्धति का उपयोग करके त्रिकोणमितीय फलन बहुपद सन्निकटन विकसित करने के अनुभव का वर्णन करता है, जो कई प्रतिनिधित्व और पूर्णांकन मोड के लिए सही पूर्णांकित परिणाम उत्पन्न कर सकता है। त्रिकोणमितीय फलनों की मुख्य चुनौती π से संबंधित श्रेणी में कमी है, जो 32-बिट फ्लोटिंग पॉइंट डोमेन में इनपुट को छोटे डोमेन में कम करती है। π मान में कोई भी पूर्णांकन त्रुटि श्रेणी में कमी की प्रक्रिया के दौरान बढ़ाई जाती है, जिससे गलत परिणाम हो सकते हैं। लेखक तीव्र श्रेणी में कमी तकनीकों को लागू करने के अनुभव का वर्णन करते हैं, जो फ्लोटिंग पॉइंट और पूर्णांक गणना दोनों में π के बड़ी संख्या में बिट्स को बनाए रखते हैं। अंतिम त्रिकोणमितीय फलन कार्यान्वयन तीव्र है और सभी इनपुट के लिए सही पूर्णांकित परिणाम उत्पन्न करता है, जो 32 बिट तक के कई प्रतिनिधित्व का समर्थन करता है और केवल एक कार्यान्वयन की आवश्यकता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

मुख्य समस्याएँ

  1. सही पूर्णांकन की चुनौती: वैज्ञानिक गणना व्यापक रूप से गणितीय पुस्तकालयों द्वारा प्रदान किए गए बुनियादी फलनों का उपयोग करती है, लेकिन सभी इनपुट के लिए सही पूर्णांकित परिणाम उत्पन्न करना अत्यंत कठिन है ("तालिका निर्माता की दुविधा"), मुख्यधारा की गणितीय पुस्तकालयें सभी इनपुट के लिए सही परिणाम उत्पन्न नहीं कर सकती हैं।
  2. पोर्टेबिलिटी और पुनरुत्पादनीयता समस्याएँ: सही पूर्णांकन की कमी के कारण अनुप्रयोग विभिन्न मशीनों पर पूरी तरह से भिन्न परिणाम उत्पन्न करते हैं, जो पोर्टेबिलिटी और पुनरुत्पादनीयता को प्रभावित करता है।
  3. कई प्रतिनिधित्व प्रारूपों की आवश्यकता: कस्टम प्रारूपों (जैसे bfloat16, tensorfloat32, FP8) की वृद्धि के साथ, एक संदर्भ पुस्तकालय की आवश्यकता है जो कई प्रतिनिधित्व और पूर्णांकन मोड के लिए सही परिणाम प्रदान कर सके।

मौजूदा तरीकों की सीमाएँ

  • Minimax बहुपद सन्निकटन: पारंपरिक विधि सभी इनपुट की अधिकतम त्रुटि को कम करने वाले बहुपद सन्निकटन उत्पन्न करती है, लेकिन जब वास्तविक मान आउटपुट पूर्णांकन सीमा के बहुत करीब होता है, तो स्वतंत्रता की डिग्री में उल्लेखनीय कमी होती है।
  • प्रदर्शन और सही परिणामों का व्यापार: मौजूदा पुस्तकालयें प्रदर्शन (जैसे Payne-Hanek कार्यान्वयन) या सही परिणामों (जैसे GCC की libm) के पहलू में व्यापार करते हैं।

मुख्य योगदान

  1. कुशल श्रेणी में कमी तकनीकें: फ्लोटिंग पॉइंट और पूर्णांक संचालन को जोड़ने वाली कुशल श्रेणी में कमी एल्गोरिदम विकसित किया, जो सही परिणाम उत्पन्न करने के लिए पर्याप्त π बिट्स को बनाए रख सकता है।
  2. बहु-प्रतिनिधित्व एकल कार्यान्वयन: एक एकल बहुपद सन्निकटन लागू किया, जो 10-बिट से 32-बिट के कई प्रतिनिधित्व और सभी मानक पूर्णांकन मोड के लिए सही पूर्णांकित परिणाम उत्पन्न कर सकता है।
  3. प्रदर्शन अनुकूलन: पूर्णांक-आधारित श्रेणी में कमी फ्लोटिंग पॉइंट रणनीति की तुलना में 19% प्रदर्शन में सुधार करता है, समग्र रूप से मुख्यधारा की पुस्तकालयों की तुलना में तेज़ या तुलनीय प्रदर्शन है।
  4. संपूर्ण त्रिकोणमितीय फलन पुस्तकालय: sin, cos, tan फलनों के लिए तीव्र और सही कार्यान्वयन प्रदान किया।

विधि विवरण

RLIBM विधि मूल विचार

RLIBM विधि की मुख्य अंतर्दृष्टि सही पूर्णांकित परिणाम को सीधे सन्निकटित करना है, न कि फलन के वास्तविक मान को। दिए गए इनपुट के लिए सही पूर्णांकित परिणाम के लिए, एक वास्तविक मान अंतराल मौजूद है, जिसके भीतर कोई भी मान सही परिणाम में पूर्णांकित होगा। यह minimax विधि की तुलना में अधिक स्वतंत्रता प्रदान करता है (सभी इनपुट के लिए 1 ULP)।

बहु-प्रतिनिधित्व समर्थन तंत्र

कई प्रतिनिधित्वों का समर्थन करने के लिए, RLIBM परियोजना (n+2)-बिट प्रतिनिधित्व का बहुपद सन्निकटन उत्पन्न करने का प्रस्ताव देती है, round-to-odd पूर्णांकन मोड का उपयोग करते हुए। इस दृष्टिकोण के लाभ हैं:

  • round-to-odd परिणाम लक्ष्य प्रतिनिधित्व में सीधे पूर्णांकन के लिए आवश्यक सभी जानकारी को संरक्षित करता है
  • बाद में कम बिट-चौड़ाई प्रतिनिधित्व में पूर्णांकन सही परिणाम उत्पन्न करता है
  • दोहरे पूर्णांकन त्रुटियों से बचता है

श्रेणी में कमी एल्गोरिदम

बुनियादी सिद्धांत

त्रिकोणमितीय फलनों की श्रेणी में कमी इनपुट x∈-∞,∞ को कम किए गए इनपुट x'∈-π/2^(t+1), π/2^(t+1) में मैप करती है, जहाँ:

x = x' + kπ/2^t
k = [2^t * x/π]
x' = π/2^t * r, जहाँ r = 2^t*x/π - k

फ्लोटिंग पॉइंट कार्यान्वयन रणनीति

छोटे इनपुट प्रसंस्करण (|x| < 2^30):

  • 80-बिट के 256/π का उपयोग, दो double मानों में संग्रहीत
  • मध्यवर्ती पूर्णांकन त्रुटियों से बचता है
  • k और भिन्नात्मक भाग r को सटीक रूप से गणना करने के लिए आंशिक उत्पाद का उपयोग करता है

बड़े इनपुट प्रसंस्करण (2^30 ≤ |x|):

  • संस्करण 1: 256/π को 28-बिट खंडों में संग्रहीत करता है double सरणी में, प्रत्येक खंड truncation मोड का उपयोग करके उत्पन्न होता है
  • संस्करण 2: 53-बिट परिशुद्धता खंडों का उपयोग करता है, पूर्णांकन त्रुटि को कम करने के लिए fused-multiply-add निर्देशों का लाभ उठाता है

पूर्णांक कार्यान्वयन रणनीति

छोटे इनपुट अनुकूलन:

  • 80-बिट के 256/π का उपयोग, दो 40-बिट पूर्णांकों P1 और P0 में विभाजित
  • बिट शिफ्ट संचालन के माध्यम से पूर्णांक k और भिन्नात्मक बिट्स की पहचान करता है
  • फ्लोटिंग पॉइंट संचालन की परिशुद्धता हानि से बचता है

बड़े इनपुट प्रसंस्करण:

  • 192-बिट के 256/π का उपयोग, तीन 64-बिट पूर्णांकों में विभाजित
  • 128-बिट आंशिक उत्पाद की गणना करता है
  • बिट शिफ्ट संचालन के माध्यम से प्रासंगिक बिट्स निकालता है

आउटपुट मुआवजा

त्रिकोणमितीय पहचान का उपयोग करके आउटपुट मुआवजा:

sin(x) = sin(k'π/2^t)cos(x') + cos(k'π/2^t)sin(x')
cos(x) = cos(k'π/2^t)cos(x') - sin(k'π/2^t)sin(x')

पूर्वगणना तालिकाओं और आवधिकता/सममिति अनुकूलन के माध्यम से, आवश्यक पूर्वगणना मानों को 512 तक कम किया जाता है।

प्रयोगात्मक सेटअप

परीक्षण पर्यावरण

  • हार्डवेयर: 2.10GHz Intel Xeon(R) Silver 4310 सर्वर, 256GB RAM
  • ऑपरेटिंग सिस्टम: Ubuntu 24.04.1 LTS
  • माप उपकरण: प्रदर्शन काउंटर

तुलनात्मक पुस्तकालयें

  • GLIBC: float और double libm
  • Core-Math: सही पूर्णांकन पुस्तकालय
  • RLIBM कार्यान्वयन: श्रेणी में कमी रणनीतियों के कई प्रकार

मूल्यांकन मेट्रिक्स

  • सही परिणाम: सभी इनपुट की सही परिणामों के लिए पूर्ण गणना के माध्यम से सत्यापन
  • प्रदर्शन: अन्य पुस्तकालयों के सापेक्ष त्वरण

प्रयोगात्मक परिणाम

सही परिणामों का सत्यापन

  • RLIBM फलन: 10-बिट से 32-बिट सभी प्रतिनिधित्वों के सभी इनपुट के लिए सही पूर्णांकित परिणाम उत्पन्न करता है
  • GLIBC float libm: 32-बिट float इनपुट के sin, cos, tan में हजारों गलत परिणाम हैं
  • GLIBC double libm: float संस्करण की तुलना में अधिक सटीक लेकिन अभी भी त्रुटियाँ हैं
  • Core-Math: केवल 32-बिट के लिए सही परिणाम, 10-32 बिट श्रेणी में दोहरे पूर्णांकन त्रुटियों के कारण विफल

प्रदर्शन परिणाम

श्रेणी में कमी अनुकूलन प्रभाव

मिश्रित विधि (छोटे इनपुट के लिए फ्लोटिंग पॉइंट, बड़े इनपुट के लिए पूर्णांक) अन्य रणनीतियों की तुलना में:

  • प्रारंभिक फ्लोटिंग पॉइंट विधि (FP V1) की तुलना में 19% तेज़
  • वैकल्पिक फ्लोटिंग पॉइंट विधि (FP V2) की तुलना में महत्वपूर्ण सुधार
  • शुद्ध पूर्णांक विधि की तुलना में 4% तेज़

अन्य पुस्तकालयों के साथ तुलना

  • Core-Math की तुलना में औसतन 10% तेज़
  • GLIBC double फलन की तुलना में औसतन 137% तेज़
  • प्रदर्शन सुधार मुख्य रूप से कुशल श्रेणी में कमी और पूर्णांक संचालन की परिशुद्धता लाभ के कारण है

तकनीकी नवाचार बिंदु

1. परिशुद्धता और प्रदर्शन का संतुलन

  • पूर्णांक संचालन 64-बिट double की तुलना में अधिक परिशुद्धता प्रदान करता है (uint64_t और uint128_t)
  • इनपुट को कम करने के लिए पर्याप्त परिशुद्धता प्राप्त करने के लिए आवश्यक आंशिक उत्पादों की संख्या को कम करता है

2. मिश्रित श्रेणी में कमी रणनीति

  • छोटे इनपुट फ्लोटिंग पॉइंट संचालन का उपयोग करते हैं (जब 256*x/π का पूर्णांक भाग पर्याप्त छोटा हो)
  • बड़े इनपुट पूर्णांक संचालन का उपयोग करते हैं (अधिक परिशुद्धता और सरल बिट संचालन प्रदान करता है)

3. बिट संचालन अनुकूलन

  • 256*x/π में कम किए गए इनपुट और k के निम्न बिट्स से संबंधित भागों की पहचान करने के लिए बिट शिफ्ट संचालन का उपयोग करता है
  • फ्लोटिंग पॉइंट संचालन में पूर्णांकन संचय से बचता है

संबंधित कार्य

पारंपरिक विधियाँ

  • Minimax सन्निकटन: Remez एल्गोरिदम आदि, लेकिन पूर्णांकन सीमा के पास स्वतंत्रता की डिग्री सीमित है
  • Payne-Hanek एल्गोरिदम: शास्त्रीय श्रेणी में कमी विधि, लेकिन कार्यान्वयन दक्षता एक चुनौती है

सही पूर्णांकन अनुसंधान

  • CR-LIBM: प्रारंभिक सही पूर्णांकन पुस्तकालय, लेकिन प्रदर्शन धीमा है
  • Core-Math: आधुनिक सही पूर्णांकन कार्यान्वयन, लेकिन केवल एकल प्रतिनिधित्व का समर्थन करता है

RLIBM परियोजना विकास

  • बुनियादी फलनों (e^x, log आदि) से त्रिकोणमितीय फलनों तक विस्तार
  • बहु-प्रतिनिधित्व समर्थन के लिए नवीन दृष्टिकोण

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. व्यवहार्यता प्रमाण: त्रिकोणमितीय फलनों के लिए तीव्र और सही कार्यान्वयन उत्पन्न करना संभव है
  2. श्रेणी में कमी की महत्ता: कुशल श्रेणी में कमी निम्न-डिग्री बहुपद सन्निकटन के समान महत्वपूर्ण है
  3. पूर्णांक संचालन लाभ: पूर्णांक-आधारित कार्यान्वयन बड़े इनपुट पर फ्लोटिंग पॉइंट विधि से महत्वपूर्ण रूप से बेहतर है

सीमाएँ

  1. जटिलता: कार्यान्वयन जटिलता अधिक है, सटीक बिट संचालन और कई रणनीतियों की आवश्यकता है
  2. मेमोरी ओवरहेड: पूर्वगणना तालिकाओं और बहु-परिशुद्धता स्थिरांकों के भंडारण की आवश्यकता है
  3. स्केलेबिलिटी: उच्च परिशुद्धता प्रतिनिधित्व तक विस्तार के लिए पुनः डिज़ाइन की आवश्यकता है

भविष्य की दिशाएँ

  1. GPU प्लेटफॉर्म: GPU प्लेटफॉर्म के लिए सही पूर्णांकन पुस्तकालय की खोज करना
  2. मानकीकरण: IEEE-754 मानक समिति के साथ भाग लेना सही पूर्णांकन को अनिवार्य करने के लिए
  3. मुख्यधारा एकीकरण: इन विधियों को एकीकृत करने के लिए मुख्यधारा की गणितीय पुस्तकालय विकासकर्ताओं के साथ सहयोग

गहन मूल्यांकन

शक्तियाँ

  1. सिद्धांत और व्यवहार का संयोजन: RLIBM सिद्धांत को चुनौतीपूर्ण त्रिकोणमितीय फलनों में सफलतापूर्वक लागू करता है
  2. व्यापक इंजीनियरिंग अनुकूलन: एल्गोरिदम से कार्यान्वयन तक सर्वांगीण अनुकूलन
  3. कठोर सत्यापन: पूर्ण गणना के माध्यम से सही परिणामों का सत्यापन
  4. व्यावहारिक मूल्य: वास्तविक अनुप्रयोगों में महत्वपूर्ण समस्याओं को हल करता है

कमियाँ

  1. कार्यान्वयन जटिलता: कई रणनीतियों का संयोजन कार्यान्वयन और रखरखाव जटिलता को बढ़ाता है
  2. पठनीयता: बड़ी संख्या में बिट संचालन कोड की पठनीयता और रखरखाव योग्यता में सुधार की आवश्यकता है
  3. सैद्धांतिक विश्लेषण: पूर्णांक विधि अधिक क्यों है इसके गहन सैद्धांतिक विश्लेषण की कमी है

प्रभाव

  1. शैक्षणिक योगदान: संख्यात्मक गणना क्षेत्र के लिए नई सही पूर्णांकन कार्यान्वयन विधि प्रदान करता है
  2. व्यावहारिक मूल्य: उच्च परिशुद्धता संख्यात्मक गणना की आवश्यकता वाले वैज्ञानिक गणना में सीधे लागू किया जा सकता है
  3. मानक संचालन: भविष्य की फ्लोटिंग पॉइंट मानकों के विकास को प्रभावित कर सकता है

लागू दृश्य

  1. वैज्ञानिक गणना: उच्च परिशुद्धता और पुनरुत्पादनीयता की आवश्यकता वाली संख्यात्मक सिमुलेशन
  2. वित्तीय गणना: सटीक परिणामों की आवश्यकता वाली वित्तीय मॉडलिंग
  3. एम्बेडेड सिस्टम: कई फ्लोटिंग पॉइंट प्रारूपों का समर्थन करने वाली प्रणालियाँ
  4. संदर्भ कार्यान्वयन: अन्य पुस्तकालयों के सही परिणामों के लिए आधार के रूप में

संदर्भ

यह पेपर संख्यात्मक विश्लेषण, फ्लोटिंग पॉइंट संचालन और सही पूर्णांकन क्षेत्र के महत्वपूर्ण साहित्य का हवाला देता है, जिसमें शामिल हैं:

  • Muller की बुनियादी फलन संदर्भ पुस्तक
  • MPFR उच्च परिशुद्धता पुस्तकालय
  • Payne-Hanek श्रेणी में कमी एल्गोरिदम
  • IEEE-754 फ्लोटिंग पॉइंट मानक संबंधित अनुसंधान

यह पेपर संख्यात्मक गणना क्षेत्र में महत्वपूर्ण योगदान देता है, सैद्धांतिक विधियों को व्यावहारिक उच्च-प्रदर्शन कार्यान्वयन में सफलतापूर्वक परिवर्तित करता है, और वैज्ञानिक गणना में सही पूर्णांकन समस्या के लिए प्रभावी समाधान प्रदान करता है।