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.

Return to MathPages Main Menu