A summer program and resource for middle school students
showing high promise in mathematics

Useful Computational Methods

Square-root Algorithms

We consider only positive real numbers. Elsewhere it is discussed why the square root of a positive real number is taken as positive.

Square roots of rational and irrational numbers
It is known that the square root of an integer that is itself not the square of another integer will be irrational. For instance, 5 is not the square of an integer. So √5 is irrational. What if x is a real number that is not an integer? Then x is either rational or irrational. If x is rational, √x can be rational or irrational, depending on x. We will leave the easy proof of the following assertion to you: For a positive rational number x, √x is rational if and only if x = a/b, where a and b are squares of integers. Only one matter now remains: x irrational. But x irrational implies √x is irrational, for if √x is rational, the square of the rational will be rational and hence x will be rational, which would be a contradiction.

Finding the square root by a procedure similar to long division was popular prior to the advent of electronic calculators. Its distinguishing feature is that if the square root is rational, then the algorithm obtains the square root exactly and in a finite number of steps. Even for irrational square roots, at each step, the method finds a correct digit of the square root. This means, at the n-th step of using the method, the n-1 digits so far found are exact. Elsewhere we describe methods that obtain square roots by successive approximations. Before describing the long-division-like algorithm, we look at, perhaps, the easiest of all methods for finding square root by successive approximations.

Square roots by Divide-and-Average
This method dating back to the Babylonians (1700 B.C.) is known as the Babylonian Algorithm.
If A > 0 is a guess of the square root of the positive number Q, then a better approximation to √Q is given by
B = (A + Q/A)/2.
Now you use B as an approximation and compute C = (B + Q/B)/2, and so on to get as close as you want to the value of √Q. We have shown elsewhere why the Babylonian Algorithm works.

Let us find the square root of 5. Let A = 2.
Then B = (2 + 5/2)/2 = 2.25
C = (B + Q/B)/2 = (2.25 + 5/2.25)/2 = (2.25 + 2.22)/2 = 2.235
Notice that this value is getting closer with each iteration to the actual value 2.2360679...

You might wonder how one might even think of Q/A in connection with finding the square root of Q. Well, if A were indeed the square root of Q, then A2 = Q and so A = Q/A. And even if A is not the square root of Q so that A ¹ Q/A, it turns out that √Q lies strictly between A and Q/A, and their average B produces a shorter interval from B to Q/B within which √Q still lies and the average of B and Q/B produces an even shorter interval containing √Q, and so on.

The Long-Division-Type Square Root Algorithm
This is a calculation that can be performed using pencil and paper for finding the square roots of rational numbers - for large numbers, a calculator to carry out some multiplications would be convenient. It is not an approximation. We pick up the correct digits at each step. In these two features, it is different from the algorithms employing successive approximations.

Let N be a positive integer. Parse the digits of N in two's from right to left. For instance, the integer 47312 is parsed as 4,73,12 so that there are three groups, namely 4, 73, and 12. In general, suppose there are n+1 groups of digits in the parsing of N. Then the largest integer an whose square an2 will go into the left-most group is subtracted from the left-most group and an is written in the "quotient" row. The next group of two digits is brought down. Then we double an and choose the largest integer an-1 so that (10(2an) + an-1)an-1 does not exceed the "dividend." We subtract (10(2an) + an-1)an-1, the next group of two digits is brought down and the process repeats, as illustrated below in finding √1156.

Observe that 1156 must equal the sum of the remainder and all the numbers that have been subtracted from 1156. The remainder is 0. The numbers subtracted are 900 and 256. The 900 appears in the procedure as 9; but the place value of the 9 is 102.
342 = 1156 = 900 + 256 + 0
                = 102(32) + (10 × 2 × 3 + 4)4.
This is an illustration of the following:
For a two-digit integer a1a0 whose units digits is a0 and tens digit is a1,
(a1a0)2 =  (10a1 + a0)2
            = 102a12 + 2 (10 × a1 × a0) + a02
            = 102a12 + (10 × 2a1 + a0)a0.

To see if this procedure extends to integers with more digits, let us extract the square root of 119025 which is the square of 345.

119025 = (345)2 = (10)2(3)2 + 10(2(3)+ 4)4 + 10(2(34)+ 5)5 + 0.

What if we are looking for the square root of 119026? Then we have a remainder of 1 and so we think of 119026 as 119026.00 and bring down the two zeros and place a decimal point immediately after 345 in the "quotient" row. We look for the largest integer a-1 so that (10 × 2 × 345 + a-1)a-1 does not exceed 100. Since 0 is the only such integer, we place a 0 after the decimal point in the quotient row, and bring down a 00 so that we now ask what the largest integer a-2 is so that (10 × 2 × 6900 + a-2)a-2, and so on. This is llustrated below.

The algorithm works in the same manner for numbers that are not integers. Let us find the square root of 119026.742. We parse the number as 11,90,26.74,2. Here, instead of bring down a 00 after bringing down 26, we bring down 74 so that, with the remainder 1, we have 174 in the current bottom dividend row. We place a decimal point after 345 in the quotient row. We ask for the largest integer a-1 so that (10 × 2 × 345 + a-1)a-1 does not exceed 174. Since 0 is the only such integer, we place a 0 after the decimal point in the quotient row, and bring down the last group of digits in the original number. It is 20. We ask for the largest integer a-2 so that (10 × 2 × 3450 + a-2)a-2 does not exceed 17420. a-2 = 0. The quotient is now 345.00. We bring down a 00 and look for the largest integer a-3 so that (10 × 2 × 34500 + a-3)a-3 does not exceed 1742000. a-3 = 2, and the remainder is 1380004. We bring down another 00, and so on to the required precision.

Our Square-root Algorithm Display will take rational number inputs, which of'course includes the integers, and display all the steps as in the diagrams above.

If you find the parsing in two's strange, note that the long division essentially parses the digits of the dividend in ones!

Why the long-division-type square root algorithm works




Send suggestions to webmaster@mathpath.org
Copyright ã 2001- MathPath
Last updated - February 6, 2004