c++ - raíz - ¿Cómo calcula la computadora las raíces cuadradas?
raíz cuadrada (5)
¿Cómo calcula la computadora las raíces cuadradas? Me refiero a lo que está pasando allí! ¿Cómo lo procesa? ¿Utiliza algunas formas matemáticas como el método de Newton? ¿Qué pasa con las funciones trigonométricas? Y casi todas esas funciones matemáticas. En el caso de que cada idioma tenga su propio camino, entonces hablemos de c ++.
Buen artículo sobre este http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi muestra una comparación de los diversos métodos que se utilizan.
Creo que el método de convergencia iterativa de Newton se usa para calcular la raíz cuadrada
La mayoría de las CPU no incorporadas modernas (x86 y los núcleos ARM más grandes, por ejemplo) tienen instrucciones de hardware para calcular las raíces cuadradas directamente. La implementación del hardware que respalda estas instrucciones varía, pero generalmente es una variante del algoritmo dígito a dígito del libro de la escuela (aunque no siempre en la base dos; también se pueden usar la base cuatro o dieciséis). Estos están típicamente entre las operaciones aritméticas básicas más lentas en una CPU; tiempos como 16-64 ciclos no son infrecuentes, y estas instrucciones a menudo no se canalizan.
En las CPU que carecen de instrucciones directas de raíz cuadrada de hardware (Itanium, PPC, otros), el enfoque típico es generar una estimación inicial (ya sea con una instrucción que produce la estimación o con una tabla de búsqueda) y luego refinar esa estimación utilizando un iterativo Método (Newton o Goldschmidt por lo general). Si está interesado, puede rastrear algunos de los escritos de Peter Markstein o Roger Golliver sobre el tema.
Las funciones matemáticas más complejas (como las operaciones trigonométricas) se calculan normalmente reduciendo el argumento a algún dominio fundamental y luego aproximándolo con una función polinomial o racional. Puede ver las fuentes de cualquiera de las varias bibliotecas de matemáticas que están disponibles en línea para obtener más detalles (fdlibm es un buen punto de partida).
El conjunto de instrucciones x86 proporciona una serie de instrucciones que admiten funciones matemáticas como exp, log y sin, pero estas ya no se usan comúnmente porque las buenas implementaciones de la biblioteca de software proporcionan un mejor rendimiento.
Como han señalado otros, esta es una pregunta muy amplia: lo que funciona bien para el software podría ser una mala elección para una implementación de hardware; y luego hay problemas de redondeo correcto para IEEE-754, tablas de búsqueda de hardware, etc. Hay muchas libm C de código abierto, con implementaciones de libm también. Una buena visión general de los métodos clásicos y modernos se puede encontrar en.wikipedia.org/wiki/Methods_of_computing_square_roots .
Otra posibilidad que no se ha mencionado, es el método CORDIC . CORDIC no es ampliamente utilizado / conocido en software, pero es bastante común en hardware, y le va bastante bien en obtener un rendimiento decente sin usar muchas puertas.