1
$\begingroup$

What is the process for determining $\sqrt[n]{x}$, where n and x are both positive integers?

I have seen algorithms for specific cases. n = 2, there is an extraction method where you group the digits of x into pairs, with the leftmost digit being alone if necessary, and then do an extraction process similar to long division.

I have also seen an n = 3 method where the digits of x are grouped intro triplets and a somewhat similar process is done.

However, those methods are not totally similar to each other. Only the "grouping by n digits" is similar. It's hard to explain without copy/pasting both methods, but the squareroot method calls for some copying with doubling the last digit. In the cuberoot method, for some reason there is a squaring of the current "quotient" before multiplying it to some other number (step 4 and 5).


I have never seen a similar a method for n > 3.

Theoretically, some roots can be taken by doing it multiple times. E.g., $\sqrt[4]{23}$ can be done by taking the square root of it twice. However, this is not a good idea for manual extraction, because in practice you are going to get a truncated answer for the first square root, and then trying to take the square root of that truncated decimal number will introduce even more "rounding errors".

So I would really like to find a method for any positive integer n, not just prime numbers. Preferably something that sets up x and n like a division box, but using exponents instead of multiplicands.

(Note, I'm mentioning all this to show that I have tried some work on this on my own.)

(Note, I'm restricting n to positive integers because I know that $\sqrt[\frac{a}{b}]{x} = \sqrt[a]{x^b}$, so rational numbers should be no problem. As for irrational numbers, that would probably be too broad, and I think they will be truncated in practice anyway, e.g., 3.142 = 3142/1000.)


I'm pretty sure a general method for n exists, because calculators let you take the nth root of a number where n can be almost anything. To do this requires an infinitely large lookup table (not possible), or a general method.

So I guess another way of asking this question is, how do calculators do it? What algorithm do they use?


There is one method I know of that works for any positive integer n. The guess and test method. What is the square root of 2? Must be between 1 and 2, so try 1.5. $1.5^2 = 2.25$, that was too high. Try 1.4, slightly too low. Try 1.45, slightly too high, etc.

And note it's okay if the method never ends. After all, we're going to get irrational answers anyway. I just hope there's a better way than the guess and test method. It seems to "converge too slowly" so I can't imagine that calculators use it.

What I'm hoping for is a general method that can be applied to all positive integer n's, rather than finding specific extraction methods for n = 2, n = 3, etc. that are slightly different from one another.

By the way, this arose from a related question about if roots can be thought of as repeated division.

$\endgroup$
8
  • 3
    $\begingroup$ Your question is addressed by this answer where it is explicitly shown how to compute n-th roots efficiently. $\endgroup$
    – user21820
    Dec 17, 2021 at 17:20
  • $\begingroup$ There are digit-by-digit algorithms, but they are very very inefficient in comparison to algorithms based on Newton-Raphson such as in the linked post. $\endgroup$
    – user21820
    Dec 17, 2021 at 17:23
  • $\begingroup$ @user21820 Can you link to one so i can read about it? Remember im looking for a general n-th root algorithm that works for any positive n, not just a specific one like a square root. $\endgroup$
    – DrZ214
    Dec 17, 2021 at 19:09
  • $\begingroup$ Did you even read the post I linked?? $\endgroup$
    – user21820
    Dec 18, 2021 at 4:15
  • $\begingroup$ @user21820 No sry. Didnt even realize you made a double comment. But i see the link now and read it, however your answer there is too complicated for me. But another answer gave a very interesting method involving averages, tho i dont see how to use it for cube root, 4th root, etc. $\endgroup$
    – DrZ214
    Dec 19, 2021 at 21:37

2 Answers 2

2
$\begingroup$

They use fast-converging iterative techniques (faster than "guess and check").

See the $n$th root algorithm. The second answer here also mentions some improvements on this algorithm that are actually used in practice (at least for square roots).

$\endgroup$
1
$\begingroup$

The easiest way to find $\sqrt[n]{a}$ for integer $n$ and $a>0$ efficiently is to use the Newton-Raphson approximation to invert the function $f : x \mapsto x^n - a$. But one must be careful with choosing the right starting point, so that the iteration will converge quadratically. Quadratic convergence means that at each step the error becomes approximately a constant times its square, which is equivalent to the error being proportional to $c^{2^k}$ after $k$ steps, for some $c \in (0,1)$.

  Let $x_0$ be such that $x_0 \in \sqrt[n]{a}·[1,1+\frac{1}{4n})$.

  For each natural $k$ from $0$ to $\infty$:

    Let $x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)} = x_k - \dfrac{{x_k}^n-a}{n{x_k}^{n-1}} = \dfrac{(n-1){x_k}^n-a}{n{x_k}^{n-1}}$.

  Then $( x_k : k \in \mathbb{N} )$ converges quadratically to $\sqrt[n]{a}$ uniformly for all $a>0$.

For the general case, see this answer.

$\endgroup$
2
  • $\begingroup$ Thank you, yes i do understand this first part. Looks a lot like the newton method i remember from college. However what do you mean by "the general case"? Does that mean when n and a are not integers? If so i think i can ignore it. Any non-integer root is truncracted in practice so something like $\sqrt[1.3]{a}$ becomes $\sqrt[13]{a^{10}}$ which can use your method. $\endgroup$
    – DrZ214
    Dec 20, 2021 at 22:03
  • $\begingroup$ @DrZ214: The general case is for arbitrary differentiable functions. I have no idea why you say "looks a lot like the newton method" when I had explicitly stated "Newton-Raphson approximation". Nevertheless, you definitely did not learn how to choose an appropriate starting point. You asked for an algorithm, and a correct algorithm must tell you how to start. $\endgroup$
    – user21820
    Dec 21, 2021 at 7:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.