How do algorithms for calculating the square root work?

Question

Algorithms for addition work by taking advantage of the fact that a string of digits can be expanded (e.g. $123 = 1\times 10^2 + 2\times 10 + 3$) and by means of this expansion together with the algebraic properties of addition it can be "creatively reinterpreted" (e.g. $3$ is less than $4$? Well we can reinterpret the $2$ as $2$ $10$s etc...).

But how do traditional algorithms for square roots that they used to teach schoolchildren in the 19th century work?

Answer 1

I'm not exactly sure which algorithms you are referring to, but they could be based off of the Taylor Expansion. For example, if $a$ is small compared to $x$, you know that $$\sqrt{x+a} \approx \sqrt{x} + \frac{a}{2 \sqrt{x}}.$$ So then you could approximate $$\sqrt{103} \approx 10 + \frac{3}{20}.$$ You can get a higher degree of accuracy by taking more terms from the Taylor Expansion.

Answer 2

Sqrt(x) = x / sqrt(x).

You can calculate the square root with pen and paper using a method quite similar to long division, except that with every additional digit the divisor changes.

Answer 3

Two ways I can think of are the Newton's method (improved) and iterative methods

Suppose we want to solve $\sqrt{a}$

Newton's Method (improved):

We try to solve the equation

$$ f(x) = \frac{1}{x^2} - a $$ with the iteration step: $$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{\frac{1}{x_n^2}-a}{-2\frac{1}{x_n^3}}= \\ =x_n-\frac{x_n-x^3_na}{-2}=\frac{3}{2}x_n-\frac{x_n^3a}{2} $$

Iterative method:

We check whether the number $x$ is a square root of $a$, by simply multiplying it with itself and with error $|a-x^2|$. The next part after the initial guess, we need to know if we want to increase the value of x or decrease it (which way do we want to take the guesses), and we use newton's method to do that: $$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. $$ where $f(x)=x^2-a$ giving us: $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n^2-a}{2x_n}= \\ =\frac{1}{2}x_n+\frac{a}{2x_n} $$

Answer 4

To see how the digit-by-digit method works, it might work best by stepping through an example. Let's set $N = 57$, and our aim is to find the sequence of digits $d_0, d_1, \ldots$ such that $\sqrt{N} = \sum_{n = 0}^\infty d_n 10^{-n}$. Notice that for every $n$, we want $d_0.d_1 \ldots d_n \leq \sqrt{N} < d_0.d_1 \ldots (d_n + 1) = d_0.d_1 \ldots d_n + 10^{-n}$.

So to find $d_0$, we're just looking for a number $a$ such that $a^2 \leq N < (a+1)^2$, and it's pretty clear that $a = 7$ works because $7^2 = 49 \leq 57 < 64 = 8^2$.

Then to find $d_1$, we now have $(7 + \frac{d_1}{10})^2 \leq 57 < (7 + \frac{d_1}{10} + \frac{1}{10})^2$. If we subtract $7^2$ from all of that, we get:

$$\begin{eqnarray} (7 + \frac{d_1}{10})^2 - 7^2 & \leq & 57 - 7^2 & < & (7 + \frac{d_1 + 1}{10})^2 - 7^2 \\ 49 - 2 \times 7 \times \frac{d_1}{10} + \frac{d_1^2}{10^2} - 49 & \leq & 57 - 49 & < & 49 - 2 \times 7 \times \frac{d_1 + 1}{10} + \frac{(d_1 + 1)^2}{10^2} - 49 \\ \frac{d_1}{10}\left(14 + \frac{d_1}{10}\right) & \leq & 8 & < & \frac{d_1 + 1}{10}\left(14 + \frac{d_1 + 1}{10}\right) \end{eqnarray}$$

So we're now looking for the biggest value for $d_1$ that keeps that left-hand inequality true, since the right-hand inequality is the same thing but using $d_1 + 1$ instead. With some trial and error we'll find that $d_1 = 5$ is right.

We can keep doing the same thing - once we have our $n$th approximation $a_n = d_0.d_1\ldots d_n$, we want to find the next one using the bound $(a_n + d_{n+1} \times 10^{-n-1})^2 \leq N < (a_n + (d_{n+1} + 1) \times 10^{-n-1})^2$, and that then becomes:

$$\begin{eqnarray} (a_n + d_{n+1} \times 10^{-n-1})^2 & \leq & N & < & (a_n + (d_{n+1} + 1) \times 10^{-n-1})^2 \\ \left(a_n^2 + \frac{d_{n+1}}{10^{n+1}}\left(2 a_n + \frac{d_{n+1}}{10^{n+1}} \right) \right) - a_n^2 & \leq & N - a_n^2 & < & \left(a_n^2 + \frac{d_{n+1} + 1}{10^{n+1}}\left(2 a_n + \frac{d_{n+1} + 1}{10^{n+1}} \right) \right) - a_n^2 \\ \frac{d_{n+1}}{10^{n+1}}\left(2 a_n + \frac{d_{n+1}}{10^{n+1}} \right) & \leq & N - a_n^2 & < & \frac{d_{n+1} + 1}{10^{n+1}}\left(2 a_n + \frac{d_{n+1} + 1}{10^{n+1}} \right) \\ \end{eqnarray}$$

So in other words we look at the gap between $a_n^2$ and $N$, and look for the value of $d_{n+1}$ such that the term on the left comes closest to matching that residual gap without going over. And what you'll find (but I won't prove rigorously here) is that the restriction of $d_n$ to single digits means that you will be able to work to within $(2n)$ decimal places, which is why in the "long division"-like method you pull down two digits at a time.