Task: Calculate the Square Root of Double value in Java
The ideal way to calculate the value of square root is using Newton's Method, but from my experience, I can barely remember that formula, especially when you are in a tidy timed online contest, there will be no time to google much on this topic. So it comes to an end with a reasonable solution: Binary Search, or someone call it bisection.
When I have this code into test, the result we have is:
We can see the result is pretty good and close.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double left = 0.0; double right = Math.max(1.0, number); while(right - left > 10e-9) { double mid = (left + right) / 2.0; if (mid*mid > number) right = mid; else left = mid; } return left; } } |
When I have this code into test, the result we have is:
3.0 - > 1.7320508044213057
4.0 - > 2.0
9.0 - > 2.9999999972060323
16.0 - > 4.0
25.0 - > 4.999999998835847
We can see the result is pretty good and close.
However, the result is still far from our expectation.
The result:
Modification:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double left = 0.0; double right = Math.max(1.0, number); double prev = 0.0; double mid = (left + right) / 2.0; while(Math.abs(prev - mid) > 10e-9) { if (mid*mid > number) { right = mid; } else { left = mid; } prev = mid; mid = (left + right) / 2.0; } return mid; } } |
The result:
3.0 - > 1.7320508044213057
4.0 - > 2.0000000074505806
9.0 - > 2.9999999972060323
16.0 - > 4.000000007450581
25.0 - > 4.999999998835847
Observation:
One of the observation is if we divide N by a number greater than it's square root, we get a number that is less than it's square root. Conversely, if we divide N by a number less than it's square root we get a number greater than it's square root. And of course, dividing N by it's square root gives us it's square root. This means:Square_Root(81.0) = 9.0So after checking on the if mid^2 value is greater than N, or not, we always have our real square root between divider and quotation. So we can update the code slightly as below:
81 / 3 = 27
81 / 5 = 16.2
81 / 10 = 8.1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double left = 0.0; double right = Math.max(1.0, number); double prev = 0.0; double mid = (left + right) / 2.0; while(Math.abs(prev - mid) > 10e-9) { if (mid*mid > number) { right = mid; left = number / mid; // added this line. } else { left = mid; right = number / mid; // added this line. } prev = mid; mid = (left + right) / 2.0; } return mid; } } |
3.0 - > 1.7320508075688772As you can see, this result is perfect for our current precision (10e-9); We can leave precision here so far. But we can't just stop here, let's see if we can make our code more precisely.
4.0 - > 2.0
9.0 - > 3.0
16.0 - > 4.0
25.0 - > 5.0
Observation:
From above code, when we calculate the mid of left and right, we always use mid = (left + right) / 2.0, so for each case, we have:- mid * mid > number, mid = (left + right) / 2.0 = (number / mid + mid) / 2.0;
- mid * mid <= number, mid = (left + right) / 2.0 = (mid + number / mid ) / 2.0;
So, mid is always equal to (mid + number / mid) / 2.0;
Then we could have our code modified as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double mid = number; double prev = 0.0; while(Math.abs(prev - mid) > 10e-9) { prev = mid; mid = (mid + number / mid) / 2.0; } return mid; } } |
We could easily derive from our binary search.
No comments :
Post a Comment