Square Root from Binary Search to Newton's Method

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.

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.

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.0
81 / 3 = 27
81 / 5 = 16.2
81 / 10 = 8.1

So 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:

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

Result:

3.0 - > 1.7320508075688772
4.0 - > 2.0
9.0 - > 3.0
16.0 - > 4.0
25.0 - > 5.0

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

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

The precision stays the same, but the code is much more precisely, and THIS IS Newton's Method.
We could easily derive from our binary search.