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

Comments: