# What is the squareRoot of 5?

Discussion in 'School Work Help' started by spider-man, Jan 25, 2010.

1. ### spider-man Well-Known Member

466
55
1
Square Roots

Programming:

I was wondering if there is an algorithm for finding the square root of "x", where x is an element of the set of real numbers.

The squareRoot of "x" will result in a double.

I know there is a squareRoot method I can use, but I don't want to use it.

Give me some ideas.
-cool

#1
Last edited: Feb 23, 2010
2. ### iiimj4everiii Well-Known Member

211
241
0
sorry man i didnt take alot of programming classes. but i think using the half method will prolly work.

If not, please keep that derogatory sarcasm to yourself. kthnxbai

#4
4. ### jamesng63 Member

12
226
0
If you have a method to use, why not use it?

5. ### spider-man Well-Known Member

466
55
1

Just For Fun. lol

6. ### ♥♥♥GIGI♥♥♥ Member

6
26
0

Ok... That was unnecessary.

#8
Last edited: Feb 23, 2010
7. ### ♥♥♥GIGI♥♥♥ Member

6
26
0
Square root means finding the root of the equation, which is zero.

Hints: For input x = 5, first find the two integer values between 2.23606798, which is 2 and 3. 8. ### spider-man Well-Known Member

466
55
1

Interesting, that's why it's called "square root". lol

9. ### spider-man Well-Known Member

466
55
1
I almost got it, it doesn't seem to work for larger numbers.

#11
Last edited: Mar 12, 2010
10. ### xtirpation Active Member

32
234
0
Three choices. The first two are simple, the third one has some almost-correct c++ code involved.

1. Develop a Taylor Series fitting the square root. Decide how much accuracy you want beforehand, and just take the Taylor Series as far as you need to, of course, not doing an actual infinite sum.

2. Use the identity sqrt(x) = e^(ln x / 2). Computers typically have very fast algorithms for finding the natural/common logs, so efficiency is pretty good. You should note though, this is how most modern languages implement the square root function, so writing something like this would not be too different from actually calling the library function.

3. Are you familiar with a binary search? Try that sort of algoritm. For example

double mysqrt(double x) {
double upper;
double lower;
double now;
if (x < 1){
upper, now = 1;
lower = 0;
}else{
upper, now = x;
lower = 1;
}
while(abs(now * now - x) >= 0.0000001){ //The 0.0000001 is the level of accuracy this function will yield
if (now * now > x){
upper = now;
now = (now + lower / 2);
}else{
lower = now;
now = (now + upper / 2);
}
return now;
}//This operates in O(n) time

Try and understand the algorithm, don't just copy it.

11. wise words. wise words.

#13
12. ### spider-man Well-Known Member

466
55
1

I'll show you what I've written when I get home. I know that method. I think there is a delay when you enter a large number. So, I did binary search twice.

I did the method that Gigi said. For input 5, I found the two numbers 2 and 3 using binary search. Then I did a binary search between 2 and 3, and make the result toggle around 0.

It works for most of the numbers. I was testing to see what is the highest number that works, and those ones won't work.

#14
Last edited: Mar 12, 2010
13. ### spider-man Well-Known Member

466
55
1
This is my code  import java.io.PrintStream;
import java.util.Scanner;

public class SquareRoot
{
public static void main(String args[]){
PrintStream output = System.out;
Scanner input = new Scanner(System.in);

output.println("Enter: ");
int num = input.nextInt();
double min = 0;
double mid = 0;
double max = 0;
double squared = 0;
double total = 0;
boolean doIt = false;
double theRoot = 0;
//I want to do binary search for this part
for(int i = 0; i <= num; i++)
{
squared = (i * i);
total = squared - num;
if(total > 0){
max = i;
min = i - 1;
doIt = true;
i = num; //ends loop
}
else if(total == 0){
theRoot = i;
i = num; //ends loop
}
}

double iWantZero = 0.0;
int counter = 0;
while((doIt) && counter < 1500)
{
mid = (min + max)/(2.0);
iWantZero = (mid * mid)- num;
if(iWantZero < 0.0)
{
min = mid + 0.1;
}
else if (iWantZero > 0.0)
{
max = mid - 0.1;
}
else if (iWantZero == 0.0)
{
theRoot = mid;
doIt = true;
}
counter++;
theRoot = mid;
}
output.println("min: " + min + " and max: " + max);
}
}

14. ### xtirpation Active Member

32
234
0
Correct me if I'm wrong in understanding the code you wrote, but it seems to be that you're trying to find a range between which the square root lies, for example, between 1 and 2 for sqrt(2). The problem here is that you're using strict equivalencies to compare irrational numbers. In Java, there are only 15 digits of accuracy allowed. Most of the time (more often with larger numbers), the 15 digits of accuracy isn't enough to allow for the strict equivalency to be true. To fix this, usually we use the absolute value function (Math.abs in Java, if I recall correctly) and set a degree of accuracy that we want. For example, in the code I posted earlier, there would be (unless I counted the 0's wrong) 7 digits of accuracy; that's usually accurate enough for most things.

In any case, I'll try and post a rewritten version of your code later on

Edit: It looks like you want to output the min/max values for the square root, as well as a close answer to the root itself. The way you're doing it is sort of ... inefficient (no offense). While I was looking through your code, there seems to be a few things you're doing repeatedly. Firstly, you're declaring variables that are pretty unnecessary, such as squared, and total. These can be eliminated by changing your if conditions slightly. However, the benefit of using this extra memory space is that, if the numbers are very, very, very large (like if we weren't using doubles but longs instead) then saving a new variable may be more efficient than calculating the square of a number twice. But this usually isn't the case.

Secondly, I called your approach inefficient because you're using two loops to do the job of one. The first loop appears to try and find a range between which two integers the root falls (like I said above). The second loop uses a sort of binary search mechanism to narrow down decimal values, however, using an arbitrary 0.1 can (and often will) cause oscillation to occur. (Sorry, but I can't really pull together the words to explain what I mean by oscillation right now, I'll edit this again when I figure out a good example. Basically I mean that sometimes, you'll go above the root, then subtract 0.1, going below the root, then adding 0.1 again, putting you above the root, repeat, etc.)

Also, I don't really understand printing the min/max. This is probably an assignment requirement or something, but the fact of the matter is, you'll probably often get values like min = 1.41, max = 1.42 or something, which isn't too helpful, given that you're also calculating the root itself. Of course, if this is an assignment and that's the requirement, you'll have to print it, but otherwise, min/max are pretty useless to us.

#16
Last edited: Mar 13, 2010
15. ### spider-man Well-Known Member

466
55
1

I first made the square root of 2 into an equation, then I'm trying to find a number that makes the equation zero.

For the first loop, I searched for a number that is zero. It starts off as a negative number for the result in the loop.........then when it hits a positive number, I know the previous number of the loop is a negative.

Negative and positive consecutive integer have zero in between.

The second loop is a search. Trying to get even closer to zero. A binary search. I think this is right.

I'm not even in high school yet. lol

My output is:

Enter:
5
min: 2.336067977499784 and max: 2.1360679774997897

I also did output.print(Math.sqrt(5, 0.5));
and the answer was the same.

16. ### Woody Well-Known Member

213
41
0
Please don't say stupid. He worked hard on this.
-cool

#18
17. ### xtirpation Active Member

32
234
0
Alright, here's the code I promised.

import java.io.PrintStream;
import java.util.Scanner;
public class SquareRoot
{
public static void main(String args[]){
PrintStream output = System.out;
Scanner input = new Scanner(System.in);
output.println("Enter: ");
double num = input.nextDouble();
//First things first, if the number is negative, throw an exception
if (num < 0){
throw new IllegalArgumentException("The number was negative");
}else if (num == 0){//Putting in a special case for 0, since this is a known value, we might as well
//avoid the slight rounding error and just output 0
output.println("min: 0 and max: 0");
}else{
output.println("Check Value: " + Math.pow(Math.E, (Math.log(num)/2)));
double min;
double max;
if (num > 1){
min = 1;
max = num;
}else{
min = num;
max = 1;
}
double current = (min + max)/2;
while (Math.abs(current * current - num)>= 0.000001){
if (current * current > num){
//This would mean current is greater than the root
max = current;
current = (min + max)/2;
}else{
//This would mean current is less than the root, but not equal to the root
//Because if it were equal, this loop wouldn't even be entered
min = current;
current = (min + max)/2;
}
}//Eventually, this loop would quit when current is within 6 digits of accuracy to the root.
output.println("min: " + min + " and max: " + max);