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)
If you know a better solution, PLEASE let me know.