SQUARE ROOT OF A NUMBER without using square root sign or any built in function - 2 methods

Recently, in an interview I was asked one simple question. How will you find a square root of  a number without  any built in function ?

I fumbled, but recovered well. Finally, I figured out two approaches. First one was Newton's method of finding the square root and second one was the one I had read during my graduation.

Method 1 (Newton's Method):

Algorithm :

We will assume square root to be s. 

s is less than square root of x (number whose square root we want to find) and x/s (Nuumber/Squareroot calculated in iterations) is greater than square root of x. Averaging these two (till the answer comes the same in two iterations) will give us the answer.

Program (C/C++/C#):

float sqrt(int x)

{

        int prev,k = 0;

        int kmax = 1000;

        float s = 1;

        for(k=0;k<kmax;k++)

        {

                prev = s;

                s = (s + x/s)/2;

                if(prev == s)

                {

                        break;

                }

        }

        return s;

}

Example :

let’s compute the square root of 9.

1. First Iteration

x = 9

k=0

s=1

prev=1

s = (1+9/1)/2 = 5

is(prev == s) -> No

2. Second Iteration

x = 9

k=1

prev=5

s=(5+9/5)/2 = 3.4

is(prev == s) -> No

3. Third Iteration

x = 9
k=2
prev=3(as it is int)
s=(3.4+9/3.4)/2 = 3.023 (This will be equal to 3 eventually)




is(prev == s) -> Yes

Stop...

Method 2 : 

This approach deals with finding a number which multiplied by itself becomes our given N(The number whose square root we want to find).The simplest way to do it would be to loop from zero to N(Number) multiplying each number by itself and verifying if it equals N.  
if we think about it for a while we  realize we can do it much faster, how?… Binary Search!.

Algorithm (Calculating 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(Actual Number i.e 9), 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 will 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. 4.5 to N(i.e 9 in this case)

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

Program (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()

Although we have built in functions to find out square root, This problem was not only a 

good brain exercise but also tested my logical skills.

I hope to come up with few more such interesting problems (this time before appearing for 
my next interview).