Calculating the floor of y**(1/m)

Resumen Técnico: Cálculo del piso de $y^{1/m}$

Planteamiento del Problema
El artículo aborda el problema computacional de determinar el piso entero de la raíz $m$-ésima de un número natural $y$, denotado como $\lfloor y^{1/m} \rfloor$, donde $y > 2$ y $m > 1$. Este cálculo es un paso fundamental en la teoría de números, específicamente para identificar si un número natural $y$ es una potencia perfecta (es decir, si existen números naturales $x$ y $m > 1$ tales que $y = x^m$). Aunque los enfoques tradicionales utilizan la búsqueda binaria para encontrar $x$ dentro del rango $[2, \lg y]$, el autor señala que tales métodos no son computacionalmente eficientes en el modelo de bits de la aritmética, a pesar de ser prácticos.

Metodología
El artículo propone dos algoritmos distintos basados en el método de Newton-Raphson, adaptados del cálculo de raíces en números reales al cálculo aritmético entero. Ambos algoritmos tienen como objetivo calcular $x = \lfloor y^{1/m} \rfloor$ mediante el refinamiento iterativo de una estimación inicial $x_0$ hasta la convergencia.

• Algoritmo 1 (Adaptación Directa):
  Este enfoque modifica la iteración estándar de Newton-Raphson para $f(x) = y - x^m = 0$. El paso de actualización de valores reales $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ se convierte a aritmética entera aplicando la función piso a la fracción:
  $$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$$
  El valor inicial $x_0$ se deriva del logaritmo de $y$ para asegurar que $x_0 \ge y^{1/m}$. El análisis de convergencia es complejo, distinguiendo entre tres casos:

1. Una secuencia decreciente que se estabiliza ($x_{n+1} = x_n$).
2. Una secuencia decreciente que "salta" y aumenta ($x_{n+1} > x_n$).
3. Decrecimiento continuo.
   El algoritmo termina cuando ocurre un salto o una repetición, momento en el cual se determina que la solución es $x_n$ o $x_n + 1$, verificando si $x_n^m \le y < (x_n+1)^m$.

• Algoritmo 2 (Recurrencia Entera Refinada):
  Este enfoque utiliza un reordenamiento algebraico diferente de la fórmula de Newton-Raphson:
  $$x_{i+1} = \left\lfloor \frac{(m-1)x_i + \lfloor y/x_i^{m-1} \rfloor}{m} \right\rfloor$$
  Esta formulación aprovecha la propiedad $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ para mantener la integridad entera. El valor inicial $x_0$ se elige como $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$, asegurando que $x_0 \ge y^{1/m}$.
  La prueba de convergencia para el Algoritmo 2 es más simplificada. Establece que la secuencia es no creciente mientras $x_i > y^{1/m}$. El algoritmo se detiene cuando $x_{i+1} \ge x_i$, momento en el cual la prueba demuestra que $x_i$ debe ser igual a $\lfloor y^{1/m} \rfloor$.

Contribuciones Clave

1. Formulaciones de Newton-Raphson para Enteros: El artículo presenta dos adaptaciones específicas basadas en enteros del método de Newton-Raphson para calcular $\lfloor y^{1/m} \rfloor$.
2. Pruebas de Convergencia: Se proporcionan pruebas matemáticas rigurosas para ambos algoritmos, estableciendo que convergen al valor entero del piso correcto. Las pruebas analizan el comportamiento de la secuencia con respecto a la raíz real $Y = y^{1/m}$, manejando casos donde la secuencia sobrepasa el valor o se estabiliza.
3. Selección del Valor Inicial: Ambos algoritmos incluyen métodos computacionalmente eficientes (usando desplazamientos de bits y logaritmos) para seleccionar una estimación inicial $x_0$ que garantice que la secuencia comience por encima o en la raíz real.

Resultados
El artículo proporciona ejemplos ilustrativos para ambos algoritmos utilizando diversos valores de $y$ y $m$ (por ejemplo, $y=108, m=8$; $y=96889010407, m=13$).

• Ambos algoritmos convergen con éxito al raíz entera correcta.
• En los ejemplos proporcionados, el Algoritmo 1 generalmente requiere menos iteraciones que el Algoritmo 2. Por ejemplo, en el caso de $y=52523350144$ y $m=7$, el Algoritmo 1 converge en 4 pasos (32, 34, 34), mientras que el Algoritmo 2 toma 7 pasos (64, 54, 46, 40, 36, 34, 34).
• El autor atribuye la diferencia de rendimiento en los ejemplos posteriores a la elección más dirigida del valor inicial $x_0$ en el Algoritmo 1.

Significancia y Reivindicaciones
El artículo establece explícitamente que las técnicas para usar Newton-Raphson en problemas enteros no son novedosas, citando literatura existente (específicamente la referencia [2]). Por consiguiente, los autores no reclaman novedad para el concepto matemático subyacente. En su lugar, la intención declarada del artículo es proporcionar una "referencia de archivo" para estos métodos específicos y sus pruebas detalladas. El trabajo sirve para formalizar la adaptación de Newton-Raphson para la identificación de potencias perfectas enteras, ofreciendo una alternativa potencialmente más eficiente a la búsqueda binaria en modelos de complejidad de bits, aunque el artículo mantiene la modestia respecto a las afirmaciones de superioridad sobre métodos establecidos.