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

Sintesi Tecnica: Calcolo del Floor di $y^{1/m}$

Enunciato del Problema
Il documento affronta il problema computazionale di determinare il floor intero della radice $m$-esima di un numero naturale $y$, indicato come $\lfloor y^{1/m} \rfloor$, dove $y > 2$ e $m > 1$. Questo calcolo è un passaggio fondamentale nella teoria dei numeri, specificamente per identificare se un numero naturale $y$ è una potenza perfetta (ovvero, se esistono numeri naturali $x$ e $m > 1$ tali che $y = x^m$). Sebbene gli approcci tradizionali utilizzino la ricerca binaria per trovare $x$ nell'intervallo $[2, \lg y]$, l'autore osserva che tali metodi non sono computazionalmente efficienti nel modello di aritmetica a bit, nonostante siano pratici.

Metodologia
Il documento propone due distinti algoritmi basati sul metodo di Newton-Raphson, adattati dal calcolo delle radici su numeri reali all'aritmetica intera. Entrambi gli algoritmi mirano a calcolare $x = \lfloor y^{1/m} \rfloor$ raffinando iterativamente una stima iniziale $x_0$ fino alla convergenza.

• Algoritmo 1 (Adattamento Diretto):
  Questo approccio modifica lo standard dell'iterazione di Newton-Raphson per $f(x) = y - x^m = 0$. Il passo di aggiornamento nel dominio dei numeri reali $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ viene convertito in aritmetica intera applicando la funzione floor alla frazione:
  $$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$$
  Il valore iniziale $x_0$ è derivato dal logaritmo di $y$ per garantire che $x_0 \ge y^{1/m}$. L'analisi della convergenza è complessa e distingue tra tre casi:

1. Una sequenza decrescente che si stabilizza ($x_{n+1} = x_n$).
2. Una sequenza decrescente che "inverte" e aumenta ($x_{n+1} > x_n$).
3. Decrescita continua.
   L'algoritmo termina quando si verifica un'inversione o una ripetizione, punto in cui la soluzione è determinata come $x_n$ o $x_n + 1$, verificata controllando se $x_n^m \le y < (x_n+1)^m$.

• Algoritmo 2 (Ricorrenza Intera Raffinata):
  Questo approccio utilizza un diverso riarrangiamento algebrico della formula di Newton-Raphson:
  $$x_{i+1} = \left\lfloor \frac{(m-1)x_i + \lfloor y/x_i^{m-1} \rfloor}{m} \right\rfloor$$
  Questa formulazione sfrutta la proprietà $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ per mantenere l'integrità intera. Il valore iniziale $x_0$ è scelto come $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$, garantendo che $x_0 \ge y^{1/m}$. La prova di convergenza per l'Algoritmo 2 è più snella. Stabilisce che la sequenza è non crescente finché $x_i > y^{1/m}$. L'algoritmo si ferma quando $x_{i+1} \ge x_i$, punto in cui la prova dimostra che $x_i$ deve essere uguale a $\lfloor y^{1/m} \rfloor$.

Contributi Chiave

1. Formulazioni Newton-Raphson per Interi: Il documento presenta due specifiche adattazioni basate su interi del metodo di Newton-Raphson per calcolare $\lfloor y^{1/m} \rfloor$.
2. Prove di Convergenza: Vengono fornite rigorose prove matematiche per entrambi gli algoritmi, stabilendo che essi convergono al corretto valore floor intero. Le prove analizzano il comportamento della sequenza rispetto alla vera radice $Y = y^{1/m}$, gestendo i casi in cui la sequenza supera il valore (overshoot) o si stabilizza.
3. Selezione del Valore Iniziale: Entrambi gli algoritmi includono metodi specifici e computazionalmente efficienti (utilizzando shift di bit e logaritmi) per selezionare una stima iniziale $x_0$ che garantisca che la sequenza parta sopra o al livello della vera radice.

Risultati
Il documento fornisce esempi illustrativi per entrambi gli algoritmi utilizzando vari valori di $y$ e $m$ (ad esempio, $y=108, m=8$; $y=96889010407, m=13$).

• Entrambi gli algoritmi convergono con successo alla corretta radice intera.
• Negli esempi forniti, l'Algoritmo 1 richiede generalmente meno iterazioni rispetto all'Algoritmo 2. Ad esempio, nel caso di $y=52523350144$ e $m=7$, l'Algoritmo 1 converge in 4 passi (32, 34, 34), mentre l'Algoritmo 2 richiede 7 passi (64, 54, 46, 40, 36, 34, 34).
• L'autore attribuisce la differenza di prestazioni negli esempi successivi alla scelta più mirata del valore iniziale $x_0$ nell'Algoritmo 1.

Significatività e Rivendicazioni
Il documento afferma esplicitamente che le tecniche per l'uso di Newton-Raphson per problemi interi non sono nuove, citando la letteratura esistente (specificamente il riferimento [2]). Di conseguenza, gli autori non rivendicano la novità del concetto matematico sottostante. Inveve, l'intento dichiarato del documento è quello di fornire un "riferimento archivistico" per questi specifici metodi e le loro prove dettagliate. Il lavoro serve a formalizzare l'adattamento di Newton-Raphson per l'identificazione di potenze perfette intere, offrendo un'alternativa potenzialmente più efficiente alla ricerca binaria nei modelli di complessità di bit, sebbene il documento rimanga modesto riguardo alle rivendicazioni di superiorità rispetto ai metodi stabiliti.