CareerCup

A simple binary search method.

The idea is f(x) = x^2 is monotonically increasing function.

So to find sqrt of Y. We need to find an x such that x * x = Y.

We start with initial guesses 0 and Y and keep bisecting the range Y in which we know the sqrt cannot lie.

const double ERROR = 0.000000001;

double findsqrt( double t )
{
	double low = 0;
	double high = t;

	while ( (high-low)  > ERROR )
	{	
		double mid = ( low + high ) /  2.0;
		if ( (mid*mid) > t )
		{
			high = mid;
		}
		else
		{
			low = mid;
		}
	}
	return low;
}

Look for Newton–Raphson method

why we are taking double high = t; in place of double high = t/2;

the sum of a sequence of odd numbers gives you the sequence for the perfect squares
1=1
1+3=4
1+3+5=9
1+3+5+7=16

double target = 100;

double n = 0.001;

while (n*n < target) {
n += 0.001;
}

System.out.println(n);

double target = 100;

double n = 0.001;

while (n*n < target) {
n += 0.001;
}

System.out.println(n);

Java: [based on binary search method]

double FindSquareRoot(double n)
	{
		double sr;
		final double ERROR = 0.00001;
		return FindRootByBinarySearch(n, 0, n/2, ERROR);
	}

	double FindRootByBinarySearch(double n, double low, double high, double ERROR)
	{
		if ((high-low) < ERROR)
			return low;
		double mid = (high+low)/2;
		if ((mid*mid)>n)
			return FindRootByBinarySearch(n, low, mid, ERROR);
		else
			return FindRootByBinarySearch(n, mid, high, ERROR);
	}

Just code this algorithm
basic-mathematics.com/square-root-algorithm.html

The basic idea here is using Newton Raphson:
y = x^2

y' = 2x

x f(x) f'(x) x' = x - f(x)/f'(x)

we use x' to replace x in each iteration until the difference value is smaller than a constant (usually 0.0000001)

At last, we will get an approximate result for x (x = sqrt(y) )

Can be done in O(1) me thinks (for a range of inputs numbers for our application).

Use Taylor's polynomial theorem.

Find polynomial expansion of sqrt(1+x) about x=0.
For the required range of inputs, design the expansion to have degree K such that the error is within required precision for the range of inputs.

Now you have a polynomial p(x) of degree K to use for your application.
{{
sqrt(num)
{
// evaluate the special polynomial at x= num -1
// above can be done with O(K) operations. K is fixed.
return whatever you got ;
}
}}}

a