अल्फा मैक्स प्लस बीटा मिन एल्गोरिथम

Not to be confused with मिनीमैक्स or अल्फा-बीटा प्रूनिंग.

अल्फ़ा और बीटा के विभिन्न मानों के लिए एल्गोरिदम में समान मान देने वाले बिंदुओं का स्थान

अल्फ़ा मैक्स प्लस बीटा मिन एल्गोरिथम दो वर्गों के योग के वर्गमूल का उच्च गति सन्निकटन होता है। इसको दो वर्गों के योग का वर्गमूल कहा जाता हैं, जिसे पायथागॉरियन जोड़ के रूप में भी जाना जाता है, यह उपयोगी फलन होता है, क्योंकि इसकी दो भुजाओं की लंबाई, 2-डी होती हैं | यह सदिश (ज्यामितीय) के मानदंड या परिमाण (गणित) $|z|={\sqrt {a^{2}+b^{2}}}$ को देखते हुए समकोण त्रिभुज का कर्ण पाता है। इसमें सम्मिश्र संख्या z = a + bi के वास्तविक संख्या और काल्पनिक संख्या के भाग दिए गए हैं।

एल्गोरिदम वर्ग और वर्ग-मूल संचालन करने से बच जाता है, इसके अतिरिक्त इसकी तुलना, गुणा और जोड़ जैसे सरल संचालन का उपयोग करता है। एल्गोरिथ्म के α और β मापदंडों के कुछ विकल्प गुणन ऑपरेशन को बाइनरी अंकों की सरल शिफ्ट में कम करने की अनुमति देते हैं जिन्हें विशेष रूप से उच्च गति डिजिटल सर्किटरी में कार्यान्वयन के लिए उपयुक्त किया जाता है।

इसको सन्निकटन के रूप में व्यक्त किया गया है।

$$|z|=\alpha \,\mathbf {Max} +\beta \,\mathbf {Min} ,$$

जहाँ $\mathbf {Max}$ a और b का अधिकतम निरपेक्ष मान होता है, और $\mathbf {Min}$ a और b का न्यूनतम निरपेक्ष मान होता है।

निकटतम सन्निकटन के लिए, $\alpha$ और $\beta$ के लिए इष्टतम मान $\alpha _{0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.960433870103...$ और हैं

$\beta _{0}={\frac {2\sin {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.397824734759...$, अधिकतम 3.96% त्रुटि दे रहा है।

$\alpha \,\!$	$\beta \,\!$	सबसे बड़ी त्रुटि (%)	माध्य त्रुटि (%)
1/1	1/2	11.80	8.68
1/1	1/4	11.61	3.20
1/1	3/8	6.80	4.25
7/8	7/16	12.50	4.91
15/16	15/32	6.25	3.08
$\alpha _{0}$	$\beta _{0}$	3.96	2.41

सुधार

जब $\alpha <1$, $|z|$ उन अक्षों के पास $\mathbf {Max}$ से छोटा हो जाता है (जो ज्यामितीय रूप से असंभव है) जहां $\mathbf {Min}$ 0 के करीब है। जब भी यह अधिक हो, तो परिणाम को $\mathbf {Max}$ से प्रतिस्थापित करके इसका समाधान किया जा सकता है। अनिवार्य रूप से रेखा को दो अलग-अलग खंडों में विभाजित करना।

$|z|=\max(\mathbf {Max} ,\alpha \,\mathbf {Max} +\beta \,\mathbf {Min} ).$

हार्डवेयर के आधार पर, यह सुधार लगभग निःशुल्क हो सकता है।

इस सुधार का उपयोग करने से यह बदल जाता है कि कौन से पैरामीटर मान इष्टतम हैं, क्योंकि उन्हें अब पूरे अंतराल के लिए करीबी मिलान की आवश्यकता नहीं है। इसलिए निम्न $\alpha$ और उच्चतर $\beta$ परिशुद्धता को और अधिक बढ़ा सकता है।

परिशुद्धता में वृद्धि: इस तरह से रेखा को दो भागों में विभाजित करते समय पहले खंड को $\mathbf {Max}$ से बेहतर अनुमान से प्रतिस्थापित करके और तदनुसार $\alpha$ और $\beta$ को समायोजित करके परिशुद्धता में और भी अधिक सुधार किया जा सकता है।

$|z|=\max {\big (}|z_{0}|,|z_{1}|{\big )},$

$|z_{0}|=\alpha _{0}\,\mathbf {Max} +\beta _{0}\,\mathbf {Min} ,$

$|z_{1}|=\alpha _{1}\,\mathbf {Max} +\beta _{1}\,\mathbf {Min} .$

$\alpha _{0}$	$\beta _{0}$	$\alpha _{1}$	$\beta _{1}$	सबसे बड़ी त्रुटि (%)
1	0	7/8	17/32	−2.65%
1	0	29/32	61/128	+2.4%
1	0	0.898204193266868	0.485968200201465	±2.12%
1	1/8	7/8	33/64	−1.7%
1	5/32	27/32	71/128	1.22%
127/128	3/16	27/32	71/128	−1.13%

हालाँकि, सावधान रहें, यह गैर-शून्य है $\beta _{0}$ इसके लिए कम से कम अतिरिक्त जोड़ और कुछ बिट-शिफ्ट (या गुणन) की आवश्यकता होगी, संभवतः लागत लगभग दोगुनी हो जाएगी और, हार्डवेयर के आधार पर, संभवतः प्रथम स्थान पर सन्निकटन का उपयोग करने का उद्देश्य विफल हो जाएगा।

यह भी देखें

• हाइपोट, सटीक फलन या एल्गोरिदम जो ओवरफ़्लो और अंडरफ़्लो के विरुद्ध भी सुरक्षित है।

संदर्भ

• Lyons, Richard G. Understanding Digital Signal Processing, section 13.2. Prentice Hall, 2004 ISBN 0-13-108989-7.
• Griffin, Grant. DSP Trick: Magnitude Estimator.

बाहरी संबंध

• "Extension to three dimensions". Stack Exchange. May 14, 2015.