(* 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