You are here: HomeArticles → Why square root algorithm works

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

In a nutshell:

Let's say we are to find the square root of a.  The algorithm is finding one more digit to the square root at each 'go'.  (Read here how to use the square root algorithm.) That means it is approaching the actual value of the square root from below, or 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 this far, at each go, one wants 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

and the last line corresponds to the step where the user tries different values of r on that 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 algorithm that resembles long division.  At every 'go' of the algorithm we use a pair of digits from the number and will find one digit in the answer.  In a sense, at each go we get a better approximation of the actual square root.  Since most square roots are irrational numbers, the best one can ever do is just approximate them, usually with a decimal number that has certain number of decimal digits.

From a calculator one finds that to two decimals √3150 =  56.12.  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 √3150 is between 56 and 57.  The third round would give us the decimal digit 1, letting us know √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

Now see 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 or first number (52 is less than 31).

 5 √31 .50
 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 what 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 x 5 = 525
106 x 6 = 636
107 x 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 x 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 x 1 = 1121
1122 x 2 = 2244, so 1 works.

You don't see the subtraction 315000 − 313600 done as such in the calculations, but instead the subtraction 650 − 636 (corresponding to 65000 − 63600).  That is because in the previous 'go' the subtraction 3150 − 2500 was done,  corresponding to 315000 − 250000, which has left the difference 65000.