Integer Square Root

Occasionally, we’re faced with the problem of calculating the square root of an integer. Here are three algorithms:

• This method is the least efficient. It relies on the fact that the difference between consequent squares is the series of odd numbers.

i	0	1	2	3	4	5	6
sqr(i)	0	1	4	9	16	25	36
sqr(i) – sqr(i + 1)	1	3	5	7	9	11	…

So, given an input integer n what the algorithm does is:
It starts with square = 1 and keeps adding odd integers (delta) from the series until square reaches n(the input integer). The root is sqrt(n) = delta / 2 - 1.
Implementation in C++

template
type sqrt(type n) {
	type square = 1;
	type delta = 3;
	while (square 		square += delta;
		delta += 2;
	}
	return delta / 2 - 1;
}

• The second method to guesses a root (guess) and then tries to minimize the distance to the real root.

In C++:

template
type sqrt(type n) {
	type upperBound = n + 1;
	type guess = 0;
	type lowerBound = 0;
	type delta;
	while (delta = (guess = (upperBound + lowerBound) / 2) * guess - n)
		if (delta > 0)
			upperBound = guess;
		else
			lowerBound = guess;
	return guess;
}

• This method is similar to the previous. However, it has different logic. We’re trying to “build” the root bit-by-bit. It is the most efficient among them.

In C++:

template
type sqrt(type n) {
	type guess = 0;
	int newBit = 1 << (sizeof(type) * 4 - 1); 	while (newBit > 0) {
		if (n >= (guess + newBit) * (guess + newBit))
			guess += newBit;
		newBit >>= 1;
	}
	return guess;
}

Caution!

• C++’s <cmath> is faster!
• Results for non-integer squares are not reliable.