Algoritmo alfa máximo más beta mínimo

El algoritmo alfa max más beta min ^{[ 1 ]} es una aproximación 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 2D o la magnitud.${\displaystyle |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 elevación al cuadrado y raíz cuadrada, utilizando en su lugar operaciones sencillas como la comparación, la multiplicación y la suma. Algunas elecciones de los parámetros α y β del algoritmo permiten reducir la operación de multiplicación a un simple desplazamiento de dígitos binarios, lo cual resulta especialmente adecuado para su implementación en circuitos digitales de alta velocidad.

La aproximación se expresa como $${\displaystyle |z|=\alpha \,\mathbf {Max} +\beta \,\mathbf {Min} ,}$$ dónde${\displaystyle \mathbf {Max} }$es el valor absoluto máximo de a y b , y${\displaystyle \mathbf {Min} }$es el valor absoluto mínimo de a y b .

Para la aproximación más cercana, los valores óptimos para${\displaystyle \alpha }$y${\displaystyle \beta }$son

${\displaystyle \alpha _{0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=1-\tan ^{2}{\frac {\pi }{16}}=0.960433870103...}$y

${\displaystyle \beta _{0}={\frac {2\sin {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=2\tan {\frac {\pi }{16}}=0.397824734759...}$,

arrojando un error máximo del 3,96%.

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

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

Dependiendo del hardware, esta mejora puede resultar prácticamente gratuita.

El uso de esta mejora cambia qué valores de parámetros son óptimos, porque ya no necesitan coincidir estrechamente en todo el intervalo. Un valor menor${\displaystyle \alpha }$y superior${\displaystyle \beta }$Por lo tanto, se puede aumentar aún más la precisión.

Esto se puede mejorar aún más, en lugar de usar${\displaystyle |z_{0}|=1\cdot \mathbf {Max} +0\cdot \mathbf {Min} }$Como segunda estimación, utilice un segundo par de parámetros.${\displaystyle \alpha _{0}}$y${\displaystyle \beta _{0}}$, con${\displaystyle \alpha _{1}}$y${\displaystyle \beta _{1}}$ajustado en consecuencia.

${\displaystyle |z|=\max \left(|z_{0}|,|z_{1}|\right),}$

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

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

Por supuesto, un valor distinto de cero${\displaystyle \beta _{0}}$requiere al menos una suma adicional y algunos desplazamientos de bits (o una multiplicación), lo que prácticamente duplica el costo y, dependiendo del hardware, posiblemente anula el propósito de usar una aproximación en primer lugar.

• Hipoteco , una función o algoritmo preciso que también es seguro contra desbordamiento y subdesbordamiento.

• Lyons, Richard G. Comprensión del procesamiento digital de señales, sección 13.2. Prentice Hall, 2004 ISBN 0-13-108989-7.
• Griffin, Grant. Truco de DSP: Estimador de magnitud .

• "Extensión a tres dimensiones" . Stack Exchange . 14 de mayo de 2015.