## 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