Old 'New' trick to compute square root

While I was reading a history of computing machinery recently, I came across an old technique for computing square roots which uses only subtraction. This was important in the days when adding machines and other "computers" were purely mechanical and could not perform multiplication or division.



Given a positive integer N, find sqrt(N).

Beginning with 1, subtract successive odd integers from N, counting the number of subtractions k, until the remainder is no longer greater than zero. If the remainder becomes zero, sqrt(N) = k. If the remainder changes sign from plus to minus, (k-1) < sqrt(N) < k.



Example: let N = 10.

k = 1: 10 - 1 = 9

k = 2: 9 - 3 = 6

k = 3: 6 - 5 = 1

k = 4: 1 - 7 = -6



==> 3 < sqrt(10) < 4



This method has the obvious shortcoming of only working with integers, but this can be circumvented somewhat by multiplying N by a perfect square and then dividing by its square root. To find sqrt(17.23), multiply by 100, find sqrt(1723), and divide the answer by 10. Using binary factors would probably be more convenient.



The other drawback is the large number of subtractions needed: sqrt(65536) requires 256 subtractions. A look-up table can shorten the process by bookmarking certain milestones (decades, e.g.). The sum of the first 10 odd integers is 100, the first 20 odd integers is 400, the first 30 is 900, etc. Comparing N with these milestones allows for shortening the chain of subtractions.



Example: find sqrt(1008)

Note that 1008 - 900 = 108

Therefore, sqrt(1008) = 30 + number of subtractions needed if you start on 108 with the 31st odd integer, which is 61, as a subtractor. This reduces the number of subtractions by 30. (Note the change from the original post.)



This method would never be used when mathematical precision is needed, but does provide a quick and dirty approximation to the square root when a full math package is not practical.



John N. Power


POWER TECHNOLOGIES

Very interesting, thanks for posting that tip. I've tried out the algorithm in VB and it seems to work perfectly, just need to make a PIC optimised version.

For completeness, I have written up a more thorough treatment of this square root algorithm, complete with sample PIC code and some hints for getting around the limitations of the method. The complete paper can be found at



http://www.bcpl.net/~jpower/ezsqrt.pdf



(121 K PDF download).



John N. Power


POWER TECHNOLOGIES

John, sorry I don't have time right now to review your opus. Perhaps you are willing to publish it at piclist.com so that others can more easily find and use it?

A somewhat better approach is to do a binary search for results, based upon the equality (A+B)^2 = A^2+2AB+B^2. If A, B, and A^2 are known and B is a power of two, then (A+B)^2 can be computed using only shifts and adds.



Using such techniques, a 32->16 square root can be computed using 16 iterations of a loop containing three adds, a single shift, a double-shift, a comparison, an assignment, and a test for zero. A 16->8 square root could be computed using 8 such iterations of a loop. I don't know if a square root can be made amenable to the "zipper logic" approach that works so well for division, but even if it can't the time required for this approach is hardly unreasonable.

I have finally completed a treatment of a modern fast algorithm for finding the square root of an integer. This will make a companion piece to the paper on the older method. It can be downloaded from: (102K download)



http://www.bcpl.net/~jpower/fastsqrt.pdf



John N. Power


POWER TECHNOLOGIES