Finding Square Root without using sqrt()

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 5091 Views - Last Post: 05 August 2012 - 09:39 AM

#1 born2c0de   User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 187
  • View blog
  • Posts: 4,673
  • Joined: 26-November 04

Finding Square Root without using sqrt()

Posted 20 August 2005 - 07:23 AM

Description: This code shows how to find out the square root of a number without using the sqrt() function. The result obtained by both functions are the same and hence can also be used as an alternative sqrt() function.
/*          Code written by Sanchit Karve
                  A.K.A born2c0de
                  Contact Me at born2c0de AT hotmail.com

                  20 August, 2005

*/




#include <iostream>
#include <math.h>

using namespace std;


float sqroot(float m)
{
     float i=0;
   float x1,x2;
   while( (i*i) <= m )
          i+=0.1;
   x1=i;
   for(int j=0;j<10;j++)
   {
        x2=m;
      x2/=x1;
      x2+=x1;
      x2/=2;
      x1=x2;
   }
   return x2;
}

int main()
{
   cout<<"Enter a Number:";
   int no;
   cin>>no;
     cout<<"Square Root using sqroot()= "<<sqroot(no)<<endl
       <<"Square Root using sqrt()  = "<<sqrt(no);

   return 0;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Finding Square Root without using sqrt()

#2 bodom658   User is offline

  • Villiage Idiom
  • member icon

Reputation: 114
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Re: Finding Square Root without using sqrt()

Posted 05 March 2008 - 06:21 PM

very cool! thanks for sharing!
Was This Post Helpful? 0
  • +
  • -

#3 mikeblas   User is offline

  • D.I.C Regular
  • member icon

Reputation: 44
  • View blog
  • Posts: 390
  • Joined: 08-February 08

Re: Finding Square Root without using sqrt()

Posted 20 April 2008 - 10:25 AM

I suppose this method kind of works, but, WOW, is it slow! You start at 0, then multiply 0*0 to find that it's less than m. Then, you add 0.1, multiplying that times itself -- you get 0.01, and it's still less than m. You keep adding 0.1 to your candidate root until it's greater than m when squared... then use that as your starting point for ten iterations of approximation. What if m is 750,000,000 ? It will take you more than 270,000 multiplications to find the answer.
Was This Post Helpful? 0
  • +
  • -

#4 born2c0de   User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 187
  • View blog
  • Posts: 4,673
  • Joined: 26-November 04

Re: Finding Square Root without using sqrt()

Posted 21 April 2008 - 01:23 AM

Yes, it will. It uses a method of approximations and has that limitation. All approximation algorithms have that property, including Newton Raphson's, Runge Kutta's etc.
Was This Post Helpful? 0
  • +
  • -

#5 trbot   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 0
  • Joined: 10-June 08

Re: Finding Square Root without using sqrt()

Posted 10 June 2008 - 08:32 AM

I suspect this method would gain much, in the processing of large numbers, by taking a page from the book of binary algorithms. If, instead of adding 0.1 each time, you added 0.1, 0.2, 0.4, 0.8, 1.6, doubling each time, and then, after exceeding m, subtracted half of the largest value originally added, halfing this value and subtracting successively until you are below m, halfing it and adding until you are above m, ..., you can iteratively narrow the margin of error until (i*i - m < 0.1) to come up with the same result in a O(log n) algorithm. For small numbers there will be some overhead (to avoid this, use an if statement to select the appropriate algorithm based on a threshold), but for big numbers, you will cut running-time significantly. m = 750,000,000 would originally take 273,862 add/mult over lines 22 and 23. With the algorithm I have described, it will take 68 add, 34 mult/div.
Was This Post Helpful? 0
  • +
  • -

#6 phauline   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 0
  • Joined: 02-September 08

Re: Finding Square Root without using sqrt()

Posted 01 September 2008 - 11:55 PM

excellent!
Was This Post Helpful? 0
  • +
  • -

#7 David W   User is offline

  • DIC supporter
  • member icon

Reputation: 298
  • View blog
  • Posts: 1,839
  • Joined: 20-September 08

Re: Finding Square Root without using sqrt()

Posted 07 October 2008 - 12:54 AM

very inaccurate for values from 0 to 0.000001
Was This Post Helpful? 0
  • +
  • -

#8 GravityGuy   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 48
  • Joined: 21-January 08

Re: Finding Square Root without using sqrt()

Posted 30 October 2008 - 11:25 PM

A very nice little square root finder is this one. It converges quadratically, meaning, the number of correct digits doubles with each iteration. #include #include #include #include using std::setprecision; double heronsqrt(double val) { int dig=0; int n = (int) val; while((n >>= 1) > 0) // count binary digits dig++; n = 2 << (dig >> 1); // initialize at 2^(D/2) double err; double x = n; do { err = x; x = (x + val/x ) /2; std::cout << x << "\n"; std::cin.get(); }while(fabs(err-x) > 0.000000001); return x; } int main (int argc, char * const argv[]) { double dnum; char* strPt; if(argc == 1) dnum = 196.0; else dnum = strtod(argv[1],&strPt); std::cout << setprecision(16); double sqrtN = heronsqrt(dnum); std::cout << "Sqrt(" << dnum << ") = " << sqrtN << "\n"; return 0; }
Was This Post Helpful? 0
  • +
  • -

#9 GravityGuy   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 48
  • Joined: 21-January 08

Re: Finding Square Root without using sqrt()

Posted 30 October 2008 - 11:26 PM

Let's try that again...
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
using std::setprecision;

double heronsqrt(double val)  {
	
	int dig=0;
	int n = (int) val;
	while((n >>= 1) > 0)		// count binary digits
		dig++;
	n = 2 << (dig >> 1);	// initialize at 2^(D/2)
	double err;
	double x = n;
	do {
		err = x;
		x = (x + val/x ) /2;
		std::cout << x << "n";
		std::cin.get();
	}while(fabs(err-x) > 0.000000001);
	
	return x;
}
int main (int argc, char * const argv[]) {
    
	double dnum;
	char* strPt;
	
	if(argc == 1) dnum = 196.0;
	else
		dnum = strtod(argv[1],&strPt);
	std::cout << setprecision(16);	
	double sqrtN = heronsqrt(dnum);

    std::cout << "Sqrt(" << dnum << ") = " << sqrtN << "n";
    return 0;
}


Was This Post Helpful? 0
  • +
  • -

#10 GravityGuy   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 48
  • Joined: 21-January 08

Re: Finding Square Root without using sqrt()

Posted 30 October 2008 - 11:27 PM

Ok, I guess it only takes comments here.
Was This Post Helpful? 0
  • +
  • -

#11 insane elite nz   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 28-November 08

Re: Finding Square Root without using sqrt()

Posted 07 December 2008 - 10:31 PM

since (X^(1/2)) == the 2nd root of X^1(the squared root), would it be possable to use a pow function to get the square root instead of guessing and checking. I think you can also get the 3rd, fourth... roots from this to by replacing X^(1/2) by X^(1/3) etc...
Was This Post Helpful? 0
  • +
  • -

#12 Guest_*


Reputation:

Re: Finding Square Root without using sqrt()

Posted 08 December 2008 - 10:39 PM

very good
Was This Post Helpful? 0

#13 HEDGE.c   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 05-December 08

Re: Finding Square Root without using sqrt()

Posted 15 February 2009 - 12:40 AM

dude need help in other programs..
Was This Post Helpful? 0
  • +
  • -

#14 abhikural   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 16-January 09

Re: Finding Square Root without using sqrt()

Posted 17 February 2009 - 01:32 AM

#include #include void main() { int a,count=1,j=2,y,q=1; char ch; clrscr(); cout<<"Do u want to calculate"; cin>>ch; while(ch=='y') { cout<<"Enter number whose square root u want to calculate"; cin>>a; count=1,j=2,q=1; while(a>1) { while(a%j==0) { a=a/j; y=a%j; count=count*j; if(count>j) { q=q*count/j; count=1; } } j++; count=1; } cout<<"sqrt ="<>ch; } getch(); } hi ,,,,copy this code,,,it will surely calculate the square root..... For help:- +919463660234.....Abhishek Sharma(Punjab,khanna)
Was This Post Helpful? 0
  • +
  • -

#15 deraj162   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 0
  • Joined: 17-February 09

Re: Finding Square Root without using sqrt()

Posted 17 February 2009 - 07:49 AM

There is a much easier way to type in this function, but my way is slightly inaccurate. Here is the function: double sqroot(double a) { long double b=1; for(int i=0;i<30000;i++) b=b/2+a/b/2; return b; }
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2