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:

See also:

• https://numberworld.blogspot.com/2013/08/the-magic-constant-0x5f3759df.html Inverse Square Root approximation via Newton in ONE iteration using "magic"

   float InvSqrt (float x) {
     float xhalf = 0.5f*x;
     long i = *(long*)&x;
     i = 0x5F83759DF - (i>>1);  //initial guess of inv-sqr
     x = *(float*)&i;
     x = x*(1.5f-xhalf*x*x);    //one step of newton iteration
     return x;
   }
  

  +