Algoritmo alfa max mas beta min

El lugar geométrico de los puntos que dan el mismo valor en el algoritmo, para diferentes valores de alfa y beta

El algoritmo Alfa max más Beta min es una aproximación lineal de alta velocidad de la raíz cuadrada de la suma de dos cuadrados. La raíz cuadrada de la suma de dos cuadrados, también conocida como suma pitagórica, es una función útil porque encuentra la hipotenusa de un triángulo rectángulo dadas las longitudes de los dos lados, la norma de un vector 2-D o la magnitud $|z|={\sqrt {a^{2}+b^{2}}}$ de un número complejo z = a + bi dadas las partes real e imaginaria .

El algoritmo evita realizar las operaciones de raíz cuadrada y cúbica, y en su lugar utiliza operaciones simples como comparación, multiplicación y suma. Algunas elecciones de los parámetros α y β del algoritmo permiten que la operación de multiplicación se reduzca a un simple cambio de dígitos binarios que es particularmente adecuado para la implementación en circuitos digitales de alta velocidad.

La aproximación se expresa como

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

dónde $\mathbf {Max}$ es el valor absoluto máximo de a y b, y $\mathbf {Min}$ es el valor absoluto mínimo de a y b.

Para la aproximación más cercana, los valores óptimos para $\alpha$ y $\beta$ son $\alpha _{0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.960433870103...$ y $\beta _{0}={\frac {2\sin {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.397824734759...$, dando un error máximo de 3,96%.

$\alpha \,\!$	$\beta \,\!$	Error máximo(%)	Error medio (%)
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

Mejoras

Cuando $\alpha <1$, $|z|$ se vuelve más pequeño que $\mathbf {Max}$ (lo cual es geométricamente imposible) cerca de los ejes donde $\mathbf {Min}$ está cerca de 0. Esto se puede remediar reemplazando el resultado con $\mathbf {Max}$ siempre que sea mayor, esencialmente dividiendo la línea en dos segmentos diferentes.

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

El uso de esta mejora cambia qué valores de parámetros son óptimos, porque ya no necesitan una coincidencia cercana para todo el intervalo. Una baja $\alpha$ y más alto $\beta$ por lo tanto, puede aumentar aún más la precisión. Al dividir la línea en dos como esta, se podría mejorar la precisión aún más reemplazando el primer segmento por una mejor estimación que $\mathbf {Max}$ y ajustar $\alpha$ y $\beta$ respectivamente.

$|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}$	Error máximo(%)
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%

Sin embargo, se debe tener en cuenta que un valor distinto de cero $\beta _{0}$ requeriría al menos una adición adicional y algunos cambios de bits (o una multiplicación), probablemente casi duplicando el costo y, dependiendo del hardware, frustrando el propósito de usar una aproximación en primer lugar.

Referencias

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

Enlaces externos

• «Extension to three dimensions». Stack Exchange. 14 de mayo de 2015.