• AVR Freaks

Old 'New' trick to compute square root

Author
maxwell
Super Member
  • Total Posts : 1510
  • Reward points : 0
  • Joined: 2003/11/07 12:35:27
  • Status: offline
2003/06/22 13:39:11 (permalink)
0

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


#1

10 Replies Related Threads

    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Old 'New' trick to compute square root 2003/06/30 13:02:26 (permalink)
    0

    A simple addition to this algorithm allows calculation of sqrt(N) to the nearest half integer, adding one bit to the resolution. For a proof of the original theorem and description of the new method, see this PDF file:



    Proof of theorem



    John N. Power


    POWER TECHNOLOGIES


    #2
    Guest
    Super Member
    • Total Posts : 80503
    • Reward points : 0
    • Joined: 2003/01/01 00:00:00
    • Location: 0
    • Status: online
    Old 'New' trick to compute square root 2003/07/15 01:37:30 (permalink)
    0

    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.


    #3
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Old 'New' trick to compute square root 2003/07/16 13:22:19 (permalink)
    0

    I should have posted this sooner, but there is a revised description of the algorithm in the new document giving the proof of the theorem. In particular, the last comparison should read "remainder <= k?" rather than "remainder < k?".

    The latest version of the proof was put up on July 1, 2003, and can be found here (same reference as earlier, newer PDF document):



    Proof of theorem .



    John N. Power


    POWER TECHNOLOGIES


    #4
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Old 'New' trick to compute square root 2003/07/28 12:29:00 (permalink)
    0

    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


    #5
    Guest
    Super Member
    • Total Posts : 80503
    • Reward points : 0
    • Joined: 2003/01/01 00:00:00
    • Location: 0
    • Status: online
    Old 'New' trick to compute square root 2003/07/29 01:07:32 (permalink)
    0

    This is monumental and most useful for industrial applications like flow rate and differential pressure where the square root is used frequently and accuracy too fits nicely.Thanks,John.


    #6
    Guest
    Super Member
    • Total Posts : 80503
    • Reward points : 0
    • Joined: 2003/01/01 00:00:00
    • Location: 0
    • Status: online
    Old 'New' trick to compute square root 2003/07/29 06:24:03 (permalink)
    0

    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?


    #7
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Old 'New' trick to compute square root 2003/07/30 13:45:50 (permalink)
    0

    > I don't know how to do that. Does this involve just

    > posting the link? If so, I have already done that in a

    > previous post. If it involves mailing the file, then this

    > might be a problem, given its size (121K). I'm open to

    > suggestions.




    I finally found the PICLIST and posted a message to it describing the work I did on this, along with the link, so disregard my comments above. It's now out there, where everyone can see it.



    John N. Power


    POWER TECHNOLOGIES


    #8
    supercat
    Starting Member
    • Total Posts : 43
    • Reward points : 0
    • Joined: 2003/11/07 12:36:47
    • Status: offline
    Old 'New' trick to compute square root 2003/07/31 11:14:23 (permalink)
    0

    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.


    #9
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Old 'New' trick to compute square root 2003/08/01 13:32:46 (permalink)
    0

    I posted the method I described basically because I had never seen it before and because I was not up to date with other methods for finding the square root. (My method is quite slow; to find the square root of 255 takes 6500 instruction cycles.) After posting the link to my paper on PICLIST, I received a reply from someone who had already written a much faster and somewhat shorter (30 words vs 47) routine that was based on an algorithm from a book. Since I don't have his permission, I won't post his link to his web page here, but if anyone wants it, send me email.

    The method he used sounds similar to that which was just described above; it is very similar to what I was taught in grade school for finding the square root of a decimal number.

    Now that I have entered the "square root contest", I feel compelled to try to improve on the fast routine mentioned above (The newer algorithm, different code).



    John N. Power


    POWER TECHNOLOGIES


    #10
    maxwell
    Super Member
    • Total Posts : 1510
    • Reward points : 0
    • Joined: 2003/11/07 12:35:27
    • Status: offline
    Old 'New' trick to compute square root 2003/10/24 14:15:09 (permalink)
    0

    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


    #11
    Jump to:
    © 2021 APG vNext Commercial Version 4.5