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

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.