Square Root Algorithm Derivation

The Algorithm:

Use this algorithm to find the square root of any real number.

Step 1: Group the number in "twos" from the decimal place. (If you have a number with an odd number of digits, the group to the far left will only be a group of 1 digit.)

Step 2: Start with the first group of two (the group on the left). This group may be a group of only one number if your number has an odd number of digits. Find the greatest square less than or equal to that group of digits and its square root will be your first approximation of the entire square root.

Step 3: Subtract the current approximation squared and bring down the next group of numbers behind it. This is your next number to work with.

Step 4: Double the current approximation of the root.

Step 5: Find the "ones" digit of the doubled number that would result in a number which divides into the number you are currently working with- with the smallest possible remainder. This is the next number in your approximation of the square root.

Step 6: Multiply the "ones" digit by the doubled number plus the "ones" digit. Subtract this number from the number you are currently working with and bring down the next group of numbers behind it. This is your next group of numbers to work with.

Step 7: Repeat steps 4 through 6 until you get an approximation with an acceptable number of significant digits.

Diagram of Algorithm:

The Derivation:

The square root of a number, N, is the number, M, so that M2 = N. The square root algorithm is set up so that we take the square root of a number in the form of (X + R)2. The square root of this number is obviously (X + R). X represents the current approximation for the square root, and R represents the remainder of the number left over from the approximation. Our approximation will always be the correct square root of the number truncated (not rounded) to the number of digits in our approximation. If we expand our number (X + R)2 it will equal X2 + 2RX + R2. This gives us the basis for our derivation of the square root algorithm.

Step 1: The square root of a number between 1 and 100 is a number between 1 and 10. Furthermore, the square root of a number between 100 and 10000 is a number between 10 and 100. And so on. Therefore, if a number is divided into groups of two digits each from the decimal point to the left, the number of digits in the integer part of the square root of that number will be equal to the number of groups of figures.

Step 2: Only the first group of two (or one) digits determine the first digit of the square root. If the first two (or one) digits are a perfect square, then there is nothing left over and the process can be repeated on the next two digits of the number. This is usually not the case, which means there is a part of the first two (or one) digits which has not been accounted for and our approximation is not perfect. This leads into Step 3.

Step 3: Take the expanded value of our number: X2 + 2RX + R2. We subtract off the current approximation, X2, which results in 2RX + R2, the part of the original number which is not accounted for in our approximation. This gives us our next value to work with.

Step 4: Rewriting 2RX + R2 gives us R(2X + R). We see that our current approximation, X, must be doubled, resulting in 2X, which are the first digits of the number we will be working with.

Step 5: In order to find the next approximation, we need the R value. This number must divide into the next grouping with the smallest remainder, as shown by R(2X + R). (R obviously divides this number.)

Step 6: Since you've found an approximation based on this number, you must subtract of R(2X + R) so you take into account any remainder from your previous group of numbers.

Step 7: The procedure can be repeated as many times as necessary until either no remainder is found, meaning you have the actual square root, or until an acceptable number of decimal places are estimated.

Diagram of Derivation: