Binary search for square root [homework]

Question

For an assignment I must create a method using a binary search to find the square root of an integer, and if it is not a square number, it should return an integer s such that s*s <= the number (so for 15 it would return 3). The code I have for it so far is

public class BinarySearch {

    /**
     * Integer square root Calculates the integer part of the square root of n,
     * i.e. integer s such that s*s <= n and (s+1)*(s+1) > n
     * requires n >= 0
     *
     * @param n number to find the square root of
     * @return integer part of its square root
     */
    private static int iSqrt(int n) {
        int l = 0;
        int r = n;
        int m = ((l + r + 1) / 2);

        // loop invariant
        while (Math.abs(m * m - n) > 0) {
            if ((m) * (m) > n) {
                r = m;
                m = ((l + r + 1) / 2);
            } else {
                l = m;
                m = ((l + r + 1) / 2);
            }
        }
        return m;
    }

    public static void main(String[] args) {
        //gets stuck
        System.out.println(iSqrt(15));
        //calculates correctly
        System.out.println(iSqrt(16));
    }
}

And this returns the right number for square numbers, but gets stick in an endless loop for other integers. I know that the problem lies in the while condition, but I can't work out what to put due to the gap between square numbers getting much bigger as the numbers get bigger (so i can't just put that the gap must be below a threshold). The exercise is about invariants if that helps at all (hence why it is set up in this way). Thank you.

Answer 1

Think about it: Math.abs(m*m-n) > 0 is always true non-square numbers, because it is never zero, and .abs cannot be negative. It is your loop condition, that's why the loop never ends.

Does this give you enough info to get you going?

Answer 2

You need to change the while (Math.abs(m * m - n) > 0) to allow for a margin of error, instead of requiring it be exactly equal to zero as you do right now.

Try while((m+1)*(m+1) <= n || n < m * m)

Answer 3

As Ken Bloom said you have to have an error marge, 1. I've tested this code and it runs as expected for 15. Also you'll need to use float's, I think this algorithm is not possible for int's (although I have no mathematical proof)

private static int iSqrt(int n){
float l = 0;
float r = n;
float m = ((l + r)/2);


while (Math.abs(m*m-n) > 0.1) {
    if ((m)*(m) > n) {
        r=m;
        System.out.println("r becomes: "+r);


    } else {
        l = m;
        System.out.println("l becomes: "+l);

    }
    m = ((l + r)/2);
    System.out.println("m becomes: "+m);
}

return (int)m;

}

Answer 4

#define EPSILON 0.0000001
double msqrt(double n){
    assert(n >= 0);
    if(n == 0 || n == 1){
       return n;
     }
    double low = 1, high = n; 
    double mid = (low+high)/2.0;
    while(abs(mid*mid - n) > EPSILON){
       mid = (low+high)/2.0;
       if(mid*mid < n){
          low = mid+1;
       }else{
          high = mid-1;
       }
     }
return mid;}

As you can see above , you should simply apply binary search (bisection method) and you can minimize Epsilon to get more accurate results but it will take more time to run. Edit: I have written code in c++ (sorry)