Perfect Squares and ℤ/ℝ Square Roots

This post will explore how the binary search algorithm can help us check if a given number is a perfect square, find the integer square root of a given number, and find the real square root of a given number efficiently relative to linear search.

Perfect Squares

A perfect square is a number that can be expressed as the product of two equal integers. For example, the numbers 4, 9, and 121 are perfect squares because they are the products of 22, 32, and 112 respectively.

Example

#   Current Search Range    m
#   1       5       9
#   i       m       j       1 + (9 - 1)/2 = 5
#   1       2       4
#   i       m       j       1 + (4 - 1)/2 = 2
#   3               4
#   im              j       3 + (4 - 3)/2 = 3
#   done because 3 * 3 = 9
#   return m

Implementation

public static boolean isPerfectSquare(int x) {
    int i = 1, j = x;

    while (i <= j) {
        int m = i + (j - i)/2;
        int p = m * m;

        if (p == x)
            return true;
        else if (p < x)
            i = m + 1;
        else
            j = m - 1;
    }

    return false;
}

ℤ Square Root

This problem concerns with finding the integer portion of the square root of a number. For example, when given 1, 2, or 3, this function should return 1 because the square roots of these numbers are 1, 1.414, and 1.732 respectively, but the integer portion of these numbers is 1. To further illustrate the example, when given 4, 5, or 7, this function should return 2 because the square roots of these numbers are 2, 2.236, and 2.646 respectively, but the integer portion of these numbers is 2.

Example

#   Current Search Range    m
#   1       4       7
#   i       m       j       1 + (7 - 1)/2 = 4
#   1       2       3
#   i       m       j       1 + (4 - 1)/2 = 2
#   2               3
#   im              j       2 + (3 - 2)/2 = 2
#   3
#   imj                     3 + (3 - 3)/2 = 3
#   done because j < i
#   return i - 1

Implementation

public static int intSqrt(int x) {
    int i = 1, j = x;

    while (i <= j) {
        int m = i + (j - i)/2;
        int p = m * m;

        if (p <= x)
            i = m + 1;
        else
            j = m - 1;
    }

    return i - 1;
}

An observation worth noting is that the range covered by an integer square root increases as the given value increases.

Observation

#   Range                   ℤ Square Root   Count
#   0                       0               1
#   1   2   3               1               3
#   4   5   6   7   8       2               5
#   9   10  11  ... 15      3               7

ℝ Square Root

This problem concerns with finding the real square root of a given number up to a given tolerance. It should be noted that this is not the implementation of the Java standard library square root function. The following example traces out the square root of 5 with tolerance of 0.01, which is 2.24.

Example

#   x = 5.0
#   EPSILON (E) = 0.01
#   
#   Current Search Range    Condition           m
#   1.00    3.00    5.00    
#   i       m       j       1.00 < 5.00(1 - E)  1.00 + 0.5(5.00 - 1.00)
#   1.00    2.00    3.00    
#   i       m       j       1.00 < 3.00(1 - E)  1.00 + 0.5(3.00 - 1.00)
#   2.00    2.50    3.00    
#   i       m       j       2.00 < 3.00(1 - E)  2.00 + 0.5(3.00 - 2.00)
#   2.00    2.25    2.50    
#   i       m       j       2.00 < 2.50(1 - E)  2.00 + 0.5(2.50 - 2.00)
#   2.00    2.13    2.25    
#   i       m       j       2.00 < 2.25(1 - E)  2.00 + 0.5(2.25 - 2.00)
#   2.13    2.19    2.25    
#   i       m       j       2.13 < 2.25(1 - E)  2.13 + 0.5(2.25 - 2.13)
#   2.19    2.22    2.25    
#   i       m       j       2.19 < 2.25(1 - E)  2.19 + 0.5(2.25 - 2.19)
#   2.22    2.24    2.25    
#   i       m       j       2.22 < 2.25(1 - E)  2.22 + 0.5(2.25 - 2.22)
#   2.24            2.25    
#   i               j
#   done because 2.24 < 2.25(1 - E) is false
#   return i

Implementation

public static double realSqrt(double x) {
    double i, j;
    if (x < 1.0) {
        i = x;
        j = 1.0;
    }
    else {
        i  = 1.0;
        j = x;
    }

    final double EPSILON = 0.00001;

    while (i <= j * (1 - EPSILON)) {
        double m = i + 0.5 * (j - i);
        double p = m * m;

        if (p == x)
            return m;
        else if (p < x)
            i = m;
        else
            j = m;
    }

    return i;
}

This article is my 22nd oldest. It is 179 words long, and it’s got 0 comments for now.