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
sorry man i didnt take alot of programming classes. but i think using the half method will prolly work.
Late reply, but please Sir, could you program it? If not, please keep that derogatory sarcasm to yourself. kthnxbai
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.
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.
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.
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); output.print("Answer: " + theRoot); } }
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.
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 Answer: 2.23606797749979 I also did output.print(Math.sqrt(5, 0.5)); and the answer was the same.
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"); output.print("Answer: 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); output.print("Answer: " + current); } } } This seems to be the maximum accuracy that's allowed, given a reasonable runtime with huge numbers (like 2 000 000 000). 7 digits of accuracy seems to make the while loop go on indefinitely (I'm not sure why). The check value is calculated using the sqrt(x) = e^(ln x/2) formula, but the built-in Math.sqrt function of Java still returns more accurate values than both of these methods (in general, the sqrt function will return exact values for perfect squares, but the other two will give a result with a really long trailing decimal that'll round to the exact value).
