Is there a process, similar to long division, to do nth roots where n is any positive integer?

Question

I did not even remember how to do square roots from high school, but I vaguely recall it was similar to long division. (Thankfully I remember how to do long division.) I just went to youtube and refreshed my memory on how to do square roots.

Is there a "long root" process to do nth roots? N can be any integer of 2 or more. (N could be 1 too but that is trivial.) The radicand can be any positive number. The radicand does not hafta be a perfect square, perfect cube, or perfect n-power of anything.

Btw, I am aware of factorization. So $\sqrt{153} = \sqrt{9 * 17} = 3\sqrt{17}$. In this case, what I want to do is something like 2 into 17, but instead of long division, use a "long root" process for putting 2 into 17. The process would go on forever, much like 25/7 goes on forever because the remainder never "settles". I would just stop when I get, say, 3 decimal places or however many I think is accurate enough.

Examples:

• $\sqrt{68}$

• $\sqrt[3]{401}$

• $\sqrt[7]{50}$

• $\sqrt[21]{675}$

• $\sqrt[n]{x}$

Answer 1

I'm having trouble understanding exactly what you are asking about but I'll focus on the following "The process would go on forever, much like 25/7 goes on forever because the remainder never "settles". I would just stop when I get, say, 3 decimal places or however many I think is accurate enough."

---

You might want to grab a book on introductory real analysis. R. P. Burn's Numbers and Functions has very good chapters on sequences and completeness that will satisfy your needs.

For example, for any $a$, $0\leq a-\frac{\lfloor a10^n \rfloor}{10^n}<\frac{1}{10^n}$ ($\lfloor x \rfloor$ here is called floor $x$, which is the greatest integer less than $x$). From this we can deduce that for any number $a$ there is a sequence of rational numbers which tends to it. This is because the sequence $(1/10^n)$ tends to zero and so by the squeeze rule for null sequences, the sequence $(\frac{\lfloor a10^n \rfloor}{10^n}-a)$ tends to zero, so by the definition of limit we see how the result is proved. Remember that $\frac{\lfloor a10^n \rfloor}{10^n}$ is always rational.

The chapter on completeness will go over how every nth root of a number exists and is unique.

Hope that points you in the right direction.

Answer 2

In a nutshell, the algorithm for square root works because of the identity: $$ y =(a+x)^2 = a^2 + 2ax + x^2 = a^2 + (2a+x) x $$ In the algorithm you iteratively determine increasing (adding one decimal at the time) values for $a$ by looking for the largest value of $x'$ at the appropriate decimal place so that $$y - a^2 \geq (2a+x') x'$$ You then essentially replace $a$ by $a+x'$ and continue for the next decimal place.

I suppose you could do this for e.g. cube roots by looking at $$ y = (a+x)^3 = a^3 + (3 a^2+3x+x^2) x $$ but it looks rather nasty to carry out in practice.

Answer 3

Partition your number. Separate the number you want to find the nth root of into n-digit intervals before and after the decimal. If there are fewer than n digits before the decimal, then that is the first interval. And if there are no digits or fewer than n digits after the decimal, fill in the spaces with zeroes.

2) Find an initial estimate. Find a number (a) raised to the nth power closest to the first n digits (or the fewer than n digits before the decimal) as a base-ten number without going over. This is the first and only digit of your estimate so far.

3) Modify the difference. Subtract your estimate to the nth power (a^n)from those first n digits and bring down the next n digits next to that difference to form a new number, a modified difference. (Or multiply the difference by 10^n and add the next n digits as a base-ten number.)

4) Find the second digit of your estimate. Find a number b such that  (nC1 a^(n - 1) (10^(n-1)) + nC2 a^(n - 2) b (10^(n - 2)) ) + . . . +  nCn - 1  a b^(n - 2)(10 )  +  nCn b^(n - 1)( 100 ) )b  is less than or equal to the modified difference above (10^n(d ) + d1d2. . . dn).  This becomes the second digit of your estimate so far. • The combinations notation nCr represents n! divided by the product of (n - r)! and r!, where n! = n(n - 1)(n - 2)(n - 3) . . . (3)(2)(1). The notation nCr is sometimes expressed as n over r within tall parentheses without a division bar, and it can be calculated simply as the first r factors of n! divided by r!, which is often written as nPr divided by r!

5) Find your new modified difference. Subtract the two quantities in the last step above (10^n (d ) + d1d2. . . dn minus nC1 a^(n - 1)(10^(n-1)) + nC2 a^(n - 2)b (10^(n - 2)) ) + . . . +  nCn - 1  a bn - 2 (10 )  +  nCn b^(n - 1)(100 ) )b) to form your new modified difference by bringing down the next set of n digits next to that result. (Or multiply the difference by 10^n and add the next n digits as a base-ten number.) 

6)

Find the third digit of your estimate. Find a new number c and use your estimate so far, a (which is now 2 digits), such that  (nC1 a^(n - 1)(10^(n - 1)) + nC2 a^(n - 2)c (10^(n - 2)) + . . . +  nCn - 1  a c^(n - 2)( 10 )  +  nCn c^(n - 1)(100 ) ) c  is less than or equal to the new modified difference in above (10^n (d ) + d1d2. . . dn). This becomes the third digit of your estimate so far.

7) Repeat. Keep repeating the last two steps above to find more digits of your estimate. • This is basically a rolling binomial expansion minus the lead term, where the two terms involved are the prior estimate multiplied by 10 and the next digit to improve the estimate.

[nth root method at wikiHow][1]

Answer 4

I would like to add to the answer of H. H. Rugh by saying that, if you can group the terms of a binomial expansion to isolate its coefficients, then you can organize them on the page in fractional form, which allows you to check whether part of the solution divides them or not, because guessing and multiplying can get messy with more digits and higher powers. I'll do a cube root by presenting two methods in one.

$$N-r=a^3+(3a^2+(3a+b)b)b \iff \frac{N-r}{\left [\frac{a^2}{2a+b}+b \right ]\left [2a+b \right ]}=a+b$$

There is a positive $r$ that is subtracting the number whose root we want to find in case it's not a perfect cube. It's usually done last, because you want the remainder to be as low as possible. The expression on the right is what you get when you organize a third degree binomial expansion into $(a+b)(a^2+(2a+b)b)$ and factor $(2a+b)$ out when it's on the denominator.

---

Let's use both expressions to find the root whose cube is closer to $1953000$ in case it's not a perfect cube.

1. Organize the number in pairs or triples of digits like this $1'953'000$ so that $a^3$ is the closest cube with zeroes behind. In this case, it's $a^3 = 1'000'000 \iff a=100$, which means that you already have $a$. You can subtract its cube and substitute it in both expressions.

$$953000-r=(30000+(300+b)b)b \iff \frac{1953000-r}{\left [\frac{10000}{200+b}+b \right ]\left [200+b \right ]}=100+b$$

2. To guess what a two digit $b$ must be, check $3a^2b=3'00'00b$ so that it's closer to $95'00'00$. I grouped the digits this way because it's a square now. When $b=30$, the expression on the right shows that it's an overestimate, so you have to try $b=20$. It turns out to be correct.

$$953000-r=(30000+(320+c)(20+c))(20+c) \iff \frac{1953000-r}{\left [\frac{10000}{220+c}+20+c \right ]\left [220+c \right ]}=120+c$$

3. Note that I added $c$ for the single digit that is left. Multiplication using the left expression is complicated now. You can use the right one to guess which $c$ added to $220$ divides $10000$. A good estimate would be $c=5$, but it goes over our number, so you can check $c=4$, which does not divide $10000$. It gets cancelled out by the same factor though.

$$953000-r=(30000+(324)24)24 \iff \frac{1953000-r}{\left [\frac{10000}{224}+24 \right ]\left [224 \right ]}=124$$

4. Now you only have to carry multiplications out using the expression on the right, subtract its result from $1953000$ to at least find $r$, and know your root through $a+b+c$. It's $124$, whose cube is closer to the number that we started with, with a remainder of $46376$.

---

As you can see, it's possible to rearrange a binomial expansion on the page so that it's easier to follow, but I don't think that there is a general way to do it for higher powers, because this one did not follow from the square root, so you'll have to see which one suits you the best. I'll edit this answer in case I find something. I hope that I helped.

---

Edit: it turns out that it can be generalized once you (and I) realize that the only terms that were used from the left expression were $a^3$ and $3a^2b$, and $(\frac{a^2}{2a+b}+b)(2a+b)$ from the right one. It's the epsilon approximation of the nth root. There's a good video about it.