Hay varias formas de encontrar raíces cuadradas enteras utilizando solo aritmética de enteros. Por ejemplo, this one. Es una lectura interesante y también una teoría muy interesante, especialmente para mi generación, donde esas técnicas ya no son tan útiles.Calcular enésima raíz con la aritmética de enteros
Lo principal es que no puede usar la aritmética de coma flotante, por lo que descarta el método de Newton y sus derivaciones. La única otra manera que conozco de encontrar raíces es la expansión binomial, pero eso también requiere una aritmética de coma flotante.
¿Qué técnicas/algoritmos existen para calcular raíces enésimas integradas usando solo aritmética de enteros?
Edit: Gracias por todas las respuestas hasta el momento. Todos parecen ser un poco más inteligentes de prueba y mejora. ¿No hay mejor manera?
Edit2: Ok, parece que no hay una forma inteligente de hacerlo sin prueba/mejora y tampoco el método newtons o una búsqueda binaria. ¿Alguien puede proporcionar una comparación de los dos en teoría? He corrido varios puntos de referencia entre los dos y los encontré bastante similares.
¿Cuál es su rango requerido de valores de entrada? –
@PaulR, idealmente podría ser extensible, pero creo que se puede suponer que tanto la base como el número serán enteros de 32 bits (sin signo) por ahora. – Matt
¿Qué operaciones enteras está permitiendo? Las raíces cuadradas son un caso especial porque es posible extraerlas usando solo sumas, restas y cambios. – Neil