Square Root math Methods

One small (but slow) method of calculating SQRT(N):

Number = N ; Number to take square root of
SQRT = 0
K=1

Do While Number > 0
    Number = Number - K
    SQRT = SQRT + 1
    K = K + 2
End Do

Another fairly simple (but much faster) method of calculating sqrt(n): is the Newton method:

        s(i+1) = { s(i)*s(i) + p }/{ 2*s(i) }

Number = N ; input value
        ;-- we want to finish with s^2 approximately equal to N.
Do While (...?...)
        s = ( s*s + N ) / ( 2 * s ) ; the average of "s" and "N/s".
End Do

The Newton method requires a 8-bit into 16-bit division algorithm.

For more theory see

• Scott Dattalo's page on SQRT() theory http://www.dattalo.com/technical/theory/sqrt.html.
• Wikipedia: Methods of computing square roots
• Fixed-point routines including the square root function

If you want tested implementations for a particular processor, see:

• PIC: http://www.piclist.com/techref/microchip/math/sqrt/index.htm really fast implementations of the square root function. Versions for 8 bit, 16 bit, 32 bit, and floating point numbers.
• The Cypress M8 (PSoC) has fast multiply hardware but no hardware for SQRT() or divide. a fast 16x8 SQR() and DIV() by mrzee
• PICList post "Code efficient square root" Algorithm

PICList 2008 contributors: o List host: MIT, Site host massmind.org, Top posters @20080704 Apptech, Jinx, Xiaofan Chen, David VanHorn, Alan B. Pearce, Bob Axtell, William \Chops\ Westfield, Cedric Chang, Gerhard Fiedler, bean, * Page Editors: James Newton, David Cary, and YOU! * Roman Black of Black Robotics donates from sales of Linistep stepper controller kits. * Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters. * Monthly Subscribers: Shultz Electronics, Larry Williams, David VanHorn, Bryan Whitehouse, Timothy Weber, David Challis. Peter Todd. on-going support is MOST appreciated! * Contributors: Neil Narwani, David Cary, Elemer AM Nyiry, Philip J Taylor, Gus Calabrese of Omegadogs.com, Gautama Venegas, Patrick B. Murphy, William Chops Westfield, Peter Todd, Leslie Ellis

  .