Microsoft Interview Question
Courtesy Wikipedia:
float fastsqrt(float val) {
int tmp = *(int *)&val;
tmp -= 1<<23; /* Remove last bit to not let it go to mantissa */
/* tmp is now an approximation to logbase2(val) */
tmp = tmp >> 1; /* divide by 2 */
tmp += 1<<29; /* add 64 to exponent: (e+127)/2 =(e/2)+63, */
/* that represents (e/2)-64 but we want e/2 */
return *(float *)&tmp;
}
Let the number be x who's square root we need.
Take a guess at the square root, let it be g.
while(1)
{
g = (1/2)(g + (x/g))
if(g*g == x)
return g;
}
add all the odd numbers till u get the number . the number of terms you added is the square root .
For eg.
1=1
4=1+3
9=1+3+5
16=1+3+5+8
One of the things that can be done is take the number n whose square root has to be determined. From range 1 to n/2 select a middle element, square it and compare with n.If it comes to be greater than the number n then look into the range 1 to n/4 else look into the range n/2 to n/4. This is kind of binary search and in this way we can determine the appx square root of a number in lg(n) time.
- gauravk.18 April 07, 2008