In a previous post I showed how to approximate the square root of a number through an iterative process that consisted of a first guess and a sequence of ajustments. In this post I will show an algorithm to find the square root of any number by hand.
The method I am about to describe can be used with any real number, either a perfect square or not, integer or not, rational or not. I will start by exposing a train of thought that shows how the algorithm work and then I will proceed to present the steps that the algorithm consists of. If you are only interested in the final form of the algorithm, you can skip to that part here.
In what follows, if $a, b$ are digits then the notation $ab$ represents the number $10a + b$ instead of the number $a\times b$. We start by noting that, if we are to calculate $\sqrt{N}$ by hand and $\sqrt{N}$ is irrational, we will have to settle for an approximation with a finite number of decimal places. On the other hand, if $\sqrt{N} = a_0a_1\cdots a_n.b_0\cdots b_m$, then $\sqrt{10^{2m}N} = a_0a_1\cdots a_nb_0 \cdots b_m \in \mathbb{Z}$. This means we can assume that the square root we are computing is an integer. This has no practical impact on the algorithm but it does simplify what follows:
Let $a_0a_1\cdots a_n = \sqrt{N}$ be the number we want to find given that we want to compute the square root of $N$. We compute that $$\begin{align} N &= (a_0a_1\cdots a_n)^2 \\ &= (a_010^n + a_110^{n-1} + \cdots + a_n)^2 \\ &= (a_010^n)^2 + (2[a_010^n] + a_110^{n-1})a_110^{n-1} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ (2[a_0 10^n + a_1 10^{n-1}] + a_2 10^{n-2})a_2 10^{n-2} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ \cdots + (2[a_010^n + \cdots + a_{n-1}10] + a_n)a_n\end{align}$$ For the more meticulous, the previous expansion of the square is valid because $$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n \left(2\sum_{j=1}^{i-1} a_j + a_i \right)a_i$$ is trivially provable by induction.
In our case we see that, from left to right, we have the digits of decreasing magnitude and the term with $(2[x] + a_i10^{n-i})a_i10^{n-i}$, where $x$ is a sum that depends only on the $a_j$ with $j < i$, has the digits with magnitude greater than that of $a_i$. We also define $$\begin{cases} N_0 = N\\ N_{i+1} = N_{i} - (2[\sum_{j=0}^{i-1} a_j^{n-j}] + a_i10^{n-i})a_i10^{n-i} \end{cases}$$ What we see now is that we can create an iterative method to find the digits $a_i$. Note that $a_0$ is the largest digit $d$ such that $(d10^n)^2 \leq N$. Having found $a_0$ we can construct $N_1$ and then notice that $a_1$ is the largest digit $d$ such that $(d10^{n-1})^2 \leq N_1$. Having found $a_1$ we can construct $N_2$ and then notice that $a_2$ is the largest digit $d$ such that $(d10^{n-2})^2 \leq N_2$. And so on and so forth, up until the point where $a_n$ was the largest digit $d$ such that $d^2 \leq N_n$.
Having gotten this far, either $N_{n+1} = 0$ - which means $a_0a_1\cdots a_n$ is the exact square root of $N$ - or $N_{n+1} > 0$ and in that case the number we computed is an approximation by defect of $\sqrt{N}$, which we can improve by including more digits, by appending zeroes to the right of $N$.
Summing up, the algorithm - which is far from trivial when compared to the usual algorithms for multiplication or division - goes like this:
We look at the number from which we want to extract the square root and, from right to left, group the digits two by two (this has to do with the fact that, at each point, we are only working with one digit from the square root).
Now we draw some auxiliary lines, leaving some space between the number and the vertical line just in case we want to add some decimal places, and start working from left to right. We start with the leftmost group, which is just the $7$, and we try to figure out what is the largest digit that, when squared, isn't greater than $7$. Of course it is $2$, because $2^2 = 4 < 7$ and $3^2 = 9 > 7$. Because we chose $2$, it means $2$ is the first digit of the square root, we mark it as correct and subtract $2^2 = 4$ from the $7$. We bring the next group down and keep going: 
This is the step that repeats every time, always in the same fashion: we take everything we already got right - only the $2$ in this case - we double it - $2\times 2 = 4$ and then we look for the largest digit $d$ such that $4d \times d \leq 338$ (remember that $4d$ is not $4\times d $ but $40+d$). I like to represent this question in the following manner: 
Usually this step takes some trial and error... If $d = 6$, $46 \times 6 = 276$ which looks small. $47 \times 7 = 329 < 338$ and $48 \times 8$ is too big, thus $7$ is the right digit. We mark $7$ as correct, subtract $329$ from $338$ and bring the next group of two digits down. Now we rinse and repeat. 
We take everything we know is correct - the $27$ in this case - double it to get $54$ and then ask for the largest digit $d$ such that $54d \times d \leq 929$. 
In this case it is straightforward to see that we have to pick $d = 1$, marking it as correct. We do that, subtract $541$ from $929$, bring the next group of two digits down and repeat everything. Only that we are out of two-digit groups, meaning what we have now, $271$, is the integer part of the square root of $73829$. If we want to find some decimal places, we add pairs of zeroes. 
Having added those two zeroes, we keep doing what we have been doing. Take what we have - which is $271$ - double it to get $542$ and then ask for the largest digit $d$ such that $542d \times d \leq 38800$. 
Well, $5000 \times 7 = 35000$ so we try $d = 7$, $5427 \times 7 = 37989$ which is good by just a little bit. We mark the $7$ as correct and subtract $37989$ from $38800$. If we want more decimal places, we bring another pair of zeroes down. 
Because I do not what to keep going, I don't need to bother finishing that subtraction. Notice how every digit we mark is correct, thus our successive approximations are always by defect. In our case, we know that the square root of $73829$ starts with $271.7$.
This method can keep going while there is paper and patience left, giving a sequence of approximations by defect. If the number is a perfect square, the method stops when we reach the last group of two digits.
I hope you understood how the method works! Leave your thoughts below as a comment!
The method I am about to describe can be used with any real number, either a perfect square or not, integer or not, rational or not. I will start by exposing a train of thought that shows how the algorithm work and then I will proceed to present the steps that the algorithm consists of. If you are only interested in the final form of the algorithm, you can skip to that part here.
In what follows, if $a, b$ are digits then the notation $ab$ represents the number $10a + b$ instead of the number $a\times b$. We start by noting that, if we are to calculate $\sqrt{N}$ by hand and $\sqrt{N}$ is irrational, we will have to settle for an approximation with a finite number of decimal places. On the other hand, if $\sqrt{N} = a_0a_1\cdots a_n.b_0\cdots b_m$, then $\sqrt{10^{2m}N} = a_0a_1\cdots a_nb_0 \cdots b_m \in \mathbb{Z}$. This means we can assume that the square root we are computing is an integer. This has no practical impact on the algorithm but it does simplify what follows:
Let $a_0a_1\cdots a_n = \sqrt{N}$ be the number we want to find given that we want to compute the square root of $N$. We compute that $$\begin{align} N &= (a_0a_1\cdots a_n)^2 \\ &= (a_010^n + a_110^{n-1} + \cdots + a_n)^2 \\ &= (a_010^n)^2 + (2[a_010^n] + a_110^{n-1})a_110^{n-1} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ (2[a_0 10^n + a_1 10^{n-1}] + a_2 10^{n-2})a_2 10^{n-2} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ \cdots + (2[a_010^n + \cdots + a_{n-1}10] + a_n)a_n\end{align}$$ For the more meticulous, the previous expansion of the square is valid because $$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n \left(2\sum_{j=1}^{i-1} a_j + a_i \right)a_i$$ is trivially provable by induction.
In our case we see that, from left to right, we have the digits of decreasing magnitude and the term with $(2[x] + a_i10^{n-i})a_i10^{n-i}$, where $x$ is a sum that depends only on the $a_j$ with $j < i$, has the digits with magnitude greater than that of $a_i$. We also define $$\begin{cases} N_0 = N\\ N_{i+1} = N_{i} - (2[\sum_{j=0}^{i-1} a_j^{n-j}] + a_i10^{n-i})a_i10^{n-i} \end{cases}$$ What we see now is that we can create an iterative method to find the digits $a_i$. Note that $a_0$ is the largest digit $d$ such that $(d10^n)^2 \leq N$. Having found $a_0$ we can construct $N_1$ and then notice that $a_1$ is the largest digit $d$ such that $(d10^{n-1})^2 \leq N_1$. Having found $a_1$ we can construct $N_2$ and then notice that $a_2$ is the largest digit $d$ such that $(d10^{n-2})^2 \leq N_2$. And so on and so forth, up until the point where $a_n$ was the largest digit $d$ such that $d^2 \leq N_n$.
Having gotten this far, either $N_{n+1} = 0$ - which means $a_0a_1\cdots a_n$ is the exact square root of $N$ - or $N_{n+1} > 0$ and in that case the number we computed is an approximation by defect of $\sqrt{N}$, which we can improve by including more digits, by appending zeroes to the right of $N$.
Summing up, the algorithm - which is far from trivial when compared to the usual algorithms for multiplication or division - goes like this:
We look at the number from which we want to extract the square root and, from right to left, group the digits two by two (this has to do with the fact that, at each point, we are only working with one digit from the square root).
This method can keep going while there is paper and patience left, giving a sequence of approximations by defect. If the number is a perfect square, the method stops when we reach the last group of two digits.
I hope you understood how the method works! Leave your thoughts below as a comment!
- RGS
How to compute any square root by hand
Reviewed by Unknown
on
May 25, 2018
Rating:
Reviewed by Unknown
on
May 25, 2018
Rating:
No comments: