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

Not to be confused with Minimax or Alpha–beta pruning.

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

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

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

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

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

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

निकटतम सन्निकटन के लिए, इष्टतम मान $\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 \,\!$	Largest error (%)	Mean error (%)
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}$	Largest error (%)
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.