El algoritmo alpha max plus beta min 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 dos lados, la norma de un vector 2-D o la magnitud de un número complejo z = a + b i dadas las partes real e imaginaria .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/1/17/AlphaMaxBetaMin.png/220px-AlphaMaxBetaMin.png)
El algoritmo evita realizar las operaciones cuadradas y de raíz cuadrada, en lugar de utilizar 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 desplazamiento de dígitos binarios que se adapta particularmente bien a la implementación en circuitos digitales de alta velocidad.
La aproximación se expresa como
dónde es el valor absoluto máximo de un y b , yes el valor absoluto mínimo de una y b .
Para la aproximación más cercana, los valores óptimos para y están y , dando un error máximo del 3,96%.
Mayor error (%) | 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 | 16/7 | 12,50 | 4,91 |
15/16 | 15/32 | 6.25 | 3,08 |
3,96 | 2,41 |
![Aproximación Alpha Max Beta Min.png](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/7b/Alpha_Max_Beta_Min_approximation.png/800px-Alpha_Max_Beta_Min_approximation.png)
Mejoras
Cuándo , se vuelve más pequeño que (que es geométricamente imposible) cerca de los ejes donde está cerca de 0. Esto se puede remediar reemplazando el resultado con siempre que sea mayor, esencialmente dividiendo la línea en dos segmentos diferentes.
Dependiendo del hardware, esta mejora puede ser casi gratuita.
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 y más alto por lo tanto, puede aumentar aún más la precisión.
Mayor precisión: al dividir la línea en dos como esta, se podría mejorar la precisión aún más al reemplazar el primer segmento por una mejor estimación quey ajustar y respectivamente.
Mayor 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% |
Sin embargo, tenga en cuenta que un valor distinto de cero 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, posiblemente anulando el propósito de usar una aproximación en primer lugar.
Ver también
- Hypot , una función o algoritmo precisos que también son seguros contra desbordes y subdesbordamientos
Referencias
- Lyons, Richard G . Comprensión del procesamiento de señales digitales, sección 13.2. Prentice Hall, 2004 ISBN 0-13-108989-7 .
- Griffin, Grant. Truco DSP: Estimador de magnitud .
enlaces externos
- "Ampliación a tres dimensiones" . Stack Exchange . 14 de mayo de 2015.