Tuesday, March 4, 2014

Ceiling of Square Root of BigInteger in Java

I was working on the programming assignment* of a MOOC dealing with big integers. I chose Java as the language and used BigInteger to handle the giant integers. In the assignment, I had to find the ceiling of the square root of a big integer (to be used somewhere else in the assignment), so I tried to find a built-in function for this. As some people I saw on online discussion forums, I could not find such a built-in function. As a result, I had to either use one coded by someone or implement one myself. The later was easier for me because by doing that, I did not have to worry about possible lack of background knowledge to understand a decent but difficult algorithm. 

(* Because the assignment is not about finding the ceiling of the square root of an integer, the code in this article does not violate any code of conduct. In fact, finding the ceiling of the square root of an integer for this assignment can be done by programming in another language using that language's libraries.)

Because what I wanted was the ceiling, which is also an integer, a simple algorithm for the approximation of the square root can lead to such a ceiling. I wrote a function for this for positive integers (for the assignment's purpose, many checks were unnecessary and therefore omitted): 

    /***
     * Finds the ceiling of the square root of an integer
     * @param N: the integer whose square root to find
     * @return the ceiling of the square root of N
     */
    public static BigInteger biSqrt(BigInteger N) {
        BigInteger o = new BigInteger("1");
        BigInteger t = new BigInteger("2");
        
        BigInteger u = N; // upper bound of search region
        // initial search value = ceil(0.5*N)
        BigInteger r = N.mod(t).compareTo(o) == 0 ? N.divide(t).add(o) : N.divide(t);
        BigInteger b = new BigInteger("0"); // lower bound of search region
        
        // new search value is ceiling of mid of upper and lower bounds
        while (true) {
            BigInteger r2 = r.pow(2); // square of search value
            
            if (r2.compareTo(N) > 0) {
                // too large, lower search upper bound
                u = r;
                BigInteger s = u.add(b);
                r = s.mod(t).compareTo(o) == 0 ? s.divide(t).add(o) : s.divide(t);
            } else if (r2.compareTo(N) < 0) {
                // too small, increase search lower bound
                b = r;
                BigInteger s = u.add(b);
                r = s.mod(t).compareTo(o) == 0 ? s.divide(t).add(o) : s.divide(t);
            } else {
                // find the value
                break;
            }
            
            // handle non-integer square root, 
            // whose ceiling = final upper bound
            if (u.compareTo(r) == 0) {
                break;
            }
        }
        
        return r;
    }

If executing these: 

        BigInteger z = new BigInteger("0");
        BigInteger o = new BigInteger("1");
        BigInteger t0 = new BigInteger("9");
        BigInteger t1 = new BigInteger("11");
        BigInteger t2 = new BigInteger("1099511627776"); // 2^40
        BigInteger t3 = new BigInteger("1099511627777"); // 2^40 + 1

The results are: 

0
1
3
4
1048576
1048577

The code was not reviewed by anyone other than myself, so it might have issues. Also, there are better algorithms for the same task. However, this should suffice for completing the assignment in Java. 

Any constructive feedback will be appreciated. 

No comments:

Post a Comment