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

(github.com/francisrstokes)

3 पॉइंट द्वारा GN⁺ 2024-05-12 | 1 टिप्पणियां | WhatsApp पर शेयर करें

CORDIC एक ऐसा एल्गोरिद्म है जो FPU या बड़े lookup table के बिना sin, cos, tan जैसी trigonometric functions की गणना करने के लिए जटिल operations को मुख्य रूप से addition और bit shift में बदल देता है
यह तरीका high-performance systems की तुलना में embedded environments, खासकर कम performance वाले microcontrollers और FPGA में उपयोगी है, और इसकी value को सिर्फ speed से आंकना मुश्किल है
floating-point के बजाय fixed-point इस्तेमाल करने पर int32_t के upper 16 bits को integer part और lower 16 bits को fractional part में बांटकर लगभग -32768.99997 से 32767.99997 तक represent किया जा सकता है
vector को target angle के अनुसार धीरे-धीरे छोटे angles से rotate किया जाता है, और atan(2**-i) की 16-entry table तथा x=39796 initial value इस्तेमाल करने पर हर iteration में multiplication को bit shift से बदला जा सकता है
example angle 0.9152 पर 16 iterations करने से sin(0.9152) का absolute error 0.00000956 और cos(0.9152) का absolute error 0.0000434 के स्तर तक घट जाता है

CORDIC के लिए उपयुक्त computation environment

CORDIC sin, cos, tan जैसी trigonometric functions को low-power hardware पर calculate करने के लिए एक एल्गोरिद्म है
यह FPU, यानी floating-point unit, न होने पर या बड़े lookup table का इस्तेमाल करना मुश्किल होने वाले environment में भी काम करता है
असली operations मुख्य रूप से सरल addition और bit shift से बने होते हैं
यह vector math, trigonometry, convergence और computer science ideas को जोड़कर complex functions को simple operations से approximate करता है
high-performance hardware में यह technique हमेशा जरूरी नहीं हो सकती
- इसका मुख्य application target embedded environment है
- यह खास तौर पर कम performance वाले microcontrollers और FPGA के लिए उपयुक्त है
- तेज hardware या peripherals भी हो सकते हैं, लेकिन speed ही usefulness का अकेला पैमाना नहीं है

floating-point से बचने वाला fixed-point representation

sin(x) जैसी function, जो -1.0 से 1.0 के बीच value देती है, उसे भी जरूरी नहीं कि floating-point में ही represent किया जाए
fixed-point integer type के अंदर decimal point की position fixed करके rational numbers को represent करता है
example में int32_t को upper 16-bit integer part और lower 16-bit fractional part में बांटा गया है
- इस case में range लगभग -32768.99997 से 32767.99997 तक होती है
- decimal point को कहां रखा जाए, इसके अनुसार integer-part range और fractional-part precision के बीच trade-off किया जा सकता है
value खुद अब भी int32_t ही रहती है, और programmer bit array को अतिरिक्त meaning देता है

fixed-point conversion और basic operations

अगर fractional precision 16 bits है, तो 42.01 जैसी float value को (1 << 16) से multiply करके fixed-point value बनाया जा सकता है
- 42.01 * (1 << 16) को int32_t में cast करने पर 2753167 मिलता है
- फिर float में बदलने के लिए 2753167 / (1 << 16) calculate करने पर लगभग 42.0099945 मिलता है
floating-point बिल्कुल इस्तेमाल किए बिना 1.5 जैसी value को सीधे encode भी किया जा सकता है
- integer part 1 को (1 << 16) से ऊपर उठाया जाता है
- fractional part का आधा हिस्सा 0x0000 और 0xffff के बीच की middle value 0x7fff रखा जा सकता है
- इस तरीके का result decimal 98303 है
समान scaling factor इस्तेमाल करने वाली values के बीच addition और subtraction वैसे ही काम करते हैं
multiplication में दो fixed-point values को multiply करने के बाद result को scaling factor जितना फिर से right shift किया जाता है
division में dividend को scaling factor जितना पहले left shift करके divisor से divide करने पर additional precision मिल सकती है

vector rotation से trigonometric functions approximate करना

CORDIC “co-ordinate rotation digital computer” का acronym है, और इसे 1950 के दशक के मध्य में बनाया गया था
core idea यह है कि unit circle पर vector को धीरे-धीरे छोटे angles से rotate किया जाए, ताकि target angle पर पहुंचने पर vector components sine और cosine values बन जाएं
यह process binary search जैसी चलती है
- target angle की ओर बड़े angle से move किया जाता है
- check किया जाता है कि target पार तो नहीं हो गया
- इसके बाद और छोटे angle से clockwise या counterclockwise rotation repeat किया जाता है
example के तौर पर sin(0.7) निकालते समय initial vector (1, 0) और target 0.7 radians से शुरू किया जाता है
- पहले 0.7853 radians, यानी 45˚, counterclockwise rotate किया जाता है
- बचा हुआ target 0.7 - 0.7853 = -0.0853 हो जाता है
- value negative है, इसलिए अगली बार 0.3926 radians, यानी 22.5˚, clockwise rotate किया जाता है
- इसके बाद बचे हुए target के sign के अनुसार 0.1963 radians आदि और छोटे angles पर direction बदलते हुए rotation किया जाता है
16 iterations के बाद vector original target angle के लगभग align हो जाता है, और y sin(a) का तथा x cos(a) का approximation बन जाता है

rotation matrix में महंगे operations घटाना

सामान्य vector rotation में sine और cosine वाली matrix multiplication इस्तेमाल होती है
CORDIC trigonometric identities का इस्तेमाल करके rotation matrix को tan(a) केंद्रित रूप में बदलता है
शुरुआत में 45˚, 22.5˚, 11.25˚ जैसे predefined rotation angles इस्तेमाल किए जाते हैं, इसलिए tan(a) values को precomputed table में रखा जा सकता है
इस table के लिए केवल 16 uint32_t चाहिए, यानी 64 bytes
- तुलना के लिए, -1 से 1 तक 4096 values रखने वाली unoptimized sin(x) table को 16KiB चाहिए और इसकी precision भी कम मानी जाती है
हर rotation में आगे लगने वाला cos(a) term हर iteration में आता है, लेकिन इन सबका product एक constant पर converge करता है
- 45˚, 22.5˚, 11.25˚ जैसे angles इस्तेमाल करने पर यह product लगभग 0.6366 होता है
- इस constant को सभी iterations के बाद एक बार multiply करना पर्याप्त है

सिर्फ shift और addition छोड़ने वाला angle selection

multiplication हटाने के लिए angle ऐसे चुने जाते हैं कि tan(a) का result हमेशा 2 की inverse power हो
इसके लिए हर iteration i=0 से 15 तक atan(2**-i) values वाली 16-entry table बनाई जाती है
असली rotation angles 45˚, 26.565˚, 14.036˚, 7.125˚ आदि बनते हैं
angles बिल्कुल आधे-आधे नहीं घटते, लेकिन इन angles का इस्तेमाल करने पर भी process सही result पर converge करता है
tan(a) multiplication iteration number i जितने bit shift में बदल जाता है
cos(a) terms का product भी नए angle selection के अनुसार दोबारा calculate होता है
- value लगभग 0.60725 है
- 16-bit fixed-point में यह 39796 बनता है
- अंत में multiply करने के बजाय initial vector के x को 1 नहीं बल्कि 39796 set किया जा सकता है

एल्गोरिद्म की प्रक्रिया

precomputation step में ऐसी table बनाई जाती है जिसमें हर entry atan(2**-i) हो, और हर value को fixed-point में convert किया जाता है
- conversion formula atan(2**-i) * (1 << 16) है
sin या cos निकालते समय input angle को भी fixed-point में बदला जाता है
- example 0.9152 0.9152 * (1 << 16) = 59978 बनता है
initial state इस प्रकार है

x = 39796
y = 0
z = 59978

z vector का हिस्सा नहीं है, बल्कि बचा हुआ target angle track करने वाली value है
z का sign rotation direction तय करता है
- अगर z >= 0 है, तो counterclockwise rotate करके z -= table[i] किया जाता है
- अगर z < 0 है, तो clockwise rotate करके z += table[i] किया जाता है
हर iteration x और y के लिए केवल addition, subtraction और >> i shift इस्तेमाल करता है

if z >= 0:
    x_next = x - (y >> i)
    y_next = y + (x >> i)
    z -= table[i]
else:
    x_next = x + (y >> i)
    y_next = y - (x >> i)
    z += table[i]
x = x_next
y = y_next

example convergence result और बाकी topics

0.9152 radians वाले example में पहले iteration में z positive है, इसलिए लगभग 0.785 radians counterclockwise rotate किया जाता है
दूसरे iteration में भी z positive है, इसलिए लगभग 0.436 radians counterclockwise rotate होता है, लेकिन target पार हो जाता है
तीसरे iteration में z negative हो जाता है, इसलिए लगभग 0.244 radians clockwise rotate किया जाता है
चौथे iteration में भी z negative है, इसलिए लगभग 0.124 radians clockwise rotate किया जाता है
angle changes छोटे होते जाने पर vector actual result के करीब आगे-पीछे move करते हुए converge करता है
16 iterations के बाद y, sin(0.9152) का बहुत करीबी approximation बन जाता है
- sine absolute error 0.00000956 है
- x का cosine absolute error 0.0000434 है
कुछ topics अभी बाकी हैं
- जब interest का angle unit circle के 1st quadrant या 4th quadrant के बाहर हो, तब जरूरी special handling
- CORDIC variants से calculate किए जा सकने वाले tan, atan, asin, acos, sinh, cosh, tanh, sqrt, ln, e^x
- logarithm और exponential calculation के लिए designed संबंधित एल्गोरिद्म BKM
संबंधित content को Low Byte Productions YouTube channel पर और detail में cover करने की योजना है

1 टिप्पणियां

GN⁺ 2024-05-12

Hacker News टिप्पणियां

लेखक ने कहा कि यह मुख्यतः FPGA जैसी जगहों पर लागू होता है, लेकिन इसे game development या distributed physics simulation में भी इस्तेमाल किया जा सकता है
floating-point calculation में अलग-अलग platforms के बीच determinism मिलाना मुश्किल होता है, और एक समाधान यह है कि floating point से पूरी तरह बचकर fixed-point physics engine implement किया जाए
trigonometric functions implement करने के लिए CORDIC जैसी चीज़ की ज़रूरत होती है
कुछ साल पहले मैंने मज़े-मज़े में ऐसी चीज़ बनानी शुरू की थी, लेकिन पूरी नहीं कर पाया; कभी फिर से आज़माना चाहूंगा
https://randomascii.wordpress.com/2013/07/16/floating-point-...
- वह लेख अब 10 साल पुराना है, लेकिन उसमें एक अहम quote है: “IEEE standard कुछ चीज़ों की गारंटी देता है। floating-point math को रहस्यवाद जैसा मानने वाले लोगों को जितना पता है, उससे ज़्यादा गारंटी देता है, लेकिन कुछ programmers जितना सोचते हैं, उससे कम गारंटी देता है”
  संक्षेप में, x87 में कुछ अजीब बातें थीं; rounding mode और flush-to-zero जैसी settings को लगातार समान रखना पड़ता है; पुराने processors में FMA नहीं था; mmsqrtps जैसे approximate instructions की consistent specification नहीं होती; और compiler expressions को reassociate कर सकता है
  अगर छोटी routines या खुद लिखी हुई library हो, तो दर्दनाक होने के बावजूद यह सुनिश्चित करना संभव है कि इन चीज़ों से बचा जाए
  IEEE-754 2008 ने specification को और साफ़ किया और असल में x87 के अंत को मानकर चला; 2024 में x87 से निश्चित रूप से बचा जा सकता है
  FMA भी IEEE-754 2008 specification का हिस्सा है और Intel Haswell के बाद वाले सहित आधुनिक processors में मौजूद है
  फिर भी 8-wide AVX2 और 4-wide NEON जैसी architecture differences अड़चन बन सकती हैं, लेकिन assembly या intrinsics, या Compiler Explorer/objdump से verify की गई C इस्तेमाल करें, तो output देखकर कहा जा सकता है कि “यह consistent रहेगा”
- लेखक ने भी कहा कि hardware performance improvements की वजह से floating point के व्यापक इस्तेमाल से पहले fixed point game development में बहुत आम था, और संभावना है कि CORDIC भी साथ में इस्तेमाल होता था
  “असल में, IEEE 754 के आज जितना popular standard बनने से पहले fixed point हमेशा इस्तेमाल होता था। 1980 से लगभग 2000 के बीच काम करने वाले किसी game developer से पूछें, वे विस्तार से बताएंगे”
- game development के लिए physics simulation library nphysics ने cross-platform determinism की ज़रूरत होने पर CORDIC के साथ fixed-point math इस्तेमाल करने का तरीका चुना था, लेकिन अब उसे deprecate कर दिया गया है
  nphysics को दोबारा लिखकर बनी नई library Rapier इसके बजाय IEEE-754 2008 की guarantees पर भरोसा करके cross-platform determinism देती है
  इसलिए यह पुराने platforms पर काम नहीं करती, लेकिन wasm सहित modern platforms पर deterministic है
  बेशक, हर platform द्वारा दिए जाने वाले sin, cos जैसे transcendental function routines पर निर्भर नहीं रहा जा सकता; उन्हें हर जगह एक ही तरीके से काम करने के लिए खुद implement करना होगा
  लेकिन अगर non-compliant platforms पर run न करें, तो यह approach संभव है
  https://www.rustsim.org/blog/2020/06/01/this-month-in-rustsi...
  https://rapier.rs/docs/user_guides/rust/determinism/
CORDIC को sine और cosine की calculation/generation के अलावा log, exponential, square root, vector magnitude, polar-to-Cartesian coordinate conversion, vector rotation जैसे कई operations के लिए भी इस्तेमाल किया जा सकता है
लेखक ने conclusion में भी इस संभावना की ओर इशारा किया है
मौजूदा orthonormal matrices की जगह quaternions इस्तेमाल करने पर लगता है कि CORDIC-based operations को ज़्यादा efficient तरीके से—यानी कम computation cycles और memory के साथ, और कम error रखते हुए—चलाया जा सकता है
https://core.ac.uk/works/8439118
- अगर मेरी याद सही है, तो इसे arbitrary Lie groups तक भी extend किया जा सकता है
high school pre-calculus में Taylor series पढ़ी थी, और teacher ने कहा था कि calculator की trigonometric functions असल में इसी तरह implement होती हैं
खोजने पर पता चला कि वास्तव में वह CORDIC था, और TI Basic में implement करके मैंने खूब मज़े किए
- यह पढ़ना दिलचस्प होगा कि कमाल का Sinclair scientific calculator trigonometric functions और logs वगैरह कैसे calculate करता था
  CORDIC नहीं था, लेकिन algorithm में कुछ समानताएं हैं
  http://files.righto.com/calculator/sinclair_scientific_simul...
- क्या कोई calculator वास्तव में Taylor expansion इस्तेमाल करता भी है?
हार्डवेयर implementation से जुड़े लेख:
https://arxiv.org/pdf/2211.04053
https://hal.science/hal-01327460/document
https://archive.ll.mit.edu/HPEC/agendas/proc05/Day_1/Abstrac...
देखना चाहता/चाहती हूँ कि अलग-अलग दौर के विभिन्न hardware पर यह सामान्य software·hardware त्रिकोणमितीय function implementation से कैसे तुलना करता है
- CORDIC एक व्यापक रूप से इस्तेमाल होने वाली और बहुत लोकप्रिय computer technique है, फिर भी किताबों में इसे ठीक से विस्तार में नहीं लिया जाता—यह अजीब लगता है
  IoT और machine-to-machine communication बढ़ रहे हैं, और CORDIC implementation व operation efficiency को देखते हुए इसका उपयोग शायद काफी बढ़ेगा, इसलिए सही और optimized implementation के लिए अच्छे references की जरूरत है
  अपवाद के तौर पर Prof. Omondi और Prof. Deschamps की किताबें हैं
  https://www.worldscientific.com/worldscibooks/10.1142/p1054
  http://www.arithmetic-circuits.org/guide2fpga/vhdl_codes.htm
sin और cos अक्सर vector rotation में इस्तेमाल होते हैं
इस मामले में CORDIC की तरकीब यह है कि पारंपरिक sin/cos/multiplication calculation से बचा जाए और जिस vector को rotate करना है, उसी को CORDIC के input के रूप में दे दिया जाए
तब CORDIC sin/cos calculate किए बिना या complex number multiplication किए बिना सीधे rotated vector बना देता है
CORDIC खासकर तब चमकता है जब latency बहुत critical न हो
calculation के हर step को pipeline करने पर काफी throughput मिल सकता है, इसलिए यह wireless systems की digital mixing के लिए अच्छी तरह फिट बैठता है
2023 तक कुछ modern MCU low-cost होने के बावजूद FPU रखते हैं
STM32G4 एक अच्छा उदाहरण है, और M0 MCU जैसे मामलों के उलट, अगर fixed-point इस्तेमाल नहीं करना चाहते तो f32 को खुलकर इस्तेमाल किया जा सकता है
ऐसे chips लगभग 1–2 डॉलर प्रति MCU में मिल सकते हैं
हालांकि G4 में fixed-point उपयोग के लिए इस algorithm को implement करने वाला hardware CORDIC peripheral भी है
मुझे जिज्ञासा है कि क्या यह मुख्य रूप से floating-point precision loss से बचने के लिए है
इसे registers से program किया जाता है, लेकिन CPU पर सीधे CORDIC implement नहीं होता; IC के अंदर dedicated hardware इसे process करता है
- Digi-Key stock के आधार पर duplicates हटाने पर सबसे सस्ते Cortex-M4F करीब 3 डॉलर वाला Nuvoton M481LE8AE https://www.digikey.com/en/products/detail/nuvoton-technolog..., 3 डॉलर वाला Maxim MAX32660 https://www.digikey.com/en/products/detail/analog-devices-in..., और 5 डॉलर वाला Atmel ATSAMD51 https://www.digikey.com/en/products/detail/microchip-technol... जैसे हैं
  सबसे सस्ता STM32G4 STM32G441KBT6 है और round off करने पर 4 डॉलर है https://www.digikey.com/en/products/detail/microchip-technol...
  जानना चाहता/चाहती हूँ कि 2 डॉलर से कम में यह कहाँ मिलता है
  Digi-Key पर Nuvoton chip 500 quantity के हिसाब से मुश्किल से 2 डॉलर से कम आता है
- दूसरे Parallax Propeller chip में silicon में implemented CORDIC engine है
  यह तेज है और 64-bit intermediate multiplication handle करता है, इसलिए division और trigonometric function precision अधिकांश उपयोगों के लिए पर्याप्त है
  जरूरत हो तो software से precision और बढ़ाई जा सकती है
  मुझे CORDIC के बारे में देर से पता चला; उससे पहले performance और determinism के लिए 8-bit·16-bit assembly की दुनिया में fixed-point का काफी उपयोग करता/करती था/थी
  जानने के बाद मैं हैरान रह गया/गई
  यह तेज था, और इसे उपयोगी ढंग से इस्तेमाल करने के लिए जरूरी math ability भी बस basic ही थी
मुझे पहले जिस काफी cute code snippet में शामिल था/थी, वह याद आता है
unit circle के arc से बनने वाले angle के angle bisector coordinates खोजने थे, और दोनों arms के (x,y) coordinates पहले से मौजूद थे
मौजूदा implementation trigonometric functions का ढेर था: (x,y) coordinates को polar coordinates (r,θ) में बदलता, calculated θ सही quadrant में है या नहीं जांचता, फिर θ को आधा करता और वापस (x,y) में convert करता
नतीजतन trigonometric और inverse functions बहुत बार call होते थे
Python में complex numbers को first-class की तरह इस्तेमाल किया जा सकता था, इसलिए (x1,y1) से z1, (x2,y2) से z2 नाम के दो complex numbers define किए और product का geometric mean √(z1*z2) लेना ही काफी था
नए code में न explicit trigonometric function था, न explicit conversion और inverse conversion
- यह लेख याद आता है जिसे मैं अक्सर फिर से देखता/देखती हूँ
  https://fgiesen.wordpress.com/2010/10/21/finish-your-derivat...
इसमें लिखा है, “22.75˚ rotate करना 45˚ rotate करने के बाद -22.5˚ rotate करने के बराबर है—यह काफी obvious है,” लेकिन तब क्या यह 22.5° rotation नहीं होना चाहिए?
जानना चाहता/चाहती हूँ कि यह लेख की गलती है या मैंने गलत समझा है
- लेख की गलती है
Meagher का octree system इस बात के लिए प्रसिद्ध है कि इसमें integer multiplication/division के बिना केवल integer arithmetic का इस्तेमाल किया गया था
“Boolean operations (union, intersection, difference), geometric operations (translation, scaling, rotation), N-dimensional interference detection, और space के किसी भी arbitrary point पर hidden-surface removal सहित display के लिए efficient linear-time algorithms विकसित किए गए। इन algorithms को floating-point operations, integer multiplication, या integer division की जरूरत नहीं होती”
https://doi.org/10.1016/0146-664X(82)90104-6
इसी वजह से octree representations के लिए तेज़ custom VLSI graphics acceleration hardware बनाना आसान था
उत्सुकता है कि CORDIC, छोटे table का इस्तेमाल करने वाली cubic interpolation या दूसरे polynomial interpolation की तुलना में कैसा performance देता है
मैंने सीखा था कि resource-constrained synthesizer कभी-कभी cubic interpolation का इस्तेमाल करते थे, शायद वह समय था जब CORDIC अपेक्षाकृत नया था
मोटे तौर पर देखें तो CORDIC हर iteration में 1 bit precision हासिल करता है, इसलिए computation ज़्यादा महंगी होगी, लेकिन space polynomial की तुलना में कम लगेगा
हालांकि space के लिहाज़ से यह ज़ोर देना चाहिए कि लेख में sin(x) के लिए दिए गए 4096-entry lookup table से भी यह सस्ता हो सकता है
symmetry की वजह से पूरे circle का सिर्फ 1/4 हिस्सा चाहिए
- पुराने game developers और demoscene developers sin और cos के लिए मुश्किल से 256-entry lookup table इस्तेमाल करते थे
  byte-sized angles इस्तेमाल करने पर वे अपने-आप wrap around हो जाते थे, इसलिए सुविधाजनक था, और 2D games में rotation के लिए 2^8 काफ़ी पर्याप्त था
  हालांकि अगर smooth movement चाहिए, तो 3D में यह बहुत दूर तक काम नहीं आता

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

CORDIC के लिए उपयुक्त computation environment

floating-point से बचने वाला fixed-point representation

fixed-point conversion और basic operations

vector rotation से trigonometric functions approximate करना

rotation matrix में महंगे operations घटाना

सिर्फ shift और addition छोड़ने वाला angle selection

एल्गोरिद्म की प्रक्रिया

example convergence result और बाकी topics

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

1 टिप्पणियां

Hacker News टिप्पणियां