# Calculating square root without sqrt

Page 1 of 1

## 12 Replies - 43341 Views - Last Post: 12 June 2009 - 04:49 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=109394&amp;s=4115227e09576dd2bc07f7e479c2c22c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 dejandenib

Reputation: 1
• Posts: 28
• Joined: 10-June 09

# Calculating square root without sqrt

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

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

Reputation: 78
• 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?

### #3 Dantheman

• D.I.C Regular

Reputation: 34
• 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.

### #4 dejandenib

Reputation: 1
• Posts: 28
• Joined: 10-June 09

## Re: Calculating square root without sqrt

Posted 10 June 2009 - 07:23 PM

I need a source code.

### #5 BlakeJustBlake

• D.I.C Regular

Reputation: 26
• 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.

### #6 Oler1s

• D.I.C Lover

Reputation: 1397
• 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.

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

### #7 Kanvus

• D.I.C Regular

Reputation: 42
• 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.

√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.

```#include <vector>

```

```/*
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

### #8 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: Calculating square root without sqrt

Posted 10 June 2009 - 09:09 PM

Nice write up....

### #9 Elcric

• D.I.C Regular

Reputation: 102
• Posts: 453
• Joined: 02-May 09

## Re: Calculating square root without sqrt

Posted 11 June 2009 - 04:06 AM

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

```

### #10 dejandenib

Reputation: 1
• 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

### #11 Kanvus

• D.I.C Regular

Reputation: 42
• 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.

### #12 rs4

Reputation: 29
• 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;
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
newEstimate = estimate- (estimate*estimate - n)/(2*estimate);
}
}

int main(){
double temp;
cin>>temp;
temp = sqroot(temp);
cout<<temp;
return 0;
}
```

Hope that helps, and made sense.

### #13 Kanvus

• D.I.C Regular

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

## Re: Calculating square root without sqrt

Posted 12 June 2009 - 04:49 AM

Brilliant...thanks