Problem description:

Given a number N, compute the square root.

Solution:

Alright, I know that every programming language has a built-in function to compute the square root of a number and of course that’s what you’re gonna use in a normal situation. But what if you are asked to solve this problem in a programming interview and you are not allowed to use any built-in function?

Well, to solve this problem we need to find a number which multiplied by itself becomes our given N, the simplest way to do it would be to loop from zero to N multiplying each number by itself and verifying if it equals N, but if we think about it for a while we realize we can do it much faster, how?… Binary Search!.

Let’s explain this algorithm with a basic example, let’s say we want to compute the square root of 9.

We have our range of possible square roots: 0 to 9

1.- The idea is to get the middle element in our range: 9 + 0 / 2 = 4.5

2.- multiply it by itself: 4.5 * 4.5 let’s call this new value P = 20.25

3.- verify if P equals N, if it does then we have found the square root of N, if not…

4.- Now we have two possibilities:

– P is greater than N: in this case we are gonna modify our range of possibilities because we know all numbers greater than 4.5 are not the square root, so now our range of possible square roots are between 0 and 4.5

– P is less than N: This is the opposite, so we would modify our lower bound instead of the upper bound.

We are going to repeat these steps until we find the square root of N.

Below you can find the code for this solution in Python.

#!/usr/bin/python -tt
import sys
def sqrt(n):
start = 0
end = n
m = 0
min_range = 0.0000000001;
while end - start > min_range:
m = (start + end) / 2.0;
pow2 = m * m
if abs(pow2 - n) <= min_range:
return m
elif pow2 < n:
start = m
else:
end = m
return m
def main():
for line in sys.stdin:
n = int(line)
print sqrt(n)
if __name__ == '__main__':
main()

### Like this:

Like Loading...

*Related*

Nice explanation.

Can you also implement a recursive implementation of the sqrt() function?

Also, I think your can add a level of recursion (or another loop iteration, in your approach) to check first if the upper bound is not the actual square root (or you can start by setting start = 0 and end = 2*n, this adds one more call, but still bounded by log(n)), because I think your program does a lot of computations to get the square root of 1 (edge case), and it will not get the exact root, even though 1 has an integer square root.