Square Roots (Contd...)

After waiting for a week, I found little response from readers. Perhaps you don't find square roots interesting enough to delve into, and may be you would like to handle bigger challenges. Anyway since I promised that I would explain the rationale behind the long division process of square roots sometime, so here in this post I discuss something about that.

It is pretty obvious (and not difficult to prove) that square of an 'n' digit number is either of (2n - 1) or (2n) digits. And reversing the logic, we see that the square root of a number of n digits is of [n/2] digits where the brackets [] represent the ceiling function. This simple fact explains the grouping by two digits while beginning the long division.

So assume that to find the square root of a given number 'a' (take as an example 121), we have grouped it by two digits (1, 21). Now the number of such groups gives us the number of digits in the final square root. And we find the digits of the square root one by one. First we guess the first digit which is simply the best guess for the square root of the number formed by the digits in first group (in our example, first group is 1, so the first digit in square root is 1).

Now assume that we have found k digits of the square roots (that means k groups of number 'a' have been consumed in the process). Let the number formed by the k digits of square root be x (in example x = 1). We have to find the next digit y. Taking this y together we have (k + 1) digits and the value of the square root is (10x + y). Square it up and we get:
(10x + y) * (10x + y) = 100xx + 20xy + yy = 100xx + (20x + y)y
= 100xx + (10*(2x) + y)y

Now out of this we already have consumed the 100xx of the dividend and we have to find y such that (10*(2x) + y)*y is nearest to the remainder left at that stage. Note this expression (10*(2x) + y) carefully. This is the same as putting a digit y after a number (2x). And we have to multiply this with y again to match the remainder. Thus we have the rule: if the quotient at each stage is x, then divisor is (2x) and we find a y such by placing y to the right of divisor (2x) and multiplying this number by y again, we get nearest to the remainder. If you actually work out the long division process you will see that this is what you do.

Let's work out the example where we want to find the square root of a = 121. We have two groups (1, 21) and so square root is of two digits. First digit x is 1, and remainder at this stage is a - 100xx = 121 - 100 = 21. The divisor at this stage become 2x i.e. 2 and we need to place a digit y after 2 (which makes it (20 + y)) and we need to multiply it with y so that we reach nearest to the remainder 21. Thus we need (20 + y)*y nearest to 21. Clearly y = 1, and the remainder becomes zero, so that 10x + y = 11 is the answer.

To illustrate using another example, let us take a = 12345 and after grouping we have (1, 23, 45), so we need three digits and first digit is x = 1. The divisor at next step is 2x i.e. 2 and we need y such that (10 * 2 + y)*y = 123 - 100*xx = 123 - 100 = 23. Clearly we need y = 1. and we get remainder 23 - 21 = 2. In the next step, quotient becomes x = 11 (two digits), divisor is 2x i.e. 22 and the remainder becomes 245. And we need to guess y such that (10 * 22 + y)*y = 245. Again y = 1. So the answer is 111.

The principles involved are as follows:

1. We get digits two by two from the dividend.
2. If quotient at any stage is x, the divisor at that stage is 2x.
3. In the next step we need to place a digit y to the right of divisor 2x and multiply it with y to get nearest to remainder i.e. (10 * 2x + y)y = remainder.

This is what we studied in school. The curious part in the above process is the fact that divisor is twice the quotient at any stage, and this is not quite obvious why it is so. After this post, I hope this will be obvious.

By the way, this long division method is not fast and in practice we use the Newton's method of finding square roots. This is quite easy. To find the square root of a we begin by an approximation x0 and improve upon it to get x1, then further x2, x3 and so on. The rule of improvement is:

x(n + 1) = (x(n) + a / x(n))/2

All operations need to be carried upto the number of decimals required. The beauty of this approach is that you can start from any positive value x0 and in 8-10 steps you will have a fairly good answer. I will leave it to the reader to figure out why this works.