Square Roots by Pencil and Paper

At some stage in our schooling each of us was taught how to extract
square roots by "pencil and paper", using a method that vaguely
resembles "long division", but this method is almost never actually
used by anyone, presumably because (1) taking square roots is not a
very common operation in daily life, and (2) we have calculators 
(and before them, sliderules) to do the job much more easily and 
reliably, in the unlikely event that we ever actually need to compute
a square root.  Nevertheless, people still occasionally ask about 
this method, so here's a brief description of the longhand way of 
computing the square root of a large integer.  [Note that the ancient
Babylonian method of iterating on R => (R + N/R)/2 is quadratically
convergent, meaning that in the neighbrhood of convergence it doubles
the number of correct digits on each iteration, so it is far superior
to the grade school method, but this doesn't seem to diminish the
interest in the "manual" method.]

Working in the base B, an integer N is uniquely expressed by a 
sequence of digits n0,n1,n2,n3,... each in the range 0 to B-1, such 
that
          N  =  n0  +  n1 B  +  n2 B^2  +  n3 B^3  +  ...

If we take the digits two-at-a-time, we can also view this as an 
expression of the number in the base B^2, where each digit is in 
the range 0 to B^2 - 1, i.e.,

      N  =  [n0 + n1 B] + [n2 + n3 B] B^2 + ...

So, suppose we wish to compute the square root of the integer N.
If the square root of N equals R with the base-B expression

                R = r0 + r1 B + r2 B^2

then we have

          N  =  R^2  =  [r0 + r1 B + r2 B^2]^2

                     =  r0^2  +  2 r0 r1 B  +  2 r0 r2 B^2
                              +   r1^2 B^2  +  2 r1 r2 B^3
                                            +    r2^2 B^4

The first requirement is to select the digit r2 such that r2^2 B^4
is as large as possible while still being less than or equal to N.
The only possibilities for r2 are 0 to B-1, and we need only examine
the integer part of N/B^4.  This determines r2, leaving a remainder
of N - r2^2 B^4.  We can then determine the next digit of the square
root, r1, by finding the value in the range 0 to B-1 that makes the
quantity r1^2 B^2 + 2r1 r2 B^3 as large as possible without exceeding
the remainder.  Obviously if we consider only the remainder divided
by B^2 we need only deal with r1^2 + 2 r1 r2 B.  Once we have found
r1 we can proceed to find r0 in the range 0 to B-1 such that the
quantity r0^2 + 2r0 [r1 + r2 B] does not exceed the new remainder.
And so on.  Obviously this works for any base, and enables us to
determine the digits one-at-a-time by means of simple integer 
operations and comparisons.  It is particularly convenient when
working in the base B=2, since then the only possibilities for the
digits of the root at each stage are 0 and 1.

To illustrate the method with an example, suppose we want to compute
the square root of N = 30000000000 in base 10.  We would begin by 
taking the digits in pairs

               N = 3 00 00 00 00 00

The first digit of the square root is obviously 1, so we subtract
this to give the remainder and bring down the next two digits

               3 00 00 00 00 00
         1     1
              --------
               2 00

We want to choose the next digit r as large as possible such that
r^2 + 2r(10) doesn't exceed 200.  One way of doing this is just
to consider r(20+r) ~ 200, so r is roughly 200/(20+r).  We can see 
that r=7.  Another, more mechanical, approach is to simply step
through the possible values of r by subtracting from 200 the
quantities 21, 23, 25,....  After r of these subtractions we will
have subtracted 20r and (1+3+5+..+2r-1) = r^2.  Thus we have

          1   2   3   4   5   6   7
    200 -21 -23 -25 -27 -29 -31 -33 = 11

so the second digit of the square root is 7, making the first two
digits 17.

The remainder is 11, and we draw down the next two digits to make
1100.  The next digit r of the square root must be as large as
possible such that r^2 + 2r(170) doesn't exceed 1100.  Taking the
mechanical approach again, we have

              1     2     3
     1100 - 341 - 343 - 345  =  71

so the third digit of the square root is 3, making the first three
digits 173, with a remainder of 71.

Drawing down two more digits, we have the remainder 7100, and we
need r such r^2 + 2r(1730) doesn't exceed 7100.  We find

                  1      2
        7100 - 3461 - 3463  =  176

so the fourth digit is 2, making the first three digits 1732, with
a remainder of 176.

Drawing down two more digits into the remainder, we now seek r such
that r^2 + 2r(17320) doesn't exceed 17600.  Obviously this requires
r = 0, so the fifth digit of the square root is 0, with remainder
17600.

Drawing down two more digits, we have a remainder of 1760000, and
we need r such that r^2 + 2r(173200) doesn't exceed this remainder.
We have
                  1        2        3        4        5
  1760000 = -346401 - 346403 - 346405 - 346407 - 346409 = 27975

so the sixth digit of the square root is 5, making the first six
digits 173205, with remainder 27975.

Obviously we can continue drawing down more digits (past the decimal
point) to get more digits of the square root.  Also, notice that
after the first stage the subtractions are almost entirely due to
the 2r(MB) term, where M represents the digits found so far, and
B is the base, so we can estimate the next digit simply by dividing
the remainder by 2MB, and then checking to be sure r^2 + 2rMB
doesn't exceed the remainder.

For a discussion of more efficient root computation methods, see the
note Ancient Square Roots.