|
|
To show why the square-root algorithm works we use the Proposition 1 below.
The algorithm merely implements for anan-1...a1a0 the decomposition shown on the right side of Equation (1). Let us see how the algorithm obtains
102nan2 which is the first term on the right side of Equation (1). The algorithm subtracts an2 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 a0 is obtained, the place value of the an2 that was first subtracted becomes (102)n = 102n. Similarly, the second number subtracted, namely, (10 × 2 × an + an-1)an-1, acquires palce value 102(n-1), the third number acquires place value 102(n-2), and so on. Then, adding up all the numbers subtracted in the algorithm gives the decomposition of (anan-1...a1a0)2 given by Proposition 1.
We have seen elsewhere that 119025 is a perfect square. What if we are looking for the square-root 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 square-root must be of the form
x = anan-1...a1a0.a-1a-2...a-k, say, up to the kth decimal place, and, so, equals
10-k(anan-1...a1a0a-1a-2...a-k).
Let n+k = m.
Rename ai as ak+i, i = n, n-1,...,2,1,0,-1,...,-k.
Then, x = 10-k(amam-1...akak-1...a0) and, from Proposition 1,
 .
This means that, in finding the square-root 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 square-root of (10kx)2. Therefore, the value of x which is the square-root of the given number is obtained up to k decimal digits by dividing the number obtained in the division process by 10k, 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 non-zero digit, then the square-root 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 square-root algorithm)
Let N be a number in decimal representation. The square-root of N is obtained by the following procedure.
(1) Beginning at the decimal point, parse N in groups Ai, 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
AnAn-1...A1A0 . A-1A-2...Ak-1A-k, where the left-most group An on the left of the decimal point and the right-most 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 an so that (an)2 is the largest square not exceeding An. Let Bn-1 be the number obtained by concatenating
(An - an2) with An-1. That is, Bn-1 = 100(An - an2) + An-1.
(3) For i = n-1 to -k, choose ai, being the largest single-digit number, so that ((10 × 2 × (an...ai+1) + ai)ai does not exceed Bi. Let Bi-1 = 100(Bi - ((10 × 2 × (an...ai+1) + ai)ai) + Ai-1.
(4) Then the square-root of N is anan-1...a1a0.a-1a-2...a-k, up to k decimal digits.
Observe that when N is an integer, Ai = 00, for i = -1 to -k. And when N is an integer that is a perfect square, Bi = 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
|
