🔢 mathematics

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

Cet article présente deux algorithmes basés sur la méthode de Newton-Raphson pour calculer la partie entière de $y^{1/m}$ pour des entiers naturels $y > 2$ et $m > 1$ , offrant une méthode pour déterminer si $y$ est une puissance entière d'un autre entier comme alternative aux approches traditionnelles par recherche binaire.

Auteurs originaux : Alexandros V. Gerbessiotis

Publié 2026-07-07

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Alexandros V. Gerbessiotis

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez un nombre géant et mystérieux, appelons-le $y$ . Vous avez aussi un nombre $m$ . Votre objectif est de trouver un nombre secret $x$ tel que si vous multipliez $x$ par lui-même $m$ fois (comme $x \times x \times x \dots$ ), vous obtenez exactement $y$ .

En termes mathématiques, vous essayez de trouver la racine $m$ -ième de $y$ . Mais il y a un piège : vous ne vous intéressez qu'aux nombres entiers. Si la réponse est 3,9, vous voulez savoir que c'est 3. Si c'est 4,1, vous voulez savoir que c'est 4. Vous cherchez la "partie entière" de la réponse — le plus grand nombre entier qui ne dépasse pas la cible.

Ce document est comme un guide pour deux différents jeux de devinettes intelligents conçus pour trouver ce nombre entier secret rapidement.

L'ancienne méthode : La randonnée de la "Recherche Binaire"

Traditionnellement, pour trouver ce nombre, les gens utilisaient une méthode appelée Recherche Binaire. Imaginez que vous faites une randonnée pour monter une montagne (la droite numérique) afin de trouver un campement spécifique. Vous partez du bas, vous devinez le milieu, et vous demandez : « Suis-je trop haut ou trop bas ? ». Ensuite, vous coupez le chemin restant en deux et vous devinez à nouveau. Vous continuez à diviser le chemin en deux jusqu'à ce que vous trouviez l'endroit.

L'auteur dit que cela fonctionne, mais c'est un peu comme parcourir un long chemin sinueux alors que vous pourriez prendre un hélicoptère. C'est fiable, mais cela demande beaucoup d'étapes (de calculs) pour y arriver, surtout avec de très grands nombres.

La nouvelle méthode : Le toboggan de "Newton-Raphson"

L'auteur propose deux nouvelles méthodes basées sur une vieille astuce mathématique appelée Newton-Raphson. Pensez à cela non pas comme une randonnée, mais comme un toboggan.

Imaginez que vous êtes debout sur une colline. Vous voulez glisser vers le bas d'une vallée (la réponse parfaite). La méthode Newton-Raphson vous donne une paire de skis spéciale qui calcule la pente de la colline là où vous vous trouvez et vous propulse plus près du fond en un seul bond géant.

Le document présente deux variantes de ce "saut de ski" :

Algorithme 1 : Le toboggan "Agressif"

C'est la première méthode. Elle commence avec une supposition qui est certainement trop haute (comme se tenir au sommet d'une montagne).

Comment ça marche : Il utilise une formule pour calculer la distance de la descente que vous devez effectuer. Vous continuez à sauter vers le bas, vous rapprochant de plus en plus du fond.
La particularité : Parfois, parce que nous traitons avec des nombres entiers (pas de fractions autorisées), le toboggan peut légèrement dépasser le fond de la vallée, vous faisant atterrir de l'autre côté, ou il peut vous faire atterrir pile sur le bord.
La fin : L'algorithme surveille votre trajectoire. Si vous commencez à glisser vers le haut de la colline (ce qui signifie que vous avez sauté trop loin), ou si vous atterrissez exactement au même endroit deux fois de suite, vous vous arrêtez. Vous vérifiez ensuite les deux nombres sur lesquels vous avez atterri pour voir lequel est la bonne réponse.

Algorithme 2 : Le toboggan "Prudent"

La deuxième méthode est également basée sur une descente, mais elle utilise une formule de saut légèrement différente.

Comment ça marche : Cette version est conçue pour que vous ne glissiez jamais en dessous du fond de la vallée. Vous êtes garanti de rester du "bon côté" de la réponse.
La fin : Vous continuez à glisser vers le bas jusqu'à ce que vous ne puissiez plus descendre sans remonter. Au moment où vous arrêtez de descendre (ou commencez à remonter), vous savez que vous êtes au fond.

L'étape "Vérifier son travail"

Les deux algorithmes sont comme un chef qui goûte une soupe. Ils continuent d'ajuster l'assaisonnement (la supposition) jusqu'à ce que le goût soit parfait. Mais comme ils utilisent une cuillère spéciale "uniquement pour les entiers" (pas de demi-cuillères), le goût final peut être légèrement décalé.

Ainsi, une fois que la glisse s'arrête, l'algorithme effectue une vérification finale :

Prenez votre supposition finale ( $x$ ).
Multipliez-la par elle-même $m$ fois.
Est-ce que cela est égal à $y$ ? Ou est-ce juste un peu moins que $y$ ?
Si cela correspond, vous avez trouvé votre nombre !

Le Verdict

L'auteur a testé ces deux "toboggans" avec des nombres très grands.

L'Algorithme 1 s'est avéré être légèrement plus rapide dans certains cas car sa supposition initiale était un peu plus "ciblée" (il partait de plus près de la réponse).
L'Algorithme 2 était un peu plus prévisible dans son parcours mais prenait parfois quelques étapes de plus pour se terminer.

En résumé : Le document propose deux nouvelles façons plus rapides de trouver la "racine entière" d'un nombre géant en utilisant un toboggan mathématique plutôt qu'une lente randonnée par découpage. C'est un outil pour les mathématiciens et les informaticiens qui ont besoin de résoudre ces énigmes efficacement.

Résumé technique : Calcul de la partie entière de $y^{1/m}$

Énoncé du problème
L'article traite du problème de calcul de la partie entière de la racine $m$ -ième d'un entier naturel $y$ , notée $\lfloor y^{1/m} \rfloor$ , où $y > 2$ et $m > 1$ . Ce calcul est une étape fondamentale en théorie des nombres, plus précisément pour identifier si un entier naturel $y$ est une puissance parfaite (c'est-à-dire s'il existe des entiers naturels $x$ et $m > 1$ tels que $y = x^m$ ). Alors que les approches traditionnelles utilisent la recherche dichotomique pour trouver $x$ dans l'intervalle $[2, \lg y]$ , l'auteur note que de telles méthodes ne sont pas informatiquement efficaces dans le modèle arithmétique des bits, bien qu'elles soient pratiques.

Méthodologie
L'article propose deux algorithmes distincts basés sur la méthode de Newton-Raphson, adaptés de la recherche de racines sur les nombres réels à l'arithmétique entière. Les deux algorithmes visent à calculer $x = \lfloor y^{1/m} \rfloor$ en affinant de manière itérative une estimation initiale $x_0$ jusqu'à la convergence.

Algorithme 1 (Adaptation directe) :
Cette approche modifie l'itération standard de Newton-Raphson pour $f(x) = y - x^m = 0$ . L'étape de mise à jour pour les réels $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ est convertie en arithmétique entière en appliquant la fonction partie entière à la fraction :
$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$
La valeur initiale $x_0$ est dérivée du logarithme de $y$ pour garantir que $x_0 \ge y^{1/m}$ . L'analyse de la convergence est complexe, distinguant trois cas :

Une séquence décroissante qui se stabilise ( $x_{n+1} = x_n$ ).
Une séquence décroissante qui « bascule » et augmente ( $x_{n+1} > x_n$ ).
Une décroissance continue.
L'algorithme s'arrête lorsqu'une bascule ou une répétition se produit, moment où la solution est déterminée comme étant soit $x_n$ , soit $x_n + 1$ , vérifiée par le contrôle si $x_n^m \le y < (x_n+1)^m$ .

Algorithme 2 (Récurrence entière raffinée) :
Cette approche utilise un réarrangement algébrique différent de la formule de Newton-Raphson :
$x_{i+1} = \left\lfloor \frac{(m-1)x_i + \lfloor y/x_i^{m-1} \rfloor}{m} \right\rfloor$
Cette formulation exploite la propriété $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ pour maintenir l'intégrité entière. La valeur initiale $x_0$ est choisie comme $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$ , garantissant que $x_0 \ge y^{1/m}$ .
La preuve de convergence pour l'Algorithme 2 est plus simplifiée. Elle établit que la séquence est non croissante tant que $x_i > y^{1/m}$ . L'algorithme s'arrête lorsque $x_{i+1} \ge x_i$ , moment où la preuve démontre que $x_i$ doit être égal à $\lfloor y^{1/m} \rfloor$ .

Contributions clés

Formulations de Newton-Raphson pour les entiers : L'article présente deux adaptations spécifiques basées sur les entiers de la méthode de Newton-Raphson pour calculer $\lfloor y^{1/m} \rfloor$ .
Preuves de convergence : Des preuves mathématiques rigoureuses sont fournies pour les deux algorithmes, établissant qu'ils convergent vers la bonne valeur de la partie entière. Les preuves analysent le comportement de la séquence par rapport à la racine réelle $Y = y^{1/m}$ , en gérant les cas où la séquence dépasse la cible ou se stabilise.
Sélection de la valeur initiale : Les deux algorithmes incluent des méthodes spécifiques et efficaces sur le plan computationnel (utilisant des décalages de bits et des logarithmes) pour sélectionner une estimation initiale $x_0$ qui garantit que la séquence commence au-dessus ou au niveau de la racine réelle.

Résultats
L'article fournit des exemples illustratifs pour les deux algorithmes utilisant diverses valeurs de $y$ et $m$ (par exemple, $y=108, m=8$ ; $y=96889010407, m=13$ ).

Les deux algorithmes convergent avec succès vers la racine entière correcte.
Dans les exemples fournis, l'Algorithme 1 nécessite généralement moins d'itérations que l'Algorithme 2. Par exemple, dans le cas de $y=52523350144$ et $m=7$ , l'Algorithme 1 converge en 4 étapes (32, 34, 34), tandis que l'Algorithme 2 en prend 7 (64, 54, 46, 40, 36, 34, 34).
L'auteur attribue la différence de performance dans les exemples ultérieurs au choix plus ciblé de la valeur initiale $x_0$ dans l'Algorithme 1.

Signification et affirmations
L'article stipule explicitement que les techniques d'utilisation de Newton-Raphson pour les problèmes entiers ne sont pas nouvelles, citant la littérature existante (spécifiquement la référence [2]). Par conséquent, les auteurs ne revendiquent pas de nouveauté pour le concept mathématique sous-jacent. Au lieu de cela, l'intention déclarée de l'article est de fournir une « référence archivistique » pour ces méthodes spécifiques et leurs preuves détaillées. Le travail sert à formaliser l'adaptation de Newton-Raphson pour l'identification des puissances parfaites entières, offrant une alternative potentiellement plus efficace à la recherche dichotomique dans les modèles de complexité de bits, bien que l'article reste modeste quant aux affirmations de supériorité sur les méthodes établies.