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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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