The Square Root Algorithm
Humans have been fascinated with square roots since eternity, the early motivation being fuelled by utilitarian questions such as — “given an area, construct a square equal to the area”. That requires us to know the side length of the square, which is, of course— the area’s square root.
We soon realised that not every natural number happens to be a perfect square. Over time, we discovered that the square roots of such numbers are not only non-integral but also non-rational. In fact, initial discoveries concerning the nature of root 2 were our first encounter with the irrational realm. Certainly, chasing square roots has taught us a lot!
Table of Contents
This article, however, focuses on the perfect squares. Here’s a quick overview of the content covered below —
- Recap: Procedures for computing square roots.
- The Square Root Algorithm.
- Why does the algorithm work? — The reasoning behind the algorithm.
- The Square Root Algorithm in Binary Base.
- Concluding remarks.
So, given a perfect square, how can we determine its square root? As you might recall, there are two elementary procedures ubiquitously taught in middle school for this purpose —
- Prime Factorisation: This is the naïve way of extracting square roots. Herein, we carry out prime factorisation of the given number and then group the factors in pairs of two. We then multiply the numbers from each group to arrive at the square root. The rationale behind the procedure is self-explanatory. For example,
- Digit-by-digit calculation: Notice that the above method turns out to be extremely tedious when dealing with large numbers. Also, in cases where the smallest prime factor of the given number is quite large, we may not even be able to start with the procedure (e.g., 12643277 = 3089 * 4093). This is where the digit-by-digit calculation technique (henceforth referred to as the square root algorithm, or simply algorithm) comes in real handy. And that is precisely what this article is about — how does the algorithm operate, its features, and most importantly, why it works (probably the most overlooked part)! So, let’s dive straight into it.
A quick note on symbols employed
First, a quick description of some symbols is used below. Let a and b be two natural numbers. Then —
- By ab, we represent the usual multiplication, i.e., ab = a * b.
- By a|b, we represent the number formed by placing b to the right of a.
For example, if a = 789 and b = 23, then a|b = 78923.
The Square Root Algorithm
As usual, an algorithm is best understood via a walkthrough example. So, below is the calculation of root 50,965,321 followed by the detailed steps:
Steps
- Pairing: Starting from the right, group the digits of the given number in pairs of two. In the above example, the groups are highlighted via underlines — (21), (53), (96), and (50). Note — If the number contains an odd number of digits, then the leftmost group will have a single digit only.
- Initial guess: Start with the leftmost group. Find the maximum digit whose square is less than or equal to the leftmost group.
In our example, the number represented by the group = 50.
So, the maximum digit whose square ≤ 50 is 7. - Note down the number obtained from the previous step at the top. This will form the first digit of the square root. Let’s call the current number present at the top as “current partial square root”, denoted by p.
In our case, the current partial square root, p = 7.
Subtract the square of this number from the leftmost group and note down the remainder.
In our case, the remainder = 50–49 = 1. - Now, bring down the next group’s digits next to the remainder.
Call the new number r.
In our example, we bring down 96 to get 196. That is r = 196. - Hit and trial:
Now, find the greatest digit d such that ((2p)|d) * d ≤ r.
In our example, 2p = 2* 7= 14 (shown in red in the figure).
We start with d = 1, 141 * 1 = 141. Next,
With d = 2, 142 * 2 = 284 > 196.
Hence, for our case, d = 1. - The d obtained from the above step is the next digit of the square root. So, place it at the top, to the right of the current partial square root.
That is, p_new = p_old | d.
Further, find out the new remainder as —
remainder = r— (((2p)|d) * d)
In our case, new value of remainder= 196–141 = 55. - Repeat steps 4 to 6 till we exhaust the given number. If the number was a perfect square, then we’d have 0 as the final remainder, and the square root would be equal to the number present at the top!
Here’s another example you can go through to aid your understanding. Note that in the below case, the leftmost group has a single-digit only (as the total number of digits are odd) —
The Rationale behind the Algorithm
Now, we come to the heart of this article!— Why does the square root algorithm work, what’s the reasoning behind it?
The answer, in a nutshell, is that the algorithm exploits the underlying algebra of the decimal place value system.
Consider you have a natural number, a. Also, you have a digit, b. That is, b is one among 0–9.
Then, we have —
The above is exactly what the algorithm takes advantage of. The basic principle is —
If we know all but the last one digit of the square root of a number, then we can get to the remaining digit by subtracting 100 times the square of the number formed by the other digits from the square of the given number, and then searching for a digit, d, such that ((2a)|d)d equals that difference.
The algorithm starts with an initial guess (step 2 above), and then iteratively applies the above principle to arrive at the square root.
Additional remark: The principle also explains why we group the digits into two —
- First of all, intuitively, the square of a number contains roughly twice the number of digits as the number itself. That’s because, if a is an n-digit number, then —
- So, it’s fair to expect that two digits from the square would correspond to a single digit of the square root.
- Now, note that we subtract 100 times the square of the partial square root from the (current remainder | next group). That’s why the next group should consist of two digits (with a single digit, we might run into negatives).
- Why do we begin grouping from the right, and not the left?
That’s because, if we begin grouping from the left for a number containing an odd number of digits, then we’ll have a single digit at the right end. So, in the final iteration, we would have just a single digit to bring down next to the remainder, which should not happen. In such cases, though we’ll have a single digit in the first step, that’s okay as it is the initial guess step. The important thing is that every group coming in the subsequent iterations should have two digits.
Let’s work through another example —
Steps —
- Initial guess: Since 6 is the largest digit whose square ≤ 38(the leftmost group), the first digit of our square root is 6.
- Next, we use the above principle to arrive at the next digit of the square root. Our number (whose square root is to be found) during this iteration is 3831. So, from 3831, we subtract 100 times the square of the current partial square root. That is 3831 — 100.6² = 231.
- Now, we search for the largest digit, d, such that (12|d)d ≤ 231 (because 2 * the current partial square root = 2 * 6 = 12). We get d = 1.
- Next, we bring down the next group to the right of the remainder to get 11061. Note that 11061 = 383161 — 100.61² (61 is the current partial square root).
- Now, we search for the largest digit, d, such that (122|d)d ≤ 11061 (because 2 * the current partial square root = 2 * 61 = 122). We get d = 9.
- Since the final remainder is 0, we have found an exact square root for the given number!
Note: At each step of the algorithm, we get the largest number whose square is less than or equal to the number formed by the digits covered till then. Using the above example,
- 6 is the largest number whose square ≤ 38.
- 61 is the largest number whose square ≤ 3831.
- 619 is the largest number whose square ≤ 383161.
Now, let’s test our understanding of the algorithm by trying it out in binary base!
The Algorithm in Binary Base
The crux of the algorithm remains the same. That is, we go about finding the square root digit-by-digit, building upon the value obtained thus far. Note that the binary number system has only two digits (also known as bits) — 0 and 1. Let us see what tweaks our algorithm needs in the binary world.
Consider you have a binary number, a. Also, you have a bit, b. That is, b is either 0 or 1.
Then —
So, the basic principle here is —
If we know all but the last one bit of the square root of a number, then we can get to the remaining bit by subtracting 4 times the square of the number formed by the other bits from the square of the given number, and then searching for a bit, d, such that (a|0d)d equals that difference.
Let’s understand this with the help of an example, square root of 10101001 (169)—
Steps (as most of the below steps are similar to the ones described above for base 10 calculations, therefore we have used succinct wording here, please refer to the base 10 examples if you encounter any understanding gaps) —
- Pairing: As before, we pair the numbers in groups of two from right to left.
- Initial guess: The leftmost group is 10 (i.e., 2). So, we find the largest bit, d, such that d² ≤ 10. We get d = 1. This is the first bit of our square root.
- We subtract 1 from 10 and bring down the next group to the right of the remainder. Effectively, this is where we are doing ((a|b)² — a²|00).
- Now, we try finding the largest bit d such that (1|0d)d ≤ 110. We get d = 1. This is the next bit of the square root.
- We repeat steps 3 and 4 until the given number is exhausted. If the number was a perfect square, we would get zero remainder at the end, and the number at the top would represent the square root. In our case, since we started with a perfect square (169 = 13²), we got 1101 as the final answer. 1101 is the binary equivalent for 13!
Pros
Note how simplified the algorithm execution is in the binary world!
Cons
However, simplicity comes at a cost. The number of steps to execute increases, as a given number takes up more digits in binary as compared to the decimal system. Taking the above example, we’d have needed two iterations to get to the square root of 169 in base 10. However, in the binary system, it took us four iterations to get there.
Note also that the algorithm retains its salient feature of iteratively producing the greatest number whose square is less than or equal to the number traversed thus far. From the above —
- 1 (1) is the largest number whose square is less than or equal to 10 (2).
- 11 (3) is the largest number whose square is less than or equal to 1010 (10).
- 110 (6) is the largest number whose square is less than or equal to 101010 (42).
- 1101 (13) is the largest number whose square is less than or equal to 10101001 (169).
Concluding remarks
As noted in the beginning, though the square root algorithm is widely practiced, the rationale behind it is seldom given due diligence. This article was an attempt at rectifying the situation. Like most people, I personally learned this algorithm in middle school. And like most people, I had no clue why this algorithm works. It remained perhaps the only thing in school mathematics that I couldn’t justify to myself.
Fortunately, I was recently led to the proof of the algorithm while going through something similar in Aryabhata’s magnum opus, Aryabhatiya. Yes, it ultimately took me 15 years to finally convince myself why the algorithm works — but it was worth the wait!
More important than that, however, is recognising how the square root algorithm epitomises the simplicity and efficiency of the decimal place value system. In today’s world, where we take this remarkable system for granted, it’s imperative that we take a step back and realise just how seminal a discovery it was.
To quote Laplace (1749–1827),
The ingenious method of expressing every possible number using a set of ten symbols (each symbol having a place value and an absolute value) emerged in India. The idea seems so simple nowadays that its significance and profound importance is no longer appreciated. Its simplicity lies in the way it facilitated calculation and placed arithmetic foremost amongst useful inventions. The importance of this invention is more readily appreciated when one considers that it was beyond the two greatest men of Antiquity, Archimedes and Apollonius.
— Laplace
To get a feel for how much the decimal place value system facilitates our calculations — forget square roots, try multiplying 14 (XIV) by 42 (XLII) in Roman numerals, and see for yourself!
