CareerCup

If you happen not to remember your Taylor series during the interview you can always fall back on a binary search.

public static double sqrt(double val) {
        double sqrt = val/Math.log(val);
        while(Math.abs(val - sqrt*sqrt) > TOLERANCE) {
            sqrt = (sqrt + val/sqrt)/2;
        }
        return Math.abs(sqrt);
    }

class SquareRoot{

    public static double root(double val, int decimalPts){
       int partInt = 0;
        while(square(partInt) < val){
            partInt ++;
        }
        if(square(partInt) == val)
            return partInt;
        partInt--;

        double[] precision = new double[decimalPts];
        double b = 0;
        double delta = 0.1;
        for(int i = 0; i < decimalPts; i++){
            while(square(partInt+b+precision[i]) < val){
                precision[i] += delta;
            }
            if(square(partInt+b+precision[i]) == val)
                return partInt+b+precision[i];
            precision[i] -= delta;
            b = b+precision[i];
            delta = delta*0.1;
        }
        return (partInt + b);
    }

    private static double square(double val){
        return (val*val);
    }

}

def newton_sqrt(a, precision=1e-32):
    if a < 0:
        raise ValueError(a)
    elif a == 0:
        return a
    x0 = a / 2.

    # Taylor series for f(x) = x**2
    # f(x) = f(x0 + (x - x0)) = f(x0) + (x - x0) * f'(x0) + O(x**2)
    # thus approximately a = f(x) = x0 ** 2 + 2 * x0 * (x - x0)
    # so 2 * x * x0 = a + x0 ** 2
    # x = (a / x0 + x0) / 2

    while True:
        next_x = (a / x0 + x0) / 2
        if abs(x0 - next_x) < precision:
            break
        x0 = next_x
    return next_x


def almost_equal(got, expected, precision=1e-17):
    assert abs(got - expected) <= precision, (got, expected)

assert newton_sqrt(0) == 0
try:
    newton_sqrt(-1)
except ValueError:
    pass
else:
    assert False
for a in [1, 4, 100, 1e8, 5, 17]:
    almost_equal(newton_sqrt(a), a ** 0.5)

void squareRoot(double num, double start, double end, double& value)
{
    if(!value)
    {
        if(num==1)
        {
            value = 1;
            return;
        }
        else if(num==4)
        {
            value = 2;
            return;
        }
        double mid = (start+end)/2;
        if(mid*mid == num)
        {
            value = mid;
            return;
        }
        else if(mid*mid > num)
            end = mid;
        else
            start = mid;
        squareRoot(num, start, end, value);
    }
}

Will add more code to handle decimal cases.

double root(double num){
        return Math.sqrt(num);
    }

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class SquareRoot {

public static int squareRoot ;
public static void main(String[] args) {
System.out.println(squareRoot(1009));
System.out.println(Math.sqrt(1009));
}

/*This method gives an approximation of square root
* Squareroot(number) = squareroot(nearest perfect square) + ( Difference between number and perfect square
* /(2*squareroot(nearest perfect square)))
* This formula has been derived using differentiation
*/
public static double squareRoot(int number){
int num = number;
while(!isPerfectSquare(num)){
num --;
}
double diff = number - (squareRoot*squareRoot);
double divisor = squareRoot*2;
return (squareRoot + (diff/divisor));
}

/*
* This method checks whether a number is a perfect square or not
*/
public static boolean isPerfectSquare(int number){
int quotient = number;
int divisor = 2;
int sqrt = 1;
Map<String, Integer> map = new HashMap<String, Integer>();
//Calculate the factors
while(quotient != 1){
if(quotient%divisor == 0){
quotient = quotient/divisor;
if(map.get(divisor+"") == null){
map.put(divisor+"",1);
}else{
int count = map.get(divisor+"");
map.put(divisor+"", ++count);
}
divisor = 2;
}else{
divisor++;
}
}
Iterator<String> it = map.keySet().iterator();
while(it.hasNext()){
String key = it.next();
int count = map.get(key);
Integer i = new Integer(key);
int k = 1;
for (int j = 0; j < count/2; j++) {
k *= i;
}
sqrt *= k;
if(count%2 != 0){
return false;
}
}
squareRoot = sqrt;
return true;
}
}

public static double sqrt(int number) {
double t;

double squareRoot = number / 2;

do {
t = squareRoot;
squareRoot = (t + (number / t)) / 2;
} while ((t - squareRoot) != 0);

return squareRoot;

public static double sqrt(int number) {
double t;

double squareRoot = number / 2;

do {
t = squareRoot;
squareRoot = (t + (number / t)) / 2;
} while ((t - squareRoot) != 0);

return squareRoot;

public static double sqrt(int number) {
double temp;

double squareRoot = number / 2;

do {
temp = squareRoot;
squareRoot = (temp + (number / t)) / 2;
} while ((temp - squareRoot) != 0);

return squareRoot;