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

Resumo Técnico: Calculando o Piso de $y^{1/m}$

Enunciado do Problema
O artigo aborda o problema computacional de determinar o piso inteiro da raiz enésima de um número natural $y$, denotado como $\lfloor y^{1/m} \rfloor$, onde $y > 2$ e $m > 1$. Este cálculo é um passo fundamental na teoria dos números, especificamente para identificar se um número natural $y$ é uma potência perfeita (ou seja, se existem números naturais $x$ e $m > 1$ tais que $y = x^m$). Embora as abordagens tradicionais utilizem busca binária para encontrar $x$ dentro do intervalo $[2, \lg y]$, o autor observa que tais métodos não são computacionalmente eficientes no modelo de bits de aritmética, apesar de serem práticos.

Metodologia
O artigo propõe dois algoritmos distintos baseados no método de Newton-Raphson, adaptados do cálculo de raízes em números reais para a aritmética inteira. Ambos os algoritmos visam calcular $x = \lfloor y^{1/m} \rfloor$ através do refinamento iterativo de um palpite inicial $x_0$ até a convergência.

• Algoritmo 1 (Adaptação Direta):
  Esta abordagem modifica a iteração padrão de Newton-Raphson para $f(x) = y - x^m = 0$. A etapa de atualização de valores reais $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ é convertida para a aritmética inteira aplicando a função piso à fração:
  $$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$$
  O valor inicial $x_0$ é derivado do logaritmo de $y$ para garantir que $x_0 \ge y^{1/m}$. A análise de convergência é complexa, distinguindo entre três casos:

  1. Uma sequência decrescente que estabiliza ($x_{n+1} = x_n$).
  2. Uma sequência decrescente que "inverte" e aumenta ($x_{n+1} > x_n$).
  3. Decréscimo contínuo.
     O algoritmo termina quando ocorre uma inversão ou uma repetição, ponto no qual a solução é determinada como sendo $x_n$ ou $x_n + 1$, verificada pela checagem se $x_n^m \le y < (x_n+1)^m$.

• Algoritmo 2 (Recorrência Inteira Refinada):
  Esta abordagem utiliza um rearranjo algébrico diferente da 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 formulação aproveita a propriedade $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ para manter a integridade inteira. O valor inicial $x_0$ é escolhido como $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$, garantindo que $x_0 \ge y^{1/m}$. A prova de convergência para o Algoritmo 2 é mais simplificada. Ela estabelece que a sequência é não-crescente enquanto $x_i > y^{1/m}$. O algoritmo para quando $x_{i+1} \ge x_i$, momento no qual a prova demonstra que $x_i$ deve ser igual a $\lfloor y^{1/m} \rfloor$.

Principais Contribuições

1. Formulações de Newton-Raphson para Inteiros: O artigo apresenta duas formulações específicas baseadas em inteiros do método de Newton-Raphson para calcular $\lfloor y^{1/m} \rfloor$.
2. Provas de Convergência: Provas matemáticas rigorosas são fornecidas para ambos os algoritmos, estabelecendo que eles convergem para o valor correto do piso inteiro. As provas analisam o comportamento da sequência em relação à raiz verdadeira $Y = y^{1/m}$, tratando casos em que a sequência ultrapassa o valor (overshoot) ou estabiliza.
3. Seleção de Valor Inicial: Ambos os algoritmos incluem métodos específicos e computacionalmente eficientes (usando deslocamentos de bits e logaritmos) para selecionar um palpite inicial $x_0$ que garanta que a sequência comece acima ou no valor da raiz real.

Resultos
O artigo fornece exemplos ilustrativos para ambos os algoritmos usando vários valores de $y$ e $m$ (por exemplo, $y=108, m=8$; $y=96889010407, m=13$).

• Ambos os algoritmos convergem com sucesso para a raiz inteira correta.
• Nos exemplos fornecidos, o Algoritmo 1 geralmente requer menos iterações do que o Algoritmo 2. Por exemplo, no caso de $y=52523350144$ e $m=7$, o Algoritmo 1 converge em 4 etapas (32, 34, 34), enquanto o Algoritmo 2 leva 7 etapas (64, 54, 46, 40, 36, 34, 34).
• O autor atribui a diferença de desempenho nos exemplos posteriores à escolha mais direcionada do valor inicial $x_0$ no Algoritmo 1.

Significância e Alegações
O artigo afirma explicitamente que as técnicas para usar Newton-Raphson para problemas inteiros não são inéditas, citando literatura existente (especificamente a referência [2]). Consequentemente, os autores não reivindicam novidade para o conceito matemático subjacente. Em vez disso, a intenção declarada deste artigo é fornecer uma "referência arquivística" para esses métodos específicos e suas provas detalhadas. O trabalho serve para formalizar a adaptação de Newton-Raphson para a identificação de potências perfeitas inteiras, oferecendo uma alternativa potencialmente mais eficiente à busca binária em modelos de complexidade de bits, embora o artigo permaneça modesto quanto a alegações de superioridade sobre métodos estabelecidos.