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
= 1: 10 - 1 = 9k
= 2: 9 - 3 = 6k
= 3: 6 - 5 = 1k
= 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. PowerPOWER TECHNOLOGIES