CareerCup

{double SquareRoot(int num) {
if(num == 0)
return 0;
if(num == 1)
return 1;

double guess = num/2, oldguess = 0;
while(guess != oldguess) {
oldguess = guess;
guess = (num/guess + guess)/2;
printf("%f %f\n", oldguess, guess);
}
return guess;
}}

guess will be never equal to oldguess!

It will be, after it crosses sufficient accuracy level

could someone explain the working ? seems greek to me .. :o

HANDRUN OF THE ABOVE ALGORITHM
For num = 4
guess = 2, oldguess = 0;
guess != oldguess = true
oldguess = 2;
guess = (2 + 2)/2;
printf( 2, 2);

For n= 16
guess = 8, oldguess = 0;
guess != oldguess = true
oldguess = 8
guess = (2+8)/2
printf( 8, 5);

guess != oldguess = true
oldguess = 5
guess = (3+5)/2
printf( 5, 4);

guess != oldguess = true
oldguess = 4
guess = (4+4)/2
printf( 4, 4);

There are several numerical techniques for the same, try the bisection method, or the newton raphson technique. There are many other more extensive techniques to approximate variety of functions.

Use Taylor expansion

use newton raphson technique to find the root of f(x)=x^2-num

The algorithm is fine, but how can you expect yourself to be able to figure out this super-smart algorithm during 10-20 minutes in the interview.

I guess any reasonable guessing algorithm will do the job for an interview question.

Here is my implemenation

double my_sqrt(int x)
{
double start;
double end;
double y;
double prec = 0.0001;

start = 0;
end = x;
y = x/2;

while(y*y < x-prec || y*y > x+prec)
{
if(y*y > x-prec && y*y < x+prec)
break;
else if(y*y > x+prec)
{
end = y;
y = (y+start)/2;
}
else
{
start = y;
y = (y+end)/2;
}
}
return y;
}

g^2=num
2g^2=num+g^2
g^2=num+g^2/2
g=((num/g)+g)/2