CORDIC एल्गोरिदम मेरे दिमाग में स्थायी रूप से क्यों बस गया

 (github.com/francisrstokes)
3 पॉइंट द्वारा GN⁺ 2024-05-12 | 1 टिप्पणियां | WhatsApp पर शेयर करें

CORDIC एल्गोरिदम मेरे मन में मुफ़्त में क्यों रहता है

Floating Point से बचने के लिए Fixed Point का उपयोग

  • Floating Point की बजाय Fixed Point का उपयोग करने से वास्तविक संख्याओं को दर्शाया जा सकता है
  • 32-बिट integer type का उपयोग करके ऊपरी 16 बिट को integer भाग और निचले 16 बिट को fractional भाग के रूप में बाँटकर इस्तेमाल किया जाता है
  • इससे लगभग -32768.99997 से 32767.99997 तक मान व्यक्त किए जा सकते हैं
  • programmer दशमलव बिंदु की स्थिति तय करके precision को नियंत्रित कर सकता है
  • Float को Fixed Point में बदलने के लिए 2^16 से गुणा करने के बाद int32_t में cast करें
  • Fixed Point को Float में बदलने के लिए 2^16 से भाग दें
  • जोड़ और घटाव वैसे ही काम करते हैं, जबकि गुणा और भाग में scaling factor को समायोजित करना पड़ता है

CORDIC एल्गोरिदम का अवलोकन

  • CORDIC, "Co-ordinate Rotation Digital Computer" का संक्षिप्त रूप है, और इसे 1950 के दशक के मध्य में विकसित किया गया था
  • unit circle पर एक vector को क्रमशः छोटे-छोटे कोणों से घुमाकर sine और cosine मान निकालने की विधि
  • binary search की तरह, लक्ष्य कोण के करीब पहुँचने के लिए पहले बड़े कोण से बढ़ते हैं, फिर clockwise या counterclockwise दिशा में कोण को आधा-आधा घटाते हुए converge करते हैं
  • अधिकतम rotation angle को 90 डिग्री (π/2 radian) मानकर, 16 iterations के जरिए लक्ष्य कोण के पास converge किया जाता है
  • converge हुए vector का y मान लगभग sin(a) और x मान लगभग cos(a) होता है

केवल constant multiplication का उपयोग करने के लिए matrix को सरल बनाना

  • rotation matrix में sine, cosine, tangent functions शामिल होते हैं, इसलिए गणना जटिल होती है
  • tangent function में उपयोग होने वाले निश्चित कोणों को पहले से गणना करके table में संग्रहीत किया जा सकता है (लगभग 64 bytes)
  • cosine term हर iteration में आता है, लेकिन इसका converged मान एक constant (लगभग 0.6366) होता है, इसलिए अंत में इसे केवल एक बार गुणा करना पर्याप्त है

केवल Shift और Add operations का उपयोग

  • tangent function में प्रयुक्त कोणों को arctangent function की मदद से 2^-i मान के रूप में चुना जाता है
  • इससे multiplication की जगह bit shift operation का उपयोग किया जा सकता है
  • cosine term के converged मान की फिर से गणना करने पर यह लगभग 0.60725 आता है, और इसे शुरुआती vector के x मान के रूप में सेट किया जाता है
  • CORDIC एल्गोरिदम की हर iteration को इस तरह सरल किया जाता है
    • यदि z 0 या उससे बड़ा है, तो counterclockwise घुमाएँ (x से y>>i घटाएँ, y में x>>i जोड़ें)
    • यदि z 0 से छोटा है, तो clockwise घुमाएँ (x में y>>i जोड़ें, y से x>>i घटाएँ)
    • table से angle value घटाकर या जोड़कर z को update करें
  • इस तरह केवल constant multiplication, bit shift, और addition operations से trigonometric functions की गणना संभव हो जाती है

GN⁺ की राय

  • CORDIC एक ऐसा एल्गोरिदम लगता है जो embedded systems या FPGA जैसे सीमित hardware resources वाले वातावरण में उपयोगी हो सकता है। खासकर तब, जब floating-point operations का समर्थन न हो।
  • tangent function के कोणों को रणनीतिक रूप से चुनकर multiplication को bit shift से बदलने का विचार प्रभावशाली है। यह गणितीय अंतर्दृष्टि और computer architecture की समझ के संयोजन का अच्छा उदाहरण है।
  • केवल trigonometric functions ही नहीं, बल्कि logarithm, exponential, square root जैसी कई अन्य functions की गणना में भी इसका उपयोग हो सकता है—यह बात भी दिलचस्प है। संबंधित एल्गोरिदम BKM को भी साथ में देखना उपयोगी हो सकता है।
  • हालांकि, आधुनिक hardware में अक्सर पहले से FPU शामिल होता है, और fixed-point arithmetic का उपयोग करने पर precision loss हो सकता है, इसलिए इसे लागू करते समय सावधानी की जरूरत है.
  • अगर किसी system में इस तरह की गणनाएँ बहुत अधिक करनी हों, तो CORDIC-विशिष्ट hardware design पर भी विचार किया जा सकता है.

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-05-12
Hacker News राय

  • CORDIC एल्गोरिदम का उपयोग सिर्फ FPGA में ही नहीं, बल्कि game development या distributed physics simulation जैसी चीज़ों में भी किया जा सकता है। floating point गणनाओं में अलग-अलग platforms के बीच deterministic behavior की गारंटी देना मुश्किल होता है, इसलिए fixed-point physics engine बनाकर और CORDIC से trigonometric functions implement करके यह एक समाधान हो सकता है.

  • CORDIC का उपयोग सिर्फ sine और cosine ही नहीं, बल्कि log, exponent, square root, vector magnitude, polar-cartesian coordinate conversion, vector rotation जैसी कई तरह की operations में किया जा सकता है। quaternion का उपयोग करने पर CORDIC-आधारित गणनाएँ और अधिक efficient और accurate हो सकती हैं.

  • हाई स्कूल की pre-calculus class में calculator के trigonometric functions के implementation के बारे में पढ़ा था, और बाद में पता चला कि वह Taylor series नहीं बल्कि वास्तव में CORDIC था। इसे TI Basic में खुद implement करके देखने का अनुभव भी साझा किया गया.

  • 2023 तक STM32G4 जैसे low-cost MCU में भी FPU built-in आता है, इसलिए fixed-point की जगह floating point का आसानी से उपयोग किया जा सकता है। लेकिन G4 में dedicated hardware के रूप में implemented CORDIC peripheral भी है, जो शायद floating point precision loss से बचने के लिए है.

  • 22.75° rotation, 45° rotation के बाद -22.5° rotation के बराबर है — इस व्याख्या में शायद गलती है। 22.5° सही लगता है.

  • Meagher का octree system integer multiplication/division के बिना, सिर्फ integer operations से implement किया गया था। इससे octree representation के लिए तेज़ और custom-built VLSI graphics acceleration hardware बनाना आसान हुआ.

  • CORDIC को angles के लिए Farey sequence (या mediant, naive fraction sum) जैसी अवधारणा के रूप में भी देखा जा सकता है.

  • CORDIC को 4-bit CPU वाले vintage programmable HP calculators पर भी implement किया गया था। sine function की Taylor expansion का उपयोग करने वाली approximation method भी program की जा सकती है.

  • अगर यह लेख पसंद आया हो, तो mathematical algorithms को examples के साथ समझाने वाली Donald Knuth की प्रसिद्ध पुस्तक "The Art of Computer Programming" पढ़ना भी अच्छा रहेगा.

  • CORDIC पहले DSP क्षेत्र में बहुत लोकप्रिय एल्गोरिदम था.

  • यह एक शानदार एल्गोरिदम है, और लगता है कि low-performance hardware पर neural networks चलाने में भी उपयोगी हो सकता है।