Bloomberg interview question
How to write the sqrt function using only +,-,*,/
Interview Answers
double step = 10000;
double result = 0;
while(1)
{
while(result*result < i)result+=step;
result-=step;
step/=2;
}
Approximating the sqrt of a number with at least 6 decimal places in python with binary search:
def sqrt(n):
max_err = 0.0000001
lo = 0.0
hi = float(n)
while 1:
mid = (lo + hi) / 2
err = (n / mid) - mid
if err > max_err:
lo = mid
elif err < -max_err:
hi = mid
else:
return mid
print sqrt(2)
You can optimize it by giving a better rough estimate for the starting value of "lo" and "hi" instead of 0.0 and n.
Newton's method, we are searching for the sqrt(S):
x^2 - S == 0
f(x) = x^2 - S
f'(x) = 2x
x(n+1) = x - (x^2 - S)/(2x) = (2x^2 - x^2 + S)/(2x) = (x^2 + S)/(2x) = 0.5 * (x + S/x)
def sqrt(n):
max_err = 0.0000001
guess = 1
while 1:
print guess
guess = 0.5 * (guess + n / guess)
err = (n / guess) - guess
if abs(err) < max_err:
return guess
def isqrt(n):
max_err = 1
guess = 1
while 1:
print guess
guess = (guess + n // guess) // 2
err = (n / guess) - guess
if abs(err) < max_err:
return guess
print sqrt(2)
print isqrt(66)
The newton method is used for integer square root (isqrt) too.
def sqrt(num):
x=num
while abs(x*x-num) > 0.000001:
x = 1/2*(x+num/x)
return x