Home

Compute integer square root without float operation

I am recently writing a graphics program, and I don't want float operations in my program. Unfortunately, I have to compute square root. Here is an implementation of the square root function, which equals to

      (int)sqrt(i).

The complete code listing is as below:


0001  int IntSqrt(int i)
0002  {
0003      int j,n;
0004  
0005      if (i==0) return 0;
0006  
0007      j = i;
0008      n = 0;
0009      while (j>>=2) 
0010          n++;
0011      j = 1<<n;
0012      
0013      while (n = ((i/j-j)>>1))
0014      {
0015          j += n;
0016          if (n == -1) break;
0017      }
0018      return j;
0019  }

Line 9~11 is to get a rough estimation. It makes use of the fact that the root of 2^a is 2^(a/2). Line 13~17 is to get an integer root as close as possible. (Newton's solution)

Version 2

This version is optimized and much more elegant than the previous version. k always holds the root. We don't have tricky check like `if (n == -1) break;' The iteration loop is very clear, and easier to understand.
#define ABS(a)  ((a) < 0 ? -(a) : (a))
int IntSqrt2(int i)
{
  int j=i,k=1;

  if (j & 0xffff0000) { k<<=8; j>>=16; }
  if (j & 0xff00) { k<<=4; j>>=8; }
  if (j & 0xf0) { k<<=2; j>>=4; }
  if (j & 0xc) { k<<=1; j>>=2; }

  do {
    j = k;
    k = (j + i/j)>>1;
  } while (ABS(j-k) > 1);
  return k;
}

If you know a better solution, PLEASE let me know.