You are here: HomeArticles → Why square root algorithm works

# Why the square root algorithm works- the logic behind it

Let's say we want to find the square root of a. Each time the algorithm is applied, it finds one more digit to the square root. That means we are approaching the actual value of the square root from below; in other words, that at each step the approximation is always less than or equal to the actual value of the square root.

If x is the approximation found at a certain point, at the next round we want to find a better approximation x + r so that  x + r ≤ √a. From this inequality follows:

 x + r ≤ √a (x + r)2 ≤ a x2 + 2xr + r2 ≤ a x2 + (2x + r) r ≤ a (2x + r) r ≤ a − x2

The last line corresponds to the step in the algorithm where the user tries different values of r on the empty line so that 2x and something times something is less than the subtraction result.

An example:

Let's say we are trying to find √3150 with the square root algorithm that resembles long division.  At every round of the algorithm we use a pair of digits from the number and will find one digit for the answer. At each round we get a better approximation of the actual square root.

From a calculator we find that √3150 =  56.12 to two decimals. The first round of applying the algorithm would produce the digit 5, telling us that √3150  is between 50 and 60. On the second round we'd find the digit 6, or in other words we would know that √3150 is between 56 and 57.  The third round would give us the decimal digit 1, letting us know that √3150  is between 56.1 and 56.2, and so on.

From now on we will concentrate on ONE single round of applying the algorithm.  Let's say we've already found the digit 5 for the square root, and are using the algorithm to find the next digit r.  Note that r is between 0 and 9 and that the digit 5 means that √3150 is 50 + something.  We can say that √3150  is between 50 + r  and the next whole number, which is 50 + r + 1.  So we know that 50 + r ≤ √3150, and from that one derives that

 50 + r ≤ √3150 (50 + r)2 ≤ 3150 502 + 100r + r2 ≤ 3150 2500 + (100 + r) r ≤ 3150 (100 + r) r ≤ 3150 − 2500 = 650

Next we will examine how the last line (100 + r) r ≤ 650 is used in the algorithm.

First we find a number whose square is less than or equal to the first pair of digits: 52 is less than 31 so 5 works. We write that above the square root line:

5
31.50

This is how the algorithm continues:

 5 √31 .50 - 25 6 50
 5 √31 .50 - 25 (10_) 6 50
 5 √31 .50 - 25 (10_) 6 50
Square the 5, giving 25, write that underneath the 31, and subtract. Bring down the next pair of digits. Then double the number above the line, and write it down in parenthesis with an empty line next to it as shown. Next think which single-digit number something could go on the empty line so that hundred-something times something would be less than or equal to 650.
105 · 5 = 525
106 · 6 = 636
107 · 7 = 749, so 6 works.

Let's try it once more with the next round.  Now we've found √3150 is between 56 and 57, and are looking for the next digit q.  Note that q is between 0 and 9 and that √3150 is between 56 + q/10  and 56 + (q + 1)/10.  So we know that 56 + q/10 ≤ √3150, and from that one derives that

 56 + q/10 ≤ √3150 560 + q ≤ 10√3150 (560 + q)2 ≤ 100 x 3150 5602 + 1120q + q2 ≤ 315000 313600 + (1120 + q) q ≤ 315000 (1120 + q) q ≤ 315000 − 313600 = 1400

You can see how the last line (1120 + q) q ≤ 1400 is used in the algorithm.

 5 6 √31 .50 .00 - 25 (106) 6 50 - 6 36 14 00
 5 6 √31 .50 .00 - 25 (106) 6 50 - 6 36 (112_) 14 00
 5 6 .1 √31 .50 .00 - 25 (106) 6 50 - 6 36 (112_) 14 00
Calculate 6 · 106, write that below 650, subtract, bring down the next pair of digits (in this case the decimal digits 00). Then double the number
above the line, and write it down in parenthesis with an empty line next to it as indicated:
Think what single digit number something could go on the empty line so that eleven-hundred twenty-something
times something would be less than or equal to 1400.
1121 · 1 = 1121
1122 · 2 = 2244, so 1 works.

You don't see the subtraction 315000 − 313600 in the algorithm but instead the subtraction 650 − 636 (corresponding to 65000 − 63600). That is because in the previous round the subtraction 3150 − 2500 was done, corresponding to 315,000 − 250,000, which has left the difference of 65,000.