So Sophie,

How do you find a square root without a calculator?

-Product of the American educational system

Hey Product,

o you really want to learn to find the square root of a number all by yourself or are you looking for a way to do your algebra homework without the calculator you left on the school bus last week and are too afraid to tell your parents you've lost? If the latter is the answer and you have a computer, the following java applet will figure it out for you:

function main()
{
var number;
var sqrt;
number=prompt("Please enter the number that you wish to find the square root of","?");
sqrt=Math.sqrt(number); ..... /* finds the square root of the number entered */
document.write("The square root of "+number+" is "+sqrt);
}

You can get answers to your algebra homework (they even show the work) at www.algebrahelp.com.

If you're not in school and are just a really poor product of the American educational system, as is your claim, you can think finding the square root of a number like this.

Here are a couple of algorithms that can be used to find the square root of a number.

Iterative Algorithm: Up until some time in the 1960's, school children were taught a really clever algorithm for taking the square root of an arbitrarily large number. The technique is quite similar to long division. Here's how it works for decimal square roots.

1. Starting at the decimal point pair off the digits.
2. Find the largest square that subtracts from the left-most pair and still yields a positive result. This is the remainder that will be used in the next step and note that it is only two (or one) digits. The square root of this largest square is the first digit of the square root of the whole number.
3. Concatenate the next pair of digits with the remainder.
4. Multiply the square root devloped so-far by 20. Note that the least significant digit is a zero.
5. The next digit in the square root is the one that satisfies the inequality: (20 * current + digit) * digit <= remainder where "current" is the current square root and "digit" is the next digit produced by the algorithm.
6. Form the new positive remainder by subtracting the left side of the equation in the previous step from the right side.
7. go to step 3

Binary Square Roots: In general, the procedure consists of taking the square root developed so far, appending 01 to it and subtracting it, properly shifted, from the current remainder. The 0 in 01 corresponds to mutliplying by 2; the 1 is a new trial bit. If the resulting remainder is positive, the new root bit developed is truly 1; if the remainder is negative, the new bit developed is 0 and the remainder must be restored (thus the name) by adding the quantity just subtracted.

The other method does not restore the subtraction if the result was negative. Instead, it appends a 11 to the root developed so far and on the next iteration it performs an addition. If the addition causes an overflow, then on the next iteration you go back to the subtraction mode. Before I botch the explanation much further, let me quote Flores again: As long as the remainder is negative, we proceed as in the previous section; we enter a 1 in the corresponding root bit being developed; we append 01 to this number; we shift it the correct number of times and subtract it from the previous remainder.

When the remainder goes negative, we do not restore as in the previous section. First we enter a 0 as the next root bit developed. To this we append 11. This result is shifted left the proper number of times and "added" to the present remainder.

Another Iterative Algorithm: Here's another iterative algorithm. It's something I did by brute force (I'm sure I wasn't the first...) before I knew about the above algorithm. After implementing code for each I discovered that the two algorithms are quite similar.

If you didn't know about the techniques described above, you'd probably be inclined to implement the square root routine like so:

unsigned char sqrt(unsigned int N)

In other words, x is built up one bit at a time, starting with the most significant bit. Then it is squared and compared to N. This algorithm works quite well for processors that have a multiply instruction. Unfortunately, the PIC doesn't fall into that category. However, it is possible to efficiently multiply a number by itself (i.e. square it).

There are several things to note in this expression:

1. The bits a-h can only be zero or one. So, a^2 == a.
2. If we are trying to build y iteratively by starting with a, then b, etc. then all of the least significant bits are assumed to be zero. Thus most of the terms do not need to be computed at each iteration.
3. The bit that is being squared is always multiplied by an even power of two.

If you follow the details of this last algorithm, you will notice that all of the arithmetic is being performed on bits 8-15 i.e. the most significant bits. The one exception is the very last iteration where s1 = 2^7. Another thing you will notice is that under certain situations, N will be larger than 2^16. But, it will never be larger than 2^17 - 1. This extra overflow bit can be handled with a relatively simple trick. Instead of shifting N one position to the left, roll N one position. The difference is that the most significant bit of N will get moved to the least significant position after the roll operation. (A simple shift zeroes the least significant bit.)

Note: I am not about to write all of this out for you because I am lazy, and math doesn't interest me as much as it does you. I pirated the algorithms above from www.dattalo.com/technical/theory/sqrt.html.