12 Replies - 32065 Views - Last Post: 12 June 2009 - 04:49 AM Rate Topic: -----

#1 dejandenib  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 10-June 09

Calculating square root without sqrt

Post icon  Posted 10 June 2009 - 05:29 PM

Can somebody help me with this. I need to calculate of a very big number with 1000 digits. I can't use sqrt because it wont fit in long long int. The input should be like this: First the number of digits, then the digits and output first the number of digits then the digits.
Input:
3
6
2
5
Output:
2
2
5
I know about finding the square root by hand procedure, but it's too hard for me to do it in a program. I used this code below but it's too slow and it't not for huge numbers.


#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;
}


*mod edit: added code tags: :code:

This post has been edited by NickDMax: 10 June 2009 - 06:56 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Calculating square root without sqrt

#2 apw5020  Icon User is offline

  • D.I.C Addict

Reputation: 78
  • View blog
  • Posts: 666
  • Joined: 26-March 09

Re: Calculating square root without sqrt

Posted 10 June 2009 - 05:38 PM

Don't forget to use the code tags.

Can you use the pow function? Will the number fit in that or will it run into the same problem?
Was This Post Helpful? 0
  • +
  • -

#3 Dantheman  Icon User is offline

  • D.I.C Regular

Reputation: 34
  • View blog
  • Posts: 445
  • Joined: 27-May 09

Re: Calculating square root without sqrt

Posted 10 June 2009 - 06:14 PM

http://lmgtfy.com/?q...ng+square+roots. There ya go.
Was This Post Helpful? 0
  • +
  • -

#4 dejandenib  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 10-June 09

Re: Calculating square root without sqrt

Posted 10 June 2009 - 07:23 PM

I need a source code.
Was This Post Helpful? 0
  • +
  • -

#5 BlakeJustBlake  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 26
  • View blog
  • Posts: 441
  • Joined: 15-February 09

Re: Calculating square root without sqrt

Posted 10 June 2009 - 07:25 PM

No one's going to give you source code.
Was This Post Helpful? 0
  • +
  • -

#6 Oler1s  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1395
  • View blog
  • Posts: 3,884
  • Joined: 04-June 09

Re: Calculating square root without sqrt

Posted 10 June 2009 - 07:52 PM

Quote

I need to calculate of a very big number with 1000 digits.
Hardware cannot store such a long number. Either you implement a software solution yourself, or look for a large number library. There's a few out there. Look under the names arbitrary precision library or large number library.

It's your task. You'll need to go and investigate yourself.

This post has been edited by Oler1s: 10 June 2009 - 07:53 PM

Was This Post Helpful? 0
  • +
  • -

#7 Kanvus  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 42
  • View blog
  • Posts: 452
  • Joined: 19-February 09

Re: Calculating square root without sqrt

Posted 10 June 2009 - 08:17 PM

Okay dude.

I pick a random number. √4892 ! Let's find the root of that. And then the same concept will work with 1000 digits, no problem.

Note: Decimals shown from here on are truncated for simplicity and will not be pinpoint accurate--maybe even off by a few. To fix, just add more decimal places when actually coding.


We must factor √4892 in the easiest way possible. How about this?

√489.2 * √10 (hmm...needs to be simpler.)
√48.92 * √10 * √10 (even more...)
√4.892 * √10 * √10 * √10 (looks good now!)

All of the above are the same, written differently. But now our target is small and pretty. Take a deeper look.

√4892 = 69.942
√4.892 = 2.21178 and √10 = 3.16227 alright?

So...

√4892 =

√4.892 * √10 * √10 * √10 is the same as
2.21178 * 3.16227 * 3.16227 * 3.16227 =

69.942


Don't be confused from this. All we did is turn the problem into a long multiplication equation. But the new obstacle is like you said, there's no room to store so many digits!

The concept to know here is BigInt. BigInt is usually mentioned when adding HUGE numbers together. Multiplying is the same thing, almost. All you need is a vector and some imagination.

Make a vector for your answer.
#include <vector>

vector<int> answer;





/*
  2.2
 x3.1
------
  2 2
6 6
------
6.8 2
*/

double temp = 6.82;

answer.push_back( (int)temp ); //Cast it so it only stores the 6! Use better way to cast.

//Find a way to just keep the leftover .8 and store it in another variable

/*Now...the next √10 is taken care of:

	 6( plus .8 from that temp )
 x3.1
--------
21.08


*/ 




The six you are now multplying with at the top is from the vector itself. The .8 is from the variable keeping track of leftover decimals. You keep them seperate to keep the vector with only ints.

When you end up with something like 21, which is 2 digits, carry the 2 over and add it to the next equation you will multiply--and store the 1 in the vector like we did to the 6.


Summary:

1) Break 'em down to many small roots of √10's and whatever is left( scientific notation form ), in this case, the √4.892

2) Multiply then store the first digit on the left of the . into your vector

3) Strip its decimals away and add it to the vector and times it by your next √10

4) Keep repeating until you run out of √10's to multiply to the growing vector. In this case, until your sum is near enough to 69.9428( accurate enough for your liking*see above Note about precision*)

5) Your vector will contain your answer when you're done so you'd have to cout it using a for loop to loop through its index. The answer will probably be backwards so do something to flip it around.


I understand very well that my explanation is nearly impossible to follow but this isn't an easy thing to digest. I've known many people who were given the task to design a BigInt class and never get it done, and that was just simple addition. Hopefully you at least know how to break your problem down now using factors of √10.

This post has been edited by Kanvus: 10 June 2009 - 08:27 PM

Was This Post Helpful? 0
  • +
  • -

#8 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Calculating square root without sqrt

Posted 10 June 2009 - 09:09 PM

Nice write up....
Was This Post Helpful? 0
  • +
  • -

#9 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 101
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Re: Calculating square root without sqrt

Posted 11 June 2009 - 04:06 AM

:D
Hello,

Try this one and see if it helps.

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

using namespace std;


float sqroot(float m)
{
	 float i = 0;
	 float x1;
	 float 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;
}


Was This Post Helpful? 0
  • +
  • -

#10 dejandenib  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 10-June 09

Re: Calculating square root without sqrt

Posted 11 June 2009 - 04:34 AM

i've already tried that and it is not efficient enough. It's very slow. I know how to calculate the square root myself, but it's hard for me to make a program to do it for me
Was This Post Helpful? 0
  • +
  • -

#11 Kanvus  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 42
  • View blog
  • Posts: 452
  • Joined: 19-February 09

Re: Calculating square root without sqrt

Posted 11 June 2009 - 04:37 AM

It caps off at about the ninth digit then shows 1514 for everything.
Was This Post Helpful? 0
  • +
  • -

#12 rs4  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 153
  • Joined: 01-February 09

Re: Calculating square root without sqrt

Posted 12 June 2009 - 04:36 AM

Newtons method for solving equations can be used to find square roots easily and quickly,
It state's x1 = x0 - f(x0)/f'(x0), where x0 is its initial estimate and x1 is its new estimate which will be closer to actual value.
Starting with n as starting no. and x as the answer
√n = x
So x^2 = n
f(x) = x^2 - n = 0
f'(x) = 2x

So in newtons method x1 = x0 - (x0 ^2 -n)/2x0
And in c++ that looks like this

#include <iostream>
using namespace std;
double sqroot(double n);

double sqroot(double n)
{
	double estimate;
	double newEstimate;
	newEstimate = n-1;
	estimate = n;//estimate can be made closer to expected value but the number to square will also work just needs to run a few more times
	for(int i =0;estimate != newEstimate && i !=20;i++){// i is only to stop cycling due to calculation errors in using doubles
		estimate = newEstimate;
		newEstimate = estimate- (estimate*estimate - n)/(2*estimate);
	}
return newEstimate;
}

int main(){
	double temp;
cout<<"Please enter no. to sqaure";
cin>>temp;
temp = sqroot(temp);
cout<<temp;
return 0;
}


Hope that helps, and made sense.
Was This Post Helpful? 1
  • +
  • -

#13 Kanvus  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 42
  • View blog
  • Posts: 452
  • Joined: 19-February 09

Re: Calculating square root without sqrt

Posted 12 June 2009 - 04:49 AM

Brilliant...thanks
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1