¿Cuál es el algoritmo más rápido para calcular la raíz cuadrada entera de un número?

Answer 1

La forma “teórica” ​​más rápida que conozco es el método de Newton, que tiene convergencia cuadrática. Aquí está disponible una descripción de cómo hacer que el método de Newton funcione para raíces cuadradas enteras: raíz cuadrada entera.

Si está trabajando con enteros acotados, probablemente pueda encontrar algo más rápido que use tablas de búsqueda y / o manipulación de bits … tal vez algo como:

typedef unsigned char uint8; typedef unsigned short int uint16; typedef unsigned long int uint32; uint32 isqrt32 (uint32 n) { register uint32 root, remainder, place; root = 0; remainder = n; place = 0x40000000; while (place > remainder) { place = place >> 2; } while (place) { if (remainder >= root + place) { remainder = remainder - root - place; root = root + (place <> 1; place = place >> 2; } return root; } 

o:

 unsigned int sqrt32(unsigned long n) { unsigned int c = 0x8000; unsigned int g = 0x8000; for (;;) { if (g*g > n) { g ^= c; } c >>= 1; if (c == 0) { return g; } g |= c; } } 

(desde Calcular una raíz cuadrada entera)