Square Root By Long Division 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
Square Root By Long Division  2014/08/11The other day on Twitter, Paul Salomon (@lostinrecursion) asked:
Good question. The answer is yes, and I solved it using a technique Paul didn't know:
Long DivisionSo let's start with the division problem, computing 999999 divided by 7. Apparently modern teaching doesn't use long division any more. Instead they use a thing called "chunking". In fact, "chunking" is nothing more than long division done with more guesses and less formality.
999999 = 700000 + 299999 We can see that laid out formally at right. That table then says that
9999999 / 7 = 100000 + 299999/7 We now iterate. We can remove 4 chunks of 7 from 29, so that's removing 40000 lots of 7 from 299999. Again, we lay that out in the tabular fashion:
So we are, at each stage, deciding what the next digit should be, multiply by 7, subtract from the remaining amount, and then repeat. This is laid out in a formal, tabular fashion. At each stage we have an intermediate sum that makes sense.
Here we can see that 999999 = 7 * 142800 + 399. At each stage we reduce the remainder, subtracting a chunk of 7s from it. Polynomial divisionThis can be used for polynomials too. So, for example, here we start:
The first term has to be multiplied by $x^2$ so we end up cancelling the $x^4,$ so the first term has to be $x^2.$ Multiply and subtract  the first term cancels:
We've magically vanished the $x^2$ term as well, although that will come back in a moment. We bring down the "8x" and ask what we need that will cancel the $2x^3$ term. Clearly that will have to be "2x", and so we continue ...
As you can see, we can divide $x^4x^33x^2+8x5$ by $x^2+x3$ and we get $x^22x+2$ with a remainder of 1. So we can perform long division with polynomials in exactly the same way as we can perform long division with numbers, and in effect, it's just a formalised way of doing "chunking." Square roots by Long DivisionSo, on to Square Roots By Long Division ... We do the same thing. We remove as much as we can from the leading portion, hang on to the remainder, and then carry on. At each stage we have an equation giving the current status. Let's compute the square root of 677329. We start by thinking of it as $67*10^4+7329.$ That means the square root will be 800 and a bit (because the square root of 67 is 8 and a bit, and the square root of $10^4$ is 100.) So $\sqrt{677329}$ is (800 and a bit). Let's put that in a table:
So, specifically, $677329=800^2+37329.$ Now let's go for the next phase. Drop the last two digits of 37329 to get 373. We computed the square root of 6773 as 80 and a bit, so we have $(80+x)^2=6400+2\times80\times{x}+x^2.$ We've already removed the 6400 to be left with 373, so we think of that 373 as the $(2\times80+x)\times{x}.$ We need to find a digit "d" such that "16d" (that's one hundred and sixtyd) times "d" is as big as possible, but no bigger than 373. In other words, find the maximum value of "d" such that $(160+d)\times{d}\leq{373}.$
The "16" at left in that table is twice 8. So we want a "d" such that "16d" times "d" is as close as possible to, but no bigger than, 373. Clearly the best value is "2". We insert the value "2", multiply, and subtract:
Now again, we double the answer so far (giving 164) and find a digit that we can put on the end, then multiply by, to get something as close as possible but no bigger than 4929.
So we need to the largest "d" such that $(1640+d)\times{d}\leq{4929}.$ Just looking at the first two digits gives us a first approximation. 16 goes into 49 three and a bit times, so let's try 3:
It goes exactly, the remainder is zero, and so we've computed our square root. Now let's do that with 2:
Here we are looking for the next digit. Our equation so far is that $\sqrt{2}=(1.4142+x)^2.$ We are part way, and we can see that $2=(1.4142)^2+0.00003836.$ We double the bit we have so far, multiply by 10, then find the digit to put on the end, multiply by, and get close to 0.00383600. So "28284x" times "x" has to be close to, but not exceed, 383600. The value for "x" has to be 1, and so we continue. Polynomial Square Roots by Long DivisionAnd so, back to the original question.
Remember, we double what we have so far, and then work out what the next term will be:
Whatever X is going to be, we have to get rid of the $2n^3$ term when we multiply by $2n^2,$ so there's only one option  X has to be n.
Double the answer so far, and work out what to extend by:
We can see that X has to be 1 and we get this:
.............. and there's no remainder. Therefore
And we're done. So, a final example. Let's take the square root of this:
Here it is ...
So:
and hence it's the difference of two squares. That means we have the factorisation:
or
Credits ...Hat tips to both Colin Beveridge (@icecolbeveridge) and James Tauber (@jtauber) for useful feedback and helpful suggestions while writing this.
CommentsI've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate. If the number of emails/comments gets too large to handle then I might return to a semiautomated system. That's looking increasingly unlikely.

Contents 
Links on this page


Quotation from Tim BernersLee 