How do calculators compute square roots?

In school, we all learn how to multiply add and divide numbers. They are simple algorithms and it is easy to conceive how computers perform the same kind of calculations. And this is mostly what happens: instead of decimals, a binary representation is used and instead of humans transistors perform the operations but the rest is quite similar.

But how are more complicated operations, such as square roots calculated?

Iterative methods

There are many ways to calculate the square root, but they all have a common property: they start out with an initial guess and then refine the guess over many steps. These are called iterative methods.

The idea is simple: checking whether a number $x$ is the square root of $a$ is very easy. Just multiply it with itself and you can estimate the error $|a-x^2|$. Now you know if you have to increase or decrease your guess. You do this many times and the accuracy of your guess constantly improves.

The question is, how to change our guess, in which direction and how much? One technique is the Newton-method. It finds the root of a function $f(x)$ by doing the following iteration, starting out from an initial guess $x_0$:
$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}.$$

Note that this solves an equation but we need to take a square root. Well, the trick is simple. Just define $f(x)$ as:
$$f(x)=x^2-a,$$if you wan to take the square root of $a$. Note that the solution of this equation is $\sqrt{a}$!.

We can just substitute the above formula in Newton’s method:
$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}=x_n-\frac{x_n^2-a}{2x_n}=$$ $$=\frac{1}{2}{x}_n+\frac{a}{2x_n}$$This formula reaches high accuracy pretty quickly. The number of correct digits doubles every step. Using 15 digits of precision, 5-6 steps is enough. However, it has a great drawback: it uses division, which is a rather slow operation.

Newton’s method improved

Modern processors can calculate additions and multiplication very fast, almost at the same speed. But divisions are difficult and much slower. Consequently, if our square root calculation algorithm uses division, it will be slow too.

We can apply a clever trick to remove all divisions from our formula: calculate $\frac{1}{\sqrt{a}}$ instead of $\sqrt{a}$!. Once we have $\frac{1}{\sqrt{a}}$, multiply it with $a$ to get $\sqrt{a}$. Using the above equations, we can derive Newton’s method for $\frac{1}{\sqrt{a}}$ . First, the equation we want to solve will be:
$$f(x)=\frac{1}{x^2}-a$$ Then, the iteration step:
$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}=x_n-\frac{\frac{1}{x_n^2}-a}{-2\frac{1}{x_n^3}}=$$ $$=x_n-\frac{x_n-x_n^{3}a}{-2}=\frac{3}{2}{x}_n-\frac{x_n^{3}a}{2}$$This formula has only multiplications and additions. It does have a division by two but that is a cheap operation for computers because they use binary representation.

This is the method that Algeo uses and also many other calculators.

Other methods

There are other ways to calculate the square root. In the last section, I said divisions are expensive so it’s best to avoid them. However many decades ago even multiplication were expensive, some processors didn’t even have a builtin multiplication method! For those cases, there is CORDIC which uses only addition, subtractions and bit shifting.

Some processors use Goldschmidt’s algorithm that calculates $\sqrt{a}$ and $\frac{1}{\sqrt{a}}$ at the same time. If the CPU has fused multiply-add operations (this operation does a multiplication directly followed by an addition), the algorithm is faster than Newton’s method.