Wednesday, June 26, 2013

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.

No comments :