The integer part of square roots

Consider a domain of discourse in which the only meaningful values are natural numbers. That is, all expressions evaluate to natural numbers. Then the square root of most numbers, such as the square root of two, is undefined. However, the floor of the square root of two, is one. That's because

$$1^2 \le 2 \lt 2^2$$

Since our domain consists of only natural numbers, we can tabulate our function: $$\begin{array}{c|ccccccccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \ldots \\ \hline \left\lfloor \sqrt{x} \right\rfloor & 0 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 3 & \ldots \\[1em] x & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & \ldots \\ \hline \left\lfloor \sqrt{x} \right\rfloor & 3 & 3 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 & \ldots \end{array}$$

Supposing we can't simply evaluate the square root of a natural number and subsequently round it down, how can we compute this? I will show you two ways. The second way is better, but the first will help you understand the second, so please bear with me. Let \(x = 5.\) Hold a natural number \(i\) that begins at \(1.\) Then \(i^2\) is less than or equal to \(x,\) so we increment \(i.\) We repeat this until \(i^2\) is greater than \(x,\) then we return \(i - 1.\) We know that returning \(i - 1\) is permitted, because \(i\) starts at one, and only increases.

$$\begin{align} 1^2 & \le 5 \\ 2^2 & \le 5 \\ 3^2 & \gt 5 \end{align}$$

So finally we have \(i = 3,\) and thus our function returns \(2\) when \(x = 5.\) To see that it works for square numbers too:

$$\begin{align} 1^2 & \le 9 \\ 2^2 & \le 9 \\ 3^2 & \le 9 \\ 4^2 & \gt 9 \end{align}$$

In this case, we end at \(i = 4\) and thus our function returns \(3\) when \(x = 9.\) Here's a Python implementation of this algorithm:


def floor_sqrt(x):
	i = 1
	while pow(x, 2) <= x:
		i += 1
	return i - 1

Now, that works, but it's not very efficient, because we're squaring successively large \(i.\) It would be much better to jump from one square number to the next, and compare against this value. To see how this is can be done, check out this table of first differences for square numbers:

$$\begin{array}{c|cccccc} x & 0 & 1 & 2 & 3 & 4 & 5 & \ldots \\ \hline x^2 & 0 & 1 & 4 & 9 & 16 & 25 & \ldots \\ (x + 1)^2 - x^2 & 1 & 3 & 5 & 7 & 9 & 11 & \ldots \end{array}$$

Aha! So to go from one square number to the next, we just have to add an odd number.

It appears the distance between the \(n\)-th square number and the \((n + 1)\)-th square number is \(2n,\) but we must prove it algebraically:

$$(x + 1)^2 - x^2 = x^2 + 2x + 1 - x^2 = 2x + 1$$

Instead of creating an unnecessary variable to hold succesive square numbers, we can repeatedly remove successive odd numbers from \(x.\) Here's our new algorithm:


def floor_sqrt(x):
	i = 1
	j = 0
	while x >= i:
		x -= i
		i += 2
		j += 1
	return j