🔢 mathematics

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

This paper presents two Newton-Raphson-based algorithms for computing the floor of $y^{1/m}$ for natural numbers $y > 2$ and $m > 1$ , offering a method to determine if $y$ is an integer power of another integer as an alternative to traditional binary search approaches.

Original authors: Alexandros V. Gerbessiotis

Published 2026-07-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandros V. Gerbessiotis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, mysterious number, let's call it $y$ . You also have a number $m$ . Your goal is to find a secret number $x$ such that if you multiply $x$ by itself $m$ times (like $x \times x \times x \dots$ ), you get exactly $y$ .

In math terms, you are trying to find the $m$ -th root of $y$ . But there's a catch: you only care about whole numbers. If the answer is 3.9, you want to know it's 3. If it's 4.1, you want to know it's 4. You are looking for the "floor" of the answer—the biggest whole number that doesn't overshoot.

This paper is like a guidebook for two different smart guessing games designed to find that secret whole number quickly.

The Old Way: The "Binary Search" Hike

Traditionally, to find this number, people used a method called Binary Search. Imagine you are hiking up a mountain (the number line) to find a specific campsite. You start at the bottom, guess the middle, and ask, "Am I too high or too low?" Then you cut the remaining path in half and guess again. You keep chopping the path in half until you find the spot.

The author says this works, but it's a bit like walking a long, winding path when you could have taken a helicopter. It's reliable, but it takes a lot of steps (computations) to get there, especially with huge numbers.

The New Way: The "Newton-Raphson" Slide

The author proposes two new methods based on an old mathematical trick called Newton-Raphson. Think of this not as a hike, but as a slide.

Imagine you are standing on a hill. You want to slide down to the bottom of a valley (the perfect answer). The Newton-Raphson method gives you a special pair of skis that calculate the slope of the hill right where you are standing and shoot you closer to the bottom in one giant leap.

The paper presents two variations of this "ski jump":

Algorithm 1: The "Aggressive" Slide

This is the first method. It starts with a guess that is definitely too high (like standing on a mountain peak).

How it works: It uses a formula to calculate how far down the hill you should jump. It keeps jumping down, getting closer and closer to the bottom.
The Quirk: Sometimes, because we are dealing with whole numbers (no fractions allowed), the slide might overshoot the valley floor slightly, landing you on the other side, or it might land you right on the edge.
The Finish: The algorithm watches your path. If you start sliding up the hill again (meaning you jumped too far), or if you land on the exact same spot twice in a row, you stop. You then check the two numbers you landed on to see which one is the correct answer.

Algorithm 2: The "Careful" Slide

This is the second method. It also starts high up, but it uses a slightly different formula for the jump.

How it works: This version is designed so that you never slide below the valley floor. You are guaranteed to stay on the "safe side" of the answer.
The Finish: You keep sliding down until you can't go any lower without going up. The moment you stop sliding down (or start sliding up), you know you are at the bottom.

The "Check Your Work" Step

Both algorithms are like a chef tasting a soup. They keep adjusting the seasoning (the guess) until it tastes just right. But because they are using a special "integer-only" spoon (no half-spoons), the final taste might be slightly off.

So, once the sliding stops, the algorithm does a final check:

Take your final guess ( $x$ ).
Multiply it by itself $m$ times.
Does it equal $y$ ? Or is it just slightly less than $y$ ?
If it fits, you found your number!

The Verdict

The author tested these two "slides" with some very large numbers.

Algorithm 1 was found to be slightly faster in some cases because its initial guess was a bit more "targeted" (it started closer to the answer).
Algorithm 2 was a bit more predictable in its path but sometimes took a few more steps to finish.

In a nutshell: The paper offers two new, faster ways to find the "whole number root" of a giant number by using a mathematical slide instead of a slow, chopping hike. It's a tool for mathematicians and computer scientists who need to solve these puzzles efficiently.

Technical Summary: Calculating the Floor of $y^{1/m}$

Problem Statement
The paper addresses the computational problem of determining the integer floor of the $m$ -th root of a natural number $y$ , denoted as $\lfloor y^{1/m} \rfloor$ , where $y > 2$ and $m > 1$ . This calculation is a fundamental step in number theory, specifically for identifying whether a natural number $y$ is a perfect power (i.e., whether there exist natural numbers $x$ and $m > 1$ such that $y = x^m$ ). While traditional approaches utilize binary search to find $x$ within the range $[2, \lg y]$ , the author notes that such methods are not computationally efficient in the bit model of arithmetic, despite being practical.

Methodology
The paper proposes two distinct algorithms based on the Newton-Raphson method, adapted from real-number root finding to integer arithmetic. Both algorithms aim to compute $x = \lfloor y^{1/m} \rfloor$ by iteratively refining an initial guess $x_0$ until convergence.

Algorithm 1 (Direct Adaptation):
This approach modifies the standard Newton-Raphson iteration for $f(x) = y - x^m = 0$ . The real-valued update step $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ is converted to integer arithmetic by applying the floor function to the fraction:
$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$
The initial value $x_0$ is derived from the logarithm of $y$ to ensure $x_0 \ge y^{1/m}$ . The convergence analysis is complex, distinguishing between three cases:
1. A decreasing sequence that stabilizes ( $x_{n+1} = x_n$ ).
2. A decreasing sequence that "flips" and increases ( $x_{n+1} > x_n$ ).
3. Continued decrease.
  The algorithm terminates when a flip or a repeat occurs, at which point the solution is determined to be either $x_n$ or $x_n + 1$ , verified by checking if $x_n^m \le y < (x_n+1)^m$ .
Algorithm 2 (Refined Integer Recurrence):
This approach utilizes a different algebraic rearrangement of the Newton-Raphson formula:
$x_{i+1} = \left\lfloor \frac{(m-1)x_i + \lfloor y/x_i^{m-1} \rfloor}{m} \right\rfloor$
This formulation leverages the property $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ to maintain integer integrity. The initial value $x_0$ is chosen as $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$ , ensuring $x_0 \ge y^{1/m}$ .
The convergence proof for Algorithm 2 is more streamlined. It establishes that the sequence is non-increasing as long as $x_i > y^{1/m}$ . The algorithm stops when $x_{i+1} \ge x_i$ , at which point the proof demonstrates that $x_i$ must equal $\lfloor y^{1/m} \rfloor$ .

Key Contributions

Integer Newton-Raphson Formulations: The paper presents two specific integer-based adaptations of the Newton-Raphson method for calculating $\lfloor y^{1/m} \rfloor$ .
Convergence Proofs: Rigorous mathematical proofs are provided for both algorithms, establishing that they converge to the correct integer floor value. The proofs analyze the behavior of the sequence relative to the true root $Y = y^{1/m}$ , handling cases where the sequence overshoots or stabilizes.
Initial Value Selection: Both algorithms include specific, computationally efficient methods (using bit shifts and logarithms) for selecting an initial guess $x_0$ that guarantees the sequence starts above or at the true root.

Results
The paper provides illustrative examples for both algorithms using various values of $y$ and $m$ (e.g., $y=108, m=8$ ; $y=96889010407, m=13$ ).

Both algorithms successfully converge to the correct integer root.
In the provided examples, Algorithm 1 generally requires fewer iterations than Algorithm 2. For instance, in the case of $y=52523350144$ and $m=7$ , Algorithm 1 converges in 4 steps (32, 34, 34), while Algorithm 2 takes 7 steps (64, 54, 46, 40, 36, 34, 34).
The author attributes the performance difference in the later examples to the more targeted choice of the initial value $x_0$ in Algorithm 1.

Significance and Claims
The paper explicitly states that the techniques for using Newton-Raphson for integer problems are not novel, citing existing literature (specifically reference [2]). Consequently, the authors do not claim novelty for the underlying mathematical concept. Instead, the stated intent of the paper is to provide an "archival reference" for these specific methods and their detailed proofs. The work serves to formalize the adaptation of Newton-Raphson for integer perfect power identification, offering a potentially more efficient alternative to binary search in bit-complexity models, though the paper remains modest regarding claims of superiority over established methods.