Interview Question
Country: United States
There might be better ways but you can approach in this manner. Kind of binary search approach.
If you know the range of number ie < 10000 or something. As the double is < 10000, its quareroot should be between 1 and 100. Find its mean, 50. Does the double lies between 1^2 and 50^2 or between 50^2 and 100^2. depending on that take the mean. Go on until you find the square root.
Below code will give sqrt with higher precision:
Mathematical Logic: b^2 = a;
2*b^2 = a + b^2;
b= (a + b^2)/(2*b);
Take starting point as b=1;
Code:
#include<iostream>
using namespace std;
int main(){
float x;
while(cin>>x){
float b=1,temp;
do{
temp=b;
b = 0.5*(b+(x/b));
}while(temp!=b);
cout<<b<<endl;
}
}
This will work with the binary search approach.
public class Sqrt {
private static final double precision = 0.00001;
/**
* @param args
*/
public static void main(String[] args) {
double number = 0.4923423423;
double min=0, max=0;
for (int i=0;;i++) {
double boundary = Math.pow(5, i);
if (number < boundary * boundary) {
min = max;
max = boundary;
break;
}
max = boundary;
}
System.out.println(getSqrt(number, min, max));
System.out.println(Math.sqrt(number));
}
private static double getSqrt(double num, double min, double max) {
double mid = (min + max)/2;
if (Math.abs(num - mid * mid) <= precision) {
return mid;
}
if (num < (mid * mid)) {
max = mid-precision;
} else if (num > (mid*mid)) {
min = mid+precision;
}
return getSqrt(num, min, max);
}
}
Bisection Method :
Suppose we have to find square root of n.
A = greatest number less than equals to n which is a perfect square = a*a
B = smallest number greater than n which is a perfect square = b*b
let square_root(n) = sr
}
- Anonymous September 20, 2012ABS = absolute value function