Computing (integer) square root is usually done by using a float square root routine and casting it to an integer, possibly with rounding. What if, for some reason, we can’t use floats? What are the possibilities?

One possibility is to use binary search to find the square root of a number. It may be a good choice because it will only perform a number of iterations that is half of the (maximum) numbers of bits of the number (we will explain why in a moment). Another possibility is to use Newton’s method to find the square root. It does a bit better than binary search, but not exceedingly so: on very small integers, it may iterate a third as much iterations as binary search, but on large integers, it will do only a bit fewer iterations. Can we do better? Yes!

Read the rest of this entry »