to find square root of a number

static unsigned mborg_isqrt3(unsigned long val)
{
  unsigned long temp, g=0, b = 0x8000, bshft = 15;
  do {
    if (val >= (temp = (((g<<1)+b)<<bshft--))) {
      g += b;
      val -= temp;
    }
  } while (b >>= 1);
  return g;
}

John

Hi ashu1004,

Most square root algorithms are based on long division and require a series of guesses.  Just as the links above demonstrate, a series of guesses determines the correct value for a given digit, a bit of simple math is performed, and the guessing mechanism is repeated for the next digit.  Usually, the guesswork is reduced to the point that each guess is instinctive, but programs will have to continue the guesswork, or be table driven to eliminate guessing.  (i.e.  You and I both just "know" that the square root of 49 is 7 and that the closest square root of 66 is 8.  For the computer program to "know" all of the square roots of two digit numbers, a 100 element table will have to be devised that contains the square roots.  Alternatively, the guessing game can be used to determine these values.)

As it turns out, determining square roots is easier if you're dealing with a binary number system.  No guesswork, just simple mathematics.  This is easy to see when you're dealing with a number that is a power of two (2, 4, 8, etc...)  Simply right shift the number halfway to the right.  (Shift bit-0 0 bits, bit-1 0 bits, bit-2 1 bit, bit-3 1 bit, bit-4, 2 bits, bit-5 2 bits, etc.)  Repeated application of this rule will allow you determine the square root of values that are not powers of 2.

First, let's look at a couple of perfect squares.

49 = 7*7.  The binary representation is 110001 = 111 * 111.

Working forward, 7*7 in binary is 111 * 111.  Performing all of the cross multiplication yields:

49 = 4*(4 + 2 + 1) + 2*(4 + 2 + 1) + 1*(4 + 2 + 1)  which further expands to:

49 = (4*4 + 4*2 + 4*1) + (2*4 + 2*2 + 2*1) + (1*4 + 1*2 + 1*1)

Similarly, 144 = 12*12.  The binary representation is 10010000 = 1100 * 1100.

Again working forward, 12*12 in binary is 1100 * 1100 and performing all of the cross multiplications yields:

144 = 8*(8 + 4) + 4*(8 + 4) which expands to:

144 = (8*8 + 8*4) + (4*8 + 4*4)


Examine both of these examples carefully.  You'll note that some of the terms are squares (n*n) and some are not (n*m).  The sum of the values in each term that is a square yields the square root.

49 = (4*4 + 4*2 + 4*1) + (2*4 + 2*2 + 2*1) + (1*4 + 1*2 + 1*1)
         4*4                     +            2*2            +                     1*1
7 =    4                         +            2               +                      1

144 = (8*8 + 8*4) + (4*8 + 4*4)
           8*8            +           4*4
12 =    8               +            4

This foundation is the basis for determing the square root of values that are not perfect squares.


Consider the value 156.  It's closest square root is 12.  We can derive the integral square root by using what we learned above.

156 = 10011100 = 128 + 16 + 8 + 4

128 >> 4 + 16 >> 2 + 8 >> 2 + 4 >> 1
   8          +      4      +      2        +    2

Clearly we're looking for a number between 12 and 13 so adding all of these values yeilds a number (16) that just can't be.  What's happened is that the decimal point should occur between the second and third digit.  By adding from left to right, we simply don't add any value that causes the sum to be larger than the integral square root.


The mathematics for determining the fractional portion of the square root is a bit more complicated, but very manageable.  The algorithm supplied by jobrienct appears to calculate the integral portion of a square root using the mathematics that I've described here.

Good Luck,
Kent

Another interesting way for integer square roots

Add up all the odd numbers from 1 while the sum is less than or equal to the number whose square root is being sought. The number of odd numbers needed is the square root.
For example, the integer square root of 23 = 4


1 + 3 + 5 + 7 = 16

1 + 3 + 5 + 7 + 9 = 25

Fast integer sqrt
long sqrt(r)
long r;
{
   long t,b,c=0;

   for (b=0x10000000;b!=0;b>>=2) {
      t = c + b;
      c >>= 1;
      if (t <= r) {
         r -= t;
         c += b;
      }
   }
   return(c);
}

But most of the times, you would be dealing with floats ... you can use one of the numerical analysis approaches (e.g. Newton's method), but they all take up some guessing
http://www.geocities.com/SiliconValley/Garage/3323/aat/a_sqrt.html

Some more methods
http://mathworld.wolfram.com/SquareRootAlgorithms.html