फास्ट inverse square root एल्गोरिदम के बारे में सब कुछ

फास्ट inverse square root एल्गोरिदम के बारे में सब कुछ

एल्गोरिदम

• फास्ट inverse square root एल्गोरिदम Quake 3 source code की वजह से मशहूर हुआ एल्गोरिदम है, और इसे John Carmack ने इस्तेमाल किया था।
• यह एल्गोरिदम floating-point के बिट्स को manipulate करके inverse square root को तेज़ी से calculate करता है।
• कोड उदाहरण:

  float Q_rsqrt(float number) {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
  
    x2 = number * 0.5F;
    y = number;
    i = *(long*)&y;              // 부동 소수점 비트 수준 해킹
    i = 0x5f3759df - ( i >> 1 ); // 마법의 상수
    y = *(float*)&i;
    y = y * ( threehalfs - ( x2 * y * y ) );  // 1차 반복
  
    return y;
  }
  

32-बिट floating-point: representation

• IEEE-754 32-बिट floating-point 3 components से मिलकर बना होता है:
  • sign: 1 बिट, यह बताता है कि संख्या positive है या negative।
  • exponent: 8 बिट, यह संख्या की range तय करता है।
  • mantissa: 23 बिट, यह range के भीतर संख्या की स्थिति तय करता है।
• वास्तविक मान इस प्रकार calculate किया जाता है:

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

32-बिट floating-point: bit interpretation

• floating-point का internal representation आम तौर पर programmers के लिए महत्वपूर्ण नहीं होता।
• लेकिन इस representation को अच्छी तरह समझने से efficient एल्गोरिदम design करना संभव होता है।
• floating-point के bit pattern को integer की तरह interpret करने पर log function का approximate value मिलता है।

  log2(x) ≈ Ix / L - B
  

Newton method

• शुरुआती approximation को बेहतर बनाने के लिए Newton method का उपयोग किया जाता है।
• Newton method एक ऐसा एल्गोरिदम है जो किसी दिए गए function के approximate value को बार-बार सुधारता है।
• कोड उदाहरण:

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

निष्कर्ष

• यह एल्गोरिदम floating-point system के internal mathematical details की गहरी समझ और कंप्यूटर पर तेज़ी से चलने वाले operations का उपयोग करके design किया गया था।
• एल्गोरिदम की उत्पत्ति निश्चित नहीं है, लेकिन यह बेहद efficient और अच्छी तरह design की गई engineering का एक उदाहरण है।

GN⁺ की राय

• ऐतिहासिक महत्व: यह एल्गोरिदम उस समय के hardware constraints को पार करने के लिए बनाया गया एक innovative तरीका था।
• शैक्षिक मूल्य: floating-point की internal structure और mathematical principles को समझने में यह बहुत मददगार है।
• आधुनिक उपयोग: आधुनिक hardware में इसकी ज़रूरत कम हो सकती है, लेकिन एल्गोरिदम के principles आज भी उपयोगी हैं।
• optimization की संभावना: एल्गोरिदम के constant values को optimize किया जा सकता है, और इस पर आगे research की गुंजाइश है।
• आलोचनात्मक दृष्टिकोण: आधुनिक hardware में इससे बेहतर तरीके हो सकते हैं, इसलिए हमेशा इसे नई तकनीकों के साथ तुलना करना महत्वपूर्ण है।

[joyfui]

कभी-कभी फिर से सामने आ जाने वाला एक दिलचस्प कोड..ह

[GN⁺]

Hacker News राय

• SSE कमांड सपोर्ट: 1999 के बाद बने कंप्यूटर SSE instruction set को सपोर्ट करते हैं, और _mm_rsqrt_ps कमांड के जरिए inverse square root को तेज़ी से कैलकुलेट किया जा सकता है.

• आधुनिक हार्डवेयर की प्रगति: आधुनिक हार्डवेयर में inverse square root की गणना CPU पर तेज़ी से की जा सकती है, और यह मानना गलत है कि सभी floating-point operations को GPU पर offload किया जाता है.

• MMIX इम्प्लीमेंटेशन: MMIX भाषा में inverse square root कैलकुलेट करने का एक उदाहरण कोड है. यह कोड मूल रूप से मानता है कि संख्या 2^-1021 से बड़ी है.

• फ़ॉर्मूला में टाइपो: floating-point फ़ॉर्मूला में एक टाइपो है. इसे (-1)^S में सुधारा जाना चाहिए.

• लॉग की व्याख्या: raw bit pattern की व्याख्या करना log का piecewise linear approximation नहीं है. डेटा पॉइंट्स के बीच की रेखाएँ वास्तव में मौजूद नहीं हैं.

• Wikipedia संदर्भ: इस फ़ंक्शन और इसके इतिहास पर अच्छी चर्चा Wikipedia में है. Wikipedia लिंक

• GitHub कोड संग्रह: संबंधित कुछ कोड GitHub पर एकत्र किए गए हैं. GitHub लिंक

• StackOverflow संदर्भ: optimized low-accuracy approximation पर StackOverflow का यह सवाल भी देखने लायक है. StackOverflow लिंक

• 3D engine optimization अनुभव: Quake से पहले 3D engine बनाते समय optimization का अनुभव मिला, और algorithm optimization हमेशा जीतता है.

• YouTube वीडियो सिफारिश: इस विषय पर एक दिलचस्प वीडियो है. YouTube लिंक

• उत्पादक समय का चोर: इस विषय में इतना डूब गया कि बहुत सारा productive समय निकल गया.

• सर्वोत्तम magic number: मशहूर code snippet में इस्तेमाल किया गया magic number optimal constant नहीं है. इससे बेहतर constant ढूँढ़ना संभव है, और Jupyter notebook के जरिए optimal magic number पाया जा सकता है.