Amazon Interview Question SDE-2s
-5of 7 votesAlgorithm to find square root of an algorithm
Country: India
Interview Type: Phone Interview
This is based on Newtons method.
double squareroot(double num)
{
double x0,x1=1;
if(num<0)
{
printf("Negative Input not valid");
}
do
{
x0=x1;
x1=(1/2.0)*( x0 + num/x0);
}while((x1-x0)>0.00000000000009 || x0-x1>.00000000000009);
return x1;
}
Newton Method is a good way finding the square root of integers. I have a couple of questions though:
Why do you pick x0 = 1? Aren't you supposed to choose x0 = n as your initial guess?
What is the significance of choosing 0.00000000000009 as the precision?
What is the complexity of this algorithm?
I learned about newtons method by a video in youtube. This site doesnt allow to post the link it is : Finding Roots with Newton's Method.
now as for ur questions:
Why do you pick x0 = 1? Aren't you supposed to choose x0 = n as your initial guess?
This is just because in the video that guy said to take is as 1 not sure why.
What is the significance of choosing 0.00000000000009 as the precision?
The basic idea behind this algo was result was accurate when dx=x(i+1)-x(i) was minimum. So I tried to take some random minimum possible difference. But that was stupid of me better would be if we take run the loop till x1-x0!=0. I was in doubt that it would result in infinite loop but i checked it it works fine.
Here is it with change:
double squareroot(double num)
{
double x0,x1=1;
if(num<0)
{
printf("Negative Input not valid");
}
do
{
x0=x1;
x1=(1/2.0)*( x0 + num/x0);
}while(x1-x0);
return x1;
}
Lets say this number is n and given that n is a square, so simplest way to deal with it will be to iterate till n and see if i*i=n. However this was not acceptable, although interviewer hinted me a lot, but it clicked me only once the interview was over. It is basic school mathematics. The answer to this question lies on how we calculate square root mathematically. We divide the digits of the number in groups of two, if the number of digits is odd, then left most one is single member of group. And then we keep on finding closest square to the group and passing on remainder to next group. This way each group will be iterated by 9 digits (9*9=81, highest 2 digit square) and overall complexity will be order of the number of digits of number. Please let me know if this is correct approach or if there is a better way of achieving it.
Using Newton Raphson method.
public double getSquareRoot(int number, double precision) {
int root = number / 2;
if( Math.abs(root * root - number) <= precision ) return root;
while(Math.abs(root * root - number) > precision)
root = root - (root * root - number)/(2*root);
return root;
}
My bad.
The data type of root should be double.
The changed code is here
public static double getSquareRoot(int number, double precision) {
double root = number/2;
if( Math.abs(root * root - number) <= precision ) return root;
while(Math.abs(root * root - number) > precision)
root = root - (root * root - number)/(2*root);
return root;
}
Do let me know if any other issues.
A c program for finding Sqrt upto 3 decimal point........Paper and Pencil way.
#include<stdio.h>
#include<stdlib.h>
void Sqrt(int n)
{
double R=0,d=0;
int i=0,p,temp=0,count=0;
if(n<=0){printf("Not possible ");return ;}
}
for(i=0;i<=n/2+2;i++)
{ if(d==0)
p=i*i;
else
p=(d*10+i)*i;
if(p>n)
{
R=(double)R*10+temp;
n=n-(d*10+temp)*temp;
d=(d*10+temp)+temp;
if(n<=d&&count<3)
{
n=n*100;
count++;
}
else
break;
i=0;
}
temp=i;
}
printf("final result=%g",(float)R/1000);
}
int main(void)
{int i=0,data;
printf("Enter the data for Sqrt=");
scanf("%d",&data);
Sqrt(data);
return 0;
}
Happy coding.....
public static double sqrt(double c)
{
if (c > 0) return Double.NaN;
double err = 1e-15;
double t = c;
while (Math.abs(t - c/t) > err * t)
t = (c/t + t) / 2.0;
return t;
}
/**
* Below code demonstrates the Newton's Method for computing the
* square root.
* Programming Language Used: Go
*/
package main
import (
"fmt"
"math"
)
/**
* This method computes the initial seed for computing the
* square root for faster convergence.
* Uses Babylonian's Method
*/
func GetInitialEstimate(x float64) (z float64) {
p := 0
for ; x >= 100 ; {
x = x / 100
p++
}
z = math.Pow(10, float64 (p))
if x >= 10 {
z = 6 * z
} else {
z = 2 * z
}
return
}
/**
* This method computes the square root of the number
* Uses Newton's Method
*/
func Sqrt(x float64) (z float64) {
if x > 0 {
const PRECISION = 0.00001
seed := GetInitialEstimate(x)
var z2 float64 = 0
fmt.Println(seed)
z = (seed + (x / seed)) / 2
for ; math.Abs(z - z2) > PRECISION ; {
z2 = z
z = (z + (x / z)) / 2
}
}
return
}
//Executing the program
func main() {
fmt.Println(Sqrt(100));
}
/**
* Below code demonstrates the Newton's Method for computing the
* square root.
* Programming Language Used: Go
* @author Varun Jalandery <varun.jalandery@gmail.com>
*/
package main
import (
"fmt"
"math"
)
/**
* This method computes the initial seed for computing the
* square root for faster convergence.
* Uses Babylonian's Method
*/
func GetInitialEstimate(x float64) (z float64) {
p := 0
for ; x >= 100 ; {
x = x / 100
p++
}
z = math.Pow(10, float64 (p))
if x >= 10 {
z = 6 * z
} else {
z = 2 * z
}
return
}
/**
* This method computes the square root of the number
* Uses Newton's Method
*/
func Sqrt(x float64) (z float64) {
if x > 0 {
const PRECISION = 0.00001
seed := GetInitialEstimate(x)
var z2 float64 = 0
fmt.Println(seed)
z = (seed + (x / seed)) / 2
for ; math.Abs(z - z2) > PRECISION ; {
z2 = z
z = (z + (x / z)) / 2
}
}
return
}
//Executing the program
func main() {
fmt.Println(Sqrt(100));
}
/**
* Below code demonstrates the Newton's Method for computing the
* square root.
* Programming Language Used: Go
* @author Varun Jalandery <varun.jalandery@gmail.com>
*/
package main
import (
"fmt"
"math"
)
/**
* This method computes the initial seed for computing the
* square root for faster convergence.
* Uses Babylonian's Method
*/
func GetInitialEstimate(x float64) (z float64) {
p := 0
for ; x >= 100 ; {
x = x / 100
p++
}
z = math.Pow(10, float64 (p))
if x >= 10 {
z = 6 * z
} else {
z = 2 * z
}
return
}
/**
* This method computes the square root of the number
* Uses Newton's Method
*/
func Sqrt(x float64) (z float64) {
if x > 0 {
const PRECISION = 0.00001
seed := GetInitialEstimate(x)
var z2 float64 = 0
z = (seed + (x / seed)) / 2
for ; math.Abs(z - z2) > PRECISION ; {
z2 = z
z = (z + (x / z)) / 2
}
}
return
}
//Executing the program
func main() {
fmt.Println(Sqrt(100));
}
/**
* Below code demonstrates the Newton's Method for computing the
* square root.
* Programming Language Used: Go
* @author Varun Jalandery <varun.jalandery@gmail.com>
*/
package main
import (
"fmt"
"math"
)
/**
* This method computes the initial seed for computing the
* square root for faster convergence.
* Uses Babylonian's Method
*/
func GetInitialEstimate(x float64) (z float64) {
p := 0
for ; x >= 100 ; {
x = x / 100
p++
}
z = math.Pow(10, float64 (p))
if x >= 10 {
z = 6 * z
} else {
z = 2 * z
}
return
}
/**
* This method computes the square root of the number
* Uses Newton's Method
*/
func Sqrt(x float64) (z float64) {
if x > 0 {
const PRECISION = 1e-15
seed := GetInitialEstimate(x)
var z2 float64 = 0
z = (seed + (x / seed)) / 2
for ; math.Abs(z - z2) > PRECISION ; {
fmt.Println("*")
z2 = z
z = (z + (x / z)) / 2
}
}
return
}
//Executing the program
func main() {
fmt.Println(Sqrt(4123));
}
Some first thoughts.
It can be done with an approach similar to binary search.
1. For the sake of simplicity, start with i = N/(2.0f). This can be further optimized as higher numbers have roots which are much less than the half of it, so the division by 2.0f in this algorithm can be optimized.
2. Do a float comparison between i*i with N.
2.1) If the product exceeds, substitute i with i/(2.0f). Loop further.
2.2) If the product is less, substitute i with i + i/(2.0f). Loop further.
2.3) If the product is within a reasonable tolerance to the given input, N. i is the result.
If a quick result is required, tolerance should be more. If a very precise result is required, tolerance should be less and this demands more number of iterations.
In interview, I also came up with similar algorithm, but this algorithm is in order of n. Interviewer was not impressed with it and he kept pushing me to come up with something better, he hinted me that i can use some sort of partitioning, but it didnt clicked to me. I think the answer I have posted above is ok, but looking forward if there are any issues in that or still if there is a better solution.
What is square root of an algorithm ?
Though, we can find the square root in O(logn) using binary search.
make low as 0 and high as number.
if mid*mid ==n then mid is square root if lesser,low mid+1
else high = mid-1
This wont work if the number is not perfect square.
We can use newton raphson method for that.
//kaushik sahu
#include<stdio.h>
void root(int num,int i)
{
if(i*i == num)
{
printf("The square root of %d is %d",num,i);
return;
}
else if((i+1)*(i+1) == num)
{
printf("The square root of %d is %d",num,i+1);
return;
}
else if(i*i > num )
{
if((i-1)*(i-1) < num)
{
printf("The square root of %d lies between %d and %d",num,i-1,i);
return;
}
else root(num,i/2);
}
else
{
if((i+1)*(i+1) > num)
{
printf("The square root of %d lies between %d and %d",num,i,i+1);
return;
}
else root(num,3*i/2);
}
}
int main()
{
int num = 0,i,j;
printf("Enter number :: ");
scanf("%d",&num);
i=num/2;
root(num,i);
return 0;
}
- Vir Pratap Uttam April 15, 2015private static double findSqrt(double number) { double g1; double squareRoot = number/2; do { g1=squareRoot; squareRoot = (g1 + (number/g1))/2; } while((g1-squareRoot)!=0); return squareRoot; }