Algoritm för alfa max plus beta min

Platsen för punkter som ger samma värde i algoritmen, för olika värden på alfa och beta

Algoritmen alfamax plus beta min är en höghastighetsapproximation av kvadratroten ur summan av två kvadrater. Kvadratroten ur summan av två kvadrater, även känd som Pythagoras addition , är en användbar funktion, eftersom den hittar hypotenusan av en rätvinklig triangel givet de två sidlängderna, normen för en 2D- vektor , eller magnituden $|z|={\sqrt {a^{2}+b^{2}}}$ av ett komplext tal $z = a + bi$ givet de reella och imaginära delarna.

Algoritmen undviker att utföra kvadrat- och kvadratrotsoperationerna, utan använder istället enkla operationer som jämförelse, multiplikation och addition. Vissa val av a- och p-parametrarna för algoritmen tillåter att multiplikationsoperationen reduceras till en enkel förskjutning av binära siffror som är särskilt väl lämpad för implementering i digitala höghastighetskretsar.

Uppskattningen uttrycks som

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

där

\mathbf {Max}

är det maximala absoluta värdet av a och b , och

\mathbf {Min}

är det minsta absoluta värdet av a och b .

är de optimala värdena för $\alpha$ och $\beta$ $\alpha _{ 0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0,960433870103...$ och ${\displaystyle \beta _{0}={\frac {2\sin {\frac {\pi }{8}}}{1+\cos { \frac {\pi }{8}}}}=0,397824734759...} ,$ vilket ger ett maximalt fel på 3,96 %.

$\alpha \,\!$	$\beta \,\!$	Största felet (%)	Medelfel (%)
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	16/7	12.50	4,91
15/16	15/32	6,25	3.08
$\alpha _{0}$	$\beta _{0}$	3,96	2,41

Förbättringar

När $\alpha <1$ , $|z|$ blir mindre än $\mathbf {Max}$ (vilket är geometriskt omöjligt) nära axlarna där $\mathbf {Min}$ är nära 0. Detta kan åtgärdas genom att ersätta resultatet med $\mathbf {Max}$ när det är större, i huvudsak dela upp linjen i två olika segment.

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

Beroende på hårdvaran kan denna förbättring vara nästan gratis.

Genom att använda denna förbättring ändras vilka parametervärden som är optimala, eftersom de inte längre behöver en nära matchning för hela intervallet. En lägre $\alpha$ och högre $\beta$ kan därför öka precisionen ytterligare.

Ökad precision: När man delar linjen i två som denna kan man förbättra precisionen ännu mer genom att ersätta det första segmentet med en bättre uppskattning än ${\displaystyle \mathbf {Max} } ,$ och justera $\alpha$ och $\beta$ i enlighet därmed.

|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}$	Största felet (%)
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 %

${\displaystyle \beta _{0}} som$ inte är noll skulle kräva minst en extra addition och några bitförskjutningar (eller en multiplikation), förmodligen nästan en fördubbling av kostnaden och, beroende på hårdvaran, ev. besegra syftet med att använda en approximation i första hand.

Se även

Hypot , en exakt funktion eller algoritm som också är säker mot över- och underflöde.

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

externa länkar

"Utbyggnad till tre dimensioner" . Stack Exchange . 14 maj 2015.