7
$\begingroup$

I have always used a calculator for determining roots But I think it would be useful to know how to do this on paper. Are there different procedures for calculating square roots than for cubic roots or does it all use the same principles?

So my question is how does one calculate the root of a number by hand (so to speak)?

$\endgroup$
1

5 Answers 5

6
$\begingroup$

A variety of techniques are shown in Wikipedia. Several of them generalize to cube roots. The choice depends on what accuracy you want and how much work you are willing to do. For low accuracy you can often use a table you may have memorized and a small correction. For example, to find $\sqrt{26}$ you can say $26=25\cdot 1.04$, so $\sqrt {26}=\sqrt{25}\sqrt {1.04}\approx 5\cdot 1.02 =5.1$ where we have used $\sqrt {1+x} \approx 1+\frac x2$ for small $x$. The same works for cube roots using $\sqrt[3]{1+x} \approx 1+\frac x3$

$\endgroup$
3
$\begingroup$

One practical way is to use Newton iteration (Wikipedia calls it the Babylonian method, check details there). For cubic roots: $$ f(x) = x^3 - n = 0 $$ gives the Newton iteration: $$ x_{k + 1} = x_k - \frac{f(x_k}{f'(x_k)} = \frac{1}{3} (2 x_k + n / x_k^2) $$ Starting point can be cooked up just like for square roots. Let $n$ have $d + 1$ digits, then one can use: $$ x_0 = \begin{cases} 1 \cdot 10^{d / 3} & d \bmod 3 = 0 \\ 2 \cdot 10^{\lfloor d / 3 \rfloor} & d \bmod 3 \ne 0 \end{cases} $$ A technique Newton himself used was to use the binomial expansion of $(1 + x)^{1/2}$ for small $\lvert x \rvert$, i.e., take the nearest square $s^2$ and: $$ n^{1/2} = s \left(1 + \frac{n - s^2}{s^2}\right)^{1/2} $$

$\endgroup$
2
$\begingroup$

There's a marvelous method for square roots described here:

http://johnkerl.org/doc/square-root.html

It's a direct computation based on $(a+b)^2 = a^2 + 2ab + b^2$, where $a$ is the digits known so far and $b$ is the digits not yet known. Each iteration gets the next digit moved from $b$ to $a$.

I still don't think of this as an "iterative" method, though - it's not really computing a correction at each step. It's a literal calculation of the next digit, which feels like a slightly different thing to me.

$\endgroup$
1
$\begingroup$

There's a paper-and pencil square root algorithm that works pretty well, based on the following idea: Suppose $n$ is the number we want to find the square root of, and $n'$ is the number you get by dropping its last two digits $\delta$. Then $n = 100n' + \delta$.

Say we already have $g$, a good guess for $\sqrt{n'}$. We want to find a good guess for $\sqrt n$. $10g$ will be a good start, but we would like to adjust $10g$ upwards to take the last two digits, $\delta$, into account. So what $\epsilon$ can we add to $10g$ so that $(10g+\epsilon)^2 \approx 100n' + \delta$?

We can try to solve for $\epsilon$ in:

$$\begin{align} (10g+\epsilon)^2 & \approx 100n' + \delta \\ 100g^2+20g\epsilon+\epsilon^2 & \approx 100g^2+\delta \\ 20g\epsilon+\epsilon^2 & \approx \delta\\ \epsilon & \approx \frac\delta{20g+\epsilon} \end{align} $$

so take $\epsilon$ so that $\epsilon(20g+\epsilon) \approx \delta$; then $10g+\epsilon$ is a guess for $\sqrt n$. We can repeat this process to find guesses for longer and longer numbers.

(This is the algorithm Brian mentioned in his comment.)

Here is an example. Let's find the square root of 142857. To do that we need a guess for the square root of 1428, to do that we need a guess for the square root of 14. A good guess is 3. So we have $n'=14, g=3$. We know that $(30)^2\approx 1400\approx 1428$, and we want a better guess for $\sqrt{1428}$. So we'd like to find $\epsilon$ such that $$\begin{align} (30+\epsilon)^2 & \approx 1428\\ 900 + 60\epsilon + \epsilon^2 & \approx 1428 \\ \epsilon(60+\epsilon) & \approx 528 \end{align} $$ Eyeballing this, it looks like $\epsilon=7$ is about right. So our new guess is that $\sqrt{1428}\approx 37$.

Now we want $\sqrt{142857}$ and we guess that $370$ is not too far off. We want $\epsilon$ so that $$\begin{align} (370+\epsilon)^2 & \approx 142857\\ 136900 + 740\epsilon + \epsilon^2 & \approx 142857 \\ \epsilon(740+\epsilon) & \approx 5957 \end{align} $$

$\epsilon=8$ is a just a shade too big, but much closer than $\epsilon=7$, so the answer is a shade under 378. If we wanted to continue, we could take $\epsilon=8$ and calculate the amount by which the square root should fall short of 378, or we could take $\epsilon=7$ and calculate the amount by which the square root should exceed 377.

It's not hard to come up with a cube (or higher) root analog of this algorithm, but it's not practical, because instead of trying to estimate an $\epsilon$ that makes $20g\epsilon+\epsilon^2\approx \delta$, which is a not-quite simple division, you have to estimate an $\epsilon$ that makes $300g^2\epsilon+20g\epsilon^2\epsilon^3\approx \delta$, which is too hard.

$\endgroup$
0
$\begingroup$

Use my method: The natural algorithm

See the computational representation of the algorithm in the bottom:

Let $N$ be the number that we want to calculate its cubic root.

The cubic root of $N$ is calculated in two stages:

The first stage: finding the nearest real root of $N$:

We make $n=N$

  1. We subtract from $n$ the terms of $3x^2-3x+1$ starting from $x=1$
    • While $n>0$, we make $x=x+1$, and we proceed the substraction.
    • When $n=0$, this stage stops and the number $N$ has a real cubic root of $x$.
    • When $n<0$, this stage stops, the nearest real cubic root is $x-1$, and we continue the second stage to find the numbers after the comma.

The second stage: Finding the numbers after the comma:

Let $x$ be the nearest real cubic root of $N$

Let $b=N-x^3$

The following process is repeated for the number of digits we want to find after the comma:

We divide this process into 3 steps

  1. Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a thousand

  2. Step 2: We assume $s=x$,

  3. Step 3: We subtract $3s^2+3s+1$ from $b$

    • If the result of $b$ is greater than zero:
      • we add to $s$ one, and continue from step 3.
    • If the result of $b$ is less than zero:
      • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$
      • In the space after the comma, we write the number $i$
      • We get to b the quotient of $3s^2+3s+1$
      • We add to $x$ the number of subtractions $i$,
      • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

E.g.

A number with a real cubic root

$N=64; \sqrt[3]N=?$

We make $n=N$

  1. We subtract from n the terms of $3x^2-3x+1$ starting from $x=1$

$x=1: n=64-(3x^2-3x+1)=64-1=63$

$x=2: n=63-(12-6+1)=63-7=56$

$x=3: n=56-19=37$

$x=4: n=37-37=0$

  • this stage stops and the number $N$ has a real cubic root of $x$.

$\sqrt[3]N=x; \sqrt[3]64=4$


E.g.

A number with an unreal cubic root

$N=66; \sqrt[3]N=?$

We make $n=N$

  1. We subtract from n the terms of $3x^2-3x+1$ starting from $x=1$:

$x=1: n=66-(3x^2-3x+1 )=66-1=65$

$x=2:n=65-(12-6+1)=65-7=58$

$x=3:n=58-19=39$

$x=4:n=39-37=2$

$x=5:n=2-61=-59$

  • This stage stops, the nearest real cubic root is $x-1$, and we continue the second stage to find the numbers after the comma.

$$\sqrt[3]N=x-1; \sqrt[3]66≈5-1≈4$$

Let $x$ be the nearest real cubic root of $N$: $$x=4$$

Let $b=N-x^3$: $$b=N-x^3=66-64=2$$

1- Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a thousand: $$x=x×10=40$$ $$b=b×1000=2000$$

2- Step 2: We assume $s=x$: $$s=40$$

3- Step 3: We subtract $3s^2+3s+1$ from $b$

$b=b-(3s^2+3s+1)=2000-4921=-2921$

  • As the result of $b$ is less than zero:
    • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$: $$i=0$$
    • In the space after the comma, we write the number $i$: $$\sqrt[3]66≈4.0$$
    • We get to $b$ the quotient of $3s^2+3s+1$: $$b=2000$$
    • We add to $x$ the number of substractions $i$: $$x=x+0=40$$
    • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

4- Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a thousand: $$x=x×10=400$$ $$b=b×1000=2000000$$

5- Step 2: We assume $s=x$: $$s=400$$

6- Step 3: We subtract $3s^2+3s+1$ from $b$:

$b=b-(〖3s〗^2+3s+1 )=2000000-481201=1518799…(i=1)$

  • If the result of $b$ is greater than zero:
    • we add to $s$ one, and continue from step 3

$s=s+1=401: b=b-(3s^2+3s+1)=1518799-483607=1035192…(i=2)$

$s=402: b=1035192-486019=549173…(i=3)$

$s=403: b=549173-488437=60736…(i=4)$

$s=404: b=60736-490861=-430125$

  • As the result of $b$ is less than zero:

    • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$: $$i=4$$

    • In the space after the comma, we write the number $i$: $$\sqrt[3]66≈4.04$$

    • We get to b the quotient of $3s^2+3s+1$: $$b=60736$$

    We add to $x$ the number of substractions $i$: $$x=x+4=404$$

    • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

7- Step 1: We multiply the number $x$ by ten, and we multiply the number $b$ by a thousand: $$x=x×10=4040$$ $$b=b×1000=60736000$$ 8- Step 2: We assume $s=x$: $$s=4040$$

9- Step 3: We subtract $3s^2+3s+1$ from $b$:

$b=b-(3s^2+3s+1)=60736000-48976921=11759079…(i=1)$

  • If the result of $b$ is greater than zero:
    • we add to $s$ one, and continue from step 3

$s=s+1=4041: b=b-(3s^2+3s+1)=11759079-49001167=-37242088$

  • As the result of $b$ is less than zero:
    • We make $i$ the number of subtractions in step 3, not counting the time that produced $b<0$: $$i=1$$

    • In the space after the comma, we write the number $i$: $$\sqrt[3]66≈4.041$$

    • We get to $b$ the quotient of $3s^2+3s+1$: $$b=11759079$$

    • We add to $x$ the number of substractions $i$: $$x=x+1=4041$$

    • We continue with the values of $x$ and $b$ from step 1 to find more numbers after the comma.

Computational representation of the algorithm in JavaScript:

https://codepen.io/am_trouzine/pen/GRyoWbM

Nth root calculation:

https://m.youtube.com/watch?v=uEpv6_4ZBG4&feature=youtu.be

My notes:

https://github.com/am-trouzine/Arithmetic-algorithms-in-different-numeral-systems/blob/master/Arithmetic%20algorithms%20in%20different%20numeral%20systems.pdf

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