Sqrt - Math Without Operator To Do It

Published: Jun 12, 2017

In my last post, Math Without Operator To Do It, I wrote about division an power implementations. There’s one more of this sort worth adding a memo here. It is calculating a square root without language provided operators.

There’s always an intuitive solution, while always effective solutions are. I’m going to write multiple solutions.

Problem Description - Integer Square Root Implementation

“Given an integer, find its square root in integer. If the square root is not an integer, the answer will be a floor of it”

For example, given 11, the answer will be 3. It is a fairly easy to understand problem.

The idea to find a square root - naive iteration

Since the answer will be only integer, I counld instantly think of a naive solution. Iterating integer from one to the given number, I will hit the integer whose multiple of itself exceeds the given number. Then, the answer will be that integer minus one.

x: given number

for (int i = 2; i < x; i++) {
    if (i * i > x) {
        return i - 1;
    }
}

This will return a correct answer, but the problem is its slowness. Time complexity is O(n).

The idea to find a square root - binary search

Again, the answer is the integer. Also, the answer is between 2 to the given number. All numbers are there in a sorted order. This is a perfect condition for a binary search.

x: given number

while (low <= high) {
    long mid = (low + high) / 2;
    long temp = mid * mid;
	if (temp <= x) {
        low = mid + 1;
        result = mid;
    } else {
        high = mid - 1;		
    }
}

The binary search improves the performance to O(log(n)). This should be fast enough. However, when the given number is big, I got time out error on the code competition website.

The idea to find a square root - Newton-Raphson method

This is a really fast, sophisticated solution. However, despite of very simple code, it took a while for me to understand why such calculation gives the answer.

The Newton-Raphson methed (NR method) has a mathematical, especially, diffential equation backgound. Also, NR method is an iterative solution to approximate root. The important point here is to find a function which satisfies:

diffentiable (continuous)
f(x) = 0 for some good value x

Given such a nice function, if I think of a slope of that, it would be:


the slope at point: (x_n, f(x_n)), where y = f(x)

f'(x) = d f(x) / dx

f'(x_n) = (y - f(x_n)) / (x - x_n)

by the definition, y = f(x) = 0,

f'(x_n) = (- f(x_n)) / (x_n+1 - x_n)

x_n+1 = x_n - f(x_n) / f'(x_n)

Now, I got the formula to iterate. The question is what is f(x). Since I want to find a number x to the given number a:


x = sqrt(a)

x^2 = a

x^2 - a = 0

x^2 - a = 0 = f(x)

f'(x) = 2x

Ok, I got the function, so let’s plugin to the previous formula.


x_n+1 = x_n - (x_n^2 - a) / 2 * x_n

x_n+1 = 1/2 * (2 * x_n - x_n^2 / x_n + a / x_n)

x_n+1 = 1/2 * (2 * x_n - x_n + a / x_n)

x_n+1 = 1/2 * (x_n + a / x_n)

If I iterate above calculation not to exceed the given number, I’ll get the integer square root.

The time complexity of NR method is the same as binary search, O(log(n)). However, it quickly converges to the answer. This is because the binary search increments the value one by one, while NR method effectively cuts down to half.

Java code for square root implementation

The result is: