Square Root By Long Division

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Subscribe!
@ColinTheMathmo

My latest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:

Square Root By Long Division - 2014/08/11

The 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:

  • Yes.
    If n is the second integer, the square root
    is $n^2+n-1.$ Interestingly, I used the algebraic
    version of square root by long division.

    • Show me your work will you? I don't think
      I know this algebraic square root business.

OK. If you're interested in the actual algorithm then simply skip to the end. However, I'm going to derive the algorithm, starting with long division.

Long Division

So 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.

 
      1
    +-------------
  7 | 9 9 9 9 9 9
      7
     ---
      2 9 9 9 9 9
So we start by ignoring everything except the most significant part. We ask how many 7s we can take out from the first digit. The answer is just one. So we have

 
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:

 
     1 4
   +-------------
 7 | 9 9 9 9 9 9
     7
    ---
     2 9 9 9 9 9
     2 8
    -----
       1 9 9 9 9

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.

 
     1 4 2 8 . .
   +-------------
 7 | 9 9 9 9 9 9
     7
    ---
     2 9 9 9 9 9
     2 8
    -----
       1 9 9 9 9
       1 4
      -----
         5 9 9 9
         5 6
        -----
           3 9 9

Here we can see that 999999 = 7 * 142800 + 399. At each stage we reduce the remainder, subtracting a chunk of 7s from it.

Polynomial division

This can be used for polynomials too. So, for example, here we start:

 
            +---------------------------
x^2 + x - 3 | x^4 - x^3 - 3x^2 + 8x - 5

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:

 
                           x^2
            +---------------------------
x^2 + x - 3 | x^4 - x^3 - 3x^2 + 8x - 5
              x^4 + x^3 - 3x^2
             ------------------
                  -2x^3 + 0x^2

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 ...

 
                           x^2 - 2x + 2
            +---------------------------
x^2 + x - 3 | x^4 - x^3 - 3x^2 + 8x - 5
              x^4 + x^3 - 3x^2
             ------------------
                  -2x^3        + 8x
                  -2x^3 - 2x^2 + 6x
                 -------------------
                        + 2x^2 + 2x - 5
                          2x^2 + 2x - 6
                     -------------------
                                      1

As you can see, we can divide $x^4-x^3-3x^2+8x-5$ by $x^2+x-3$ and we get $x^2-2x+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 Division

So, 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:

 
      8    .    .
  ,---------------
 v  6 7  7 3  2 9
    6 4
   -----
      3  7 3  2 9

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 sixty-d) 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}.$

 
         8    d    .
     ,---------------
    v  6 7  7 3  2 9
       6 4
      -----
16d      3  7 3

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:

 
        8    2    .
    ,---------------
   v  6 7  7 3  2 9
      6 4
     -----
        3  7 3
162     3  2 4
       --------
           4 9  2 9

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.

 
        8    2    d
    ,---------------
   v  6 7  7 3  2 9
      6 4
     -----
162     3  7 3
        3  2 4
       --------
           4 9  2 9
164d       ? ?  ? ?

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:

 
        8    2    3
    ,---------------
   v  6 7  7 3  2 9
      6 4
     -----
162     3  7 3
        3  2 4
       --------
           4 9  2 9
1643       4 9  2 9
          ----------
                  0

It goes exactly, the remainder is zero, and so we've computed our square root.

Now let's do that with 2:

 
       1 .   4    1    4    2
     ,-------------------------------
    v  2 . 0 0  0 0  0 0  0 0  0 0
       1
      ---
       1 . 0 0
2 4      . 9 6
      ---------
             4  0 0
2 8 1        2  8 1
            --------
             1  1 9  0 0
2 8 2 4      1  1 2  9 6
            -------------
                  6  0 4  0 0
2 8 2 8 2         5  6 5  6 4
                 -------------
                     3 8  3 6  0 0

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 Division

And so, back to the original question.

  • Is the product of 4 consecutive
    positive integers always one
    less than a square?

Let's take the product of 4 consecutive positive integers:

  • $(n-1)n(n+1)(n+2)=n^4+2n^3-n^2-2n$

Add one:

  • $(n-1)n(n+1)(n+2)+1=n^4+2n^3-n^2-2n+1$

And now we take the square root:

 
                         n^2
          ,---------------------------
         v  n^4 + 2n^3 - n^2 - 2n + 1
  n^2       n^4
           -----
              0 + 2n^3 - n^2

Remember, we double what we have so far, and then work out what the next term will be:

 
                             n^2 +  X
              ,---------------------------
             v  n^4 + 2n^3 - n^2 - 2n + 1
  n^2           n^4
               -----
  2n^2 + X        0 + 2n^3 - n^2

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.

 
                             n^2 +  n
              ,---------------------------
             v  n^4 + 2n^3 - n^2 - 2n + 1
  n^2           n^4
               -----
  2n^2 + n        0 + 2n^3 - n^2
                      2n^3 + n^2
                     ------------
                           -2n^2 - 2n + 1

Double the answer so far, and work out what to extend by:

 
                             n^2 +  n + X
              ,---------------------------
             v  n^4 + 2n^3 - n^2 - 2n + 1
  n^2           n^4
               -----
  2n^2 + n        0 + 2n^3 - n^2
                      2n^3 + n^2
                     ------------
  2n^2 + 2n + X            -2n^2 - 2n + 1

We can see that X has to be -1 and we get this:

 
                             n^2 +  n - 1
              ,---------------------------
             v  n^4 + 2n^3 - n^2 - 2n + 1
  n^2           n^4
               -----
  2n^2 + n        0 + 2n^3 - n^2
                      2n^3 + n^2
                     ------------
  2n^2 + 2n - 1            -2n^2 - 2n + 1
                           -2n^2 - 2n + 1
                          ----------------
                                        0

.............. and there's no remainder. Therefore

$\sqrt{n^4+2n^3-n^2-2n+1}\quad={\quad}n^2+n-1$

And we're done.

So, a final example. Let's take the square root of this:

 
 ,---------------------------------
v  4n^4 - 12n^3 - 11n^2 + 30n + 24

Here it is ...

 
                                2n^2 -  3n - 5
              ,---------------------------------
             v  4n^4 - 12n^3 - 11n^2 + 30n + 24
  2n^2          4n^4
               ------
                   0 - 12n^3 - 11n^2
  4n^2 - 3n          - 12n^3 +  9n^2
                  -------------------
                             - 20n^2 + 30n + 24
  4n^2 - 6n - 5              - 20n^2 + 30n + 25
                            --------------------
                                           -  1

So:

$4n^4-12n^3-11n^2+30n+24{\quad}={\quad}(2n^2-3n-5)^2-1$

and hence it's the difference of two squares. That means we have the factorisation:

$4n^4-12n^3-11n^2+30n+24{\quad}={\quad}(2n^2-3n-5+1)\times(2n^2-3n-5-1)$

or

$4n^4-12n^3-11n^2+30n+24{\quad}={\quad}(2n^2-3n-4)\times(2n^2-3n-6)$


Credits ...

Hat tips to both Colin Beveridge (@icecolbeveridge) and James Tauber (@jtauber) for useful feedback and helpful suggestions while writing this.


<<<< Prev <<<<
Beyond The Boundary
:
>>>> Next >>>>
On The Rack ...


You should follow me on twitter @ColinTheMathmo

Comments

I'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 semi-automated system. That's looking increasingly unlikely.


Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!