Algoritmos de Aproximación de Raíz Cuadrada y Raíz Cuadrada Inversa Rápida Modificados: el Método de Cambio de Constantes Mágicas
Autores: Moroz, Leonid V.; Samotyy, Volodymyr V.; Horyachyy, Oleh Y.
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Algoritmos de Aproximación de Raíz Cuadrada y Raíz Cuadrada Inversa Rápida Modificados: el Método de Cambio de Constantes Mágicas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Sistemas
Palabras clave
Plataformas de bajo costo
Aritmética de punto flotante
Raíz cuadrada
Raíz cuadrada recíproca
Método de Newton-Raphson
Formato IEEE 754
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 18
Citaciones: Sin citaciones
Muchas plataformas de bajo costo que admiten aritmética de punto flotante, como microcontroladores y matrices de compuertas programables en campo, no incluyen métodos rápidos de hardware o software para calcular la raíz cuadrada y/o la raíz cuadrada recíproca. Normalmente, estas funciones se implementan utilizando tablas de búsqueda directa o aproximaciones polinómicas, con una posterior aplicación del método de Newton-Raphson. Otras soluciones más complejas incluyen la recurrencia de dígitos de alta base y métodos basados en tablas bipartitas o multipartitas. En contraste, este artículo propone una modificación simple del método rápido de raíz cuadrada inversa que tiene una alta precisión y una latencia relativamente baja. Los algoritmos se proporcionan en C/C++ para números de precisión simple y doble en el formato IEEE 754 tanto para la raíz cuadrada como para las funciones de raíz cuadrada recíproca. Estos se basan en el cambio de constantes mágicas en la aproximación inicial, dependiendo del intervalo de entrada de los números de punto flotante normalizados, para minimizar el error relativo máximo en cada subintervalo después de la primera iteración, dando 13 bits correctos del resultado. Nuestros resultados experimentales muestran que los algoritmos propuestos proporcionan un buen equilibrio entre precisión y latencia después de dos iteraciones para números de tipo float, y después de tres iteraciones para números de tipo double cuando se utilizan instrucciones de multiplicación y adición fusionadas, dando casi completa precisión.
Descripción
Muchas plataformas de bajo costo que admiten aritmética de punto flotante, como microcontroladores y matrices de compuertas programables en campo, no incluyen métodos rápidos de hardware o software para calcular la raíz cuadrada y/o la raíz cuadrada recíproca. Normalmente, estas funciones se implementan utilizando tablas de búsqueda directa o aproximaciones polinómicas, con una posterior aplicación del método de Newton-Raphson. Otras soluciones más complejas incluyen la recurrencia de dígitos de alta base y métodos basados en tablas bipartitas o multipartitas. En contraste, este artículo propone una modificación simple del método rápido de raíz cuadrada inversa que tiene una alta precisión y una latencia relativamente baja. Los algoritmos se proporcionan en C/C++ para números de precisión simple y doble en el formato IEEE 754 tanto para la raíz cuadrada como para las funciones de raíz cuadrada recíproca. Estos se basan en el cambio de constantes mágicas en la aproximación inicial, dependiendo del intervalo de entrada de los números de punto flotante normalizados, para minimizar el error relativo máximo en cada subintervalo después de la primera iteración, dando 13 bits correctos del resultado. Nuestros resultados experimentales muestran que los algoritmos propuestos proporcionan un buen equilibrio entre precisión y latencia después de dos iteraciones para números de tipo float, y después de tres iteraciones para números de tipo double cuando se utilizan instrucciones de multiplicación y adición fusionadas, dando casi completa precisión.