CareerCup

Newton Raphson method..

use binary search:

bool squareRoot(int n, int& ans){
if (n < 0)
return false;
int l = 0;
int r = n;
while (l<=r){
int mid = (l+r)/2;
int square = mid*mid;
if (square == n){
ans = mid;
return true;
}
else if (squre < n)
l = mid + 1;
else
r = mid - 1;
}
return false;
}

Can we do this
Pow( 2, .5*log2(n) ) ??

w w w.en.wikipedia.org/wiki/Newton's_method#Square_root_of_a_number

//! Implementation of Babylonian method for square root
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	long S = 125348;
	long tempS = S;
	long X0 = 1;
	float Xcurr, Xprev, diff;
	int numIterations = 0;
	int numBits = 0;
	//Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
	while(tempS>0){
		tempS=tempS>>1; //shift bits to find the closest 2^k to the given number
		++numBits;
	}
	numBits = floor(numBits/2)+1;
	while(numBits>0){
		X0=X0<<1;
		--numBits;
	}
		
	Xcurr = X0;
	do{
		Xprev = Xcurr;
		Xcurr = .5*(Xprev + (S/Xprev));
		numIterations++;
	}while((Xprev-Xcurr)>0.001);
	cout<< "Square Root of "<< S<< " is "<< Xcurr<<endl;
	cout<< "Number of iterations :" <<numIterations;
}

Sry guys i missed one more point, he asked me to truncate it upto 4 decimal points. i used 2 while loops as binary search algo ( one with cond low < high, and another with high-low > 0.0001). Not sure he satisfied with my sol.

Pls input ur thoughts if it can done in a better way. all the best

//Bisection method, the simplest way to compute any invertible function
float SquareRoot(float y,float accuracy){
float x0=0,x1=y,temp=0;
float f0=x0*x0-y; // initially <=0
float f1=x1*x1-y; // initially >=0
float f_temp=temp*temp-y;
while((f0*f0-accuracy*accuracy)>0 && (f1*f1-accuracy*accuracy)>0)
{
temp=(x0+x1)/2;
f_temp=temp*temp-y;
if(f_temp*f0>0)
{
x0=temp;
f0=f_temp;
}
else{
x1=temp;
f1=f_temp;

}
}
if((f0*f0)<(f1*f1))
return x0;
else
return x1;
}

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package careercup.google;

/**
*
* @author learner
*/
public class Squareroot {
private static final int Number = 160000;
private static final double tolerance = 0.0000001;

public static void main(String args[]){
System.out.println("sqrt of " + Number + " is " + sqrt(Number));
}

private static double sqrt(int number){
int count = 0;
double x = number;
double newx = 0.0;
do{
count += 1;
newx = 0.5 * (x + number/x);
if(Math.abs(x - newx) < tolerance){
System.out.println("total iterations : " + count);
return newx;
}
x = newx;
}while(true);
}
}

int main()
{
float n=0.09;
if (n < 0)
return false;
float l = 0;
float r = n;
while (l<=r){
int mid = (l+r)/2;
int square = mid*mid;
if (square == n){
ans = mid;
return true;
}
else if (squre < n)
l = mid + 0.1;
else
r = mid - 0.1;
}
return false;
}

I tried the code above, that doesn't work

Try this

void main()
{
        float x1,x2,n;
        printf("\n Enter a number ");
        scanf("%f",&n);
        x1 = n;
        x2=.5*(x1+n/x1);
        while((x1-x2)!=0)
        {
                x1=x2;
                x2=.5*(x1+n/x1);
                printf("\n x1= %f, x2= %f n/x1=%f",x1,x2,(n/x1));
        }
        printf("\n %f",x2);
}

NA

#include<stdio.h>
void main(){
long int n,i,sum=0,k=1,f=0;

printf("ENTER THE NUMBER");
scanf("%ld",&n);
while(1){
sum+=(2*k-1);
if(sum==n)
{
f=1;
break;
}
else if(sum>n)
break;
k++;
}

if(f==1)
printf("This Number is Square Number Square root is:%d",k);
else
printf("This Number is not a Square Number");

}

/// <summary>
/// Returns the closest square to a given integer
/// </summary>
/// <param name="n">The n.</param>
/// <returns>The closest square to a given integer</returns>
int ClosestSquare(int n)
{
for (int i = n/2; i > 0; i--)
{
if ((i * i) <= n)
{
return i;
}
}

return 0;
}

/// <summary>
/// Calculates sqrt of a number upto 4 decimals
/// </summary>
[TestMethod]
public void Sqrt()
{
double n = 10;

double result = ClosestSquare((int)n);
double r = n - (result*result);
double q = 2 * result;
double dec = 0.1;

while ((r != 0) && (dec > 0.00001))
{
n = r*100;

double nextQ = q*10 + 1;
int i = 1;

while (nextQ * i < n)
{
i++;
nextQ = q*10 + i;
}
i--;
r = n - (q * 10 + i) * i;
q = q*10 + 2*i;

result += i*dec;
dec /= 10;
}
}

just apply the newton raphson method :)
its easy
code
float getsquareroots(float num)
{
float x1;
float x2=0;
float prev;
x1=num/2;
if(x1*x1==num)
return x1;
prev=x1;
while(x1!=x2)
{
x1=prev;
x2=x1-(x1*x1-num)/(2*x1);
if(x2*x2==num)
return x2;
prev=x2;
}
return x2;
}

static void Main(string[] args)
{
int number = give any number here;
int num1 = 1;
int num2 = num1;
int square = 1;
while (square < number)
{
square = num1 * num2;
if (square == number)
{
Console.WriteLine(num1);
}
else if (square < number)
{
num1++;
num2 = num1;
continue;
}
else if (square > number)
Console.WriteLine("number not a square");
}
Console.ReadLine();
}

var sq = 81;

var num = 1;

var prod = num * num;
while (prod != sq) {
    num++;
    prod = num * num;
 
}
   alert(num);

var sq = 81;

var num = 1;

var prod = num * num;
while (prod != sq) {
    num++;
    prod = num * num;
 
}
   alert(num);

var sq = 81;

var num = 1;

var prod = num * num;
while (prod != sq) {
    num++;
    prod = num * num;
 
}
   alert(num);

var sq = 81;

var num = 1;

var prod = num * num;
while (prod != sq) {
    num++;
    prod = num * num;
 
}
   alert(num);