


Why the LongDivisionType Squareroot Algorithm works


To show why the squareroot algorithm works we use the Proposition 1 below.
The algorithm merely implements for a_{n}a_{n1}...a_{1}a_{0} the decomposition shown on the right side of Equation (1). Let us see how the algorithm obtains
10^{2n}a_{n}^{2} which is the first term on the right side of Equation (1). The algorithm subtracts a_{n}^{2} in the first step. Each of the further subtractions takes place by bringing down two digits. Since this happens n times by the time the digit a_{0} is obtained, the place value of the a_{n}^{2} that was first subtracted becomes (10^{2})^{n} = 10^{2n}. Similarly, the second number subtracted, namely, (10 × 2 × a_{n} + a_{n1})a_{n1}, acquires palce value 10^{2(n1)}, the third number acquires place value 10^{2(n2)}, and so on. Then, adding up all the numbers subtracted in the algorithm gives the decomposition of (a_{n}a_{n1}...a_{1}a_{0})^{2} given by Proposition 1.
We have seen elsewhere that 119025 is a perfect square. What if we are looking for the squareroot of 119026? Then we have a remainder of 1 in the "division" process of the algorithm and so we think of 119026 as 119026.00 and bring down the two zeros. Why?
Since two consecutive integers can not be both perfect squares, 119026 can not be a perfect square. So its squareroot must be of the form
x = a_{n}a_{n1}...a_{1}a_{0}.a_{1}a_{2}...a_{k}, say, up to the kth decimal place, and, so, equals
10^{k}(a_{n}a_{n1}...a_{1}a_{0}a_{1}a_{2}...a_{k}).
Let n+k = m.
Rename a_{i} as a_{k+i}, i = n, n1,...,2,1,0,1,...,k.
Then, x = 10^{k}(a_{m}a_{m1}...a_{k}a_{k1}...a_{0}) and, from Proposition 1,
.
This means that, in finding the squareroot of a number that is not a perfect square, if all the digits to the left of the decimal point have been brought down in the division process of this algorithm, we continue the process beginning from the immediate right of the decimal point, successively bringing down groups of two digits and repeating the "division" as before. After k groups of two digits each are brought down beginning from the digit to the immediate right of the decimal point, we have obtained the squareroot of (10^{k}x)^{2}. Therefore, the value of x which is the squareroot of the given number is obtained up to k decimal digits by dividing the number obtained in the division process by 10^{k}, or by inserting a decimal point just before the last k digits of the "quotient." Observe that the procedure is the same whether or not the given number is an integer. If the number is an integer, but not a perfect square, the groups of digits to the right of the decimal point are all 00.
For numbers that are not integers, parse their digits in two's going left from the decimal point, and then going right from the decimal point.
If there are k groups of two digits each to the right of the decimal point so that the last group has at least one nonzero digit, then the squareroot will have k decimal digits.
In the division process, we insert the decimal point in the "quotient" row just prior to bringing down the first group of two digits after the decimal point of the given number.
We have shown the following.
Proposition 2 (The squareroot algorithm)
Let N be a number in decimal representation. The squareroot of N is obtained by the following procedure.
(1) Beginning at the decimal point, parse N in groups A_{i}, i = 0,..,n, of two digits each going left from the decimal point and then in groups A_{j}, j = 1,...,k, of two digits going right from the decimal point so that N is given by the concatenation A_{n}A_{n1}...A_{1}A_{0} . A_{1}A_{2}...A_{k1}A_{k}, where the leftmost group A_{n} on the left of the decimal point and the rightmost group A_{k}, on the right of the decimal point, each has one or two digits, depending on the number of digits of N.
(2) Choose a_{n} so that (a_{n})^{2} is the largest square not exceeding A_{n}. Let B_{n1} be the number obtained by concatenating (A_{n}  a_{n}^{2}) with A_{n1}. That is, B_{n1} = 100(A_{n}  a_{n}^{2}) + A_{n1}.
(3) For i = n1 to k, choose a_{i}, being the largest singledigit number, so that ((10 × 2 × (a_{n}...a_{i+1}) + a_{i})a_{i} does not exceed B_{i}. Let B_{i1} = 100(B_{i}  ((10 × 2 × (a_{n}...a_{i+1}) + a_{i})a_{i}) + A_{i1}.
(4) Then the squareroot of N is a_{n}a_{n1}...a_{1}a_{0}.a_{1}a_{2}...a_{k}, up to k decimal digits.
Observe that when N is an integer, A_{i} = 00, for i = 1 to k. And when N is an integer that is a perfect square, B_{i} = 0 for i = 1 to k as well.
Ü BACK
MathPath  "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001 MathPath
Last updated  November 8, 2003

