¿Cómo calcula la computadora las raíces cuadradas?

¿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, hablemos de c ++.

La mayoría de las CPU modernas no integradas (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 por lo general es una variante del algoritmo dígito a dígito del libro de la escuela (aunque no siempre está 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 fonts 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 bibliotecas de software ofrecen un mejor rendimiento.

Buen artículo sobre este http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi que muestra una comparación de los diversos métodos que se utilizan.

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 funciona bastante bien para obtener un rendimiento decente sin usar muchas puertas.

Creo que el método de convergencia iterativa de Newton se usa para calcular la raíz cuadrada

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 una gran cantidad de 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 aquí .