WAP to Calculate Square Root of Number Efficiently

It Seems to easy but people don't take care of algo & precision so why most of them don't able to implement these method & its asked in mostly core companies interviews

This Method is Known as Square root approximation - Babylonian method

Explanation
The basic idea is that if x is an overestimate to the square root of a non-negative real number S then S/x, will be an underestimate and so the average of these two numbers may reasonably be expected to provide a better approximation

It proceeds as follows:

1. Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
2. Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
3. Repeat step 2 until the desired accuracy is achieved.



#include

#include

double sqroot(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
int main()
{
printf( " %f ",sqroot(7));
}

Complexity is O(log2(n)) but if the closest 2^k number is found in constant time then complexity is O(log2log2(n))
TC O(logn)
SC O(1)
Run here http://codepad.org/jmmBxoZ4


2nd Method & Well Know Mostly Used Newton Rapson method

The Newton-Raphson method in one variable:

Given a function ƒ(x) and its derivative ƒ '(x), we begin with a first guess x0 for a root of the function. Provided the function is reasonably well-behaved a better approximation x1 is

x(n+1)=x0-f(x0,num)/f'(x0)

#include

#include

float f(float x,int n)
{
return(x*x-n);
}

float df(float x)
{
return 2*x;
}

int main()
{
float x0=3,x1,e=0.0001,num=7;
int i;

printf("\n Newton Raphson's Method : To find Square Root");

x1=(x0)-((f(x0,num))/df(x0));
printf(" %f ", x1);
i=1;
while(fabs(f(x1,num))>e)
{
x0=x1;
x1=(x0)-((f(x0,num))/df(x0));

printf("\n prev root=%f Square root of %f is %.2f",x0,num,x1);

}
}

Source http://en.citizendium.org/wiki/Newton's_method#Computational_complexity

Using Newton's method as described above, the time complexity of calculating a root of a function f(x) with n-digit precision, provided that a good initial approximation is known, is O((\log n) F(n)) where F(n) is the cost of calculating f(x)/f'(x)\, with n-digit precision.

However, depending on your precision requirements, you can do better:

If f(x) can be evaluated with variable precision, the algorithm can be improved. Because of the "self-correcting" nature of Newton's method, meaning that it is unaffected by small perturbations once it has reached the stage of quadratic convergence, it is only necessary to use m-digit precision at a step where the approximation has m-digit accuracy. Hence, the first iteration can be performed with a precision twice as high as the accuracy of x_0, the second iteration with a precision four times as high, and so on. If the precision levels are chosen suitably, only the final iteration requires f(x)/f'(x)\, to be evaluated at full n-digit precision. Provided that F(n) grows superlinearly, which is the case in practice, the cost of finding a root is therefore only O(F(n)), with a constant factor close to unit

TC O(logn)
SC O(1)
Run Here hhttp://codepad.org/mIrXDehk


Too Prove why ist log(n) you can try this simple example based on binary search 

import java.util.*;
public class SQRT
{
public static void main(String args[])
{
float n=7;
float y=sqrt(n);
System.out.println("sqrt is "+y);
}
static float sqrt(float n)
{
float low=0,high=n;
float mid=(low+high)/2;
while(Math.abs(mid*mid-n)>0.0000001)
{

if(mid*mid<n)
low=mid;
else if(mid*mid>n)
high=mid;
mid=(low+high)/2;

}