Generalized root function

Consider the equivalence of the following two questions:

We can do this for cube roots, or even nth roots as well. But we notice this structure in other functions too. For example, consider the equivalence of the following:

Notice that for both nth roots, and division by a constant, we can search for an answer. We can ask, "does 0 squared equal 81? "does 1 squared equal 81?" and so on, until we find 9 squared equals 81. We can do this because \(x / 2\) is a strictly increasing function. But consider the following:

In this case, when we search for the number that when squared equals 11, we'll eventually pass it. That is, we'll find 3^2 = 9, and 4^2 = 16. So our answer lies between 3 and 4. If we want our function to return a natural number, we might desire the integer part of the square root. We could write this search function for square roots, but the general case is nearly identical. Here's a generalized root function \(h,\) which can be instantiated whenever \(f\) is strictly increasing.

$$\begin{align} & g(x, y) = \begin{cases} g(x + 1, y) & \text{if }f(x) \lt y \\[0.5em] x & \text{if }f(x) \ge y \end{cases} \\[1em] & h(y) = g(0, y) \end{align}$$

For example, suppose we want to find the integer part of the square root of 11. Then \(f(x) = x^2,\) and our computation proceeds as follows:

$$\begin{align} h(11) &= g(0, 11) \\[0.25em] &= g(1, 11) \\[0.25em] &= \ldots \\[0.25em] &= g(4, 11) \\[0.25em] &= 4 - 1 \\[0.25em] &= 3 \end{align}$$
def f(x):
	return x ** 2

def g(x, y):
	if f(x) < y:
		return g(x + 1, y)
	elif f(x) == y:
		return x
	else:
		return x - 1

def h(y):
	return g(0, y)

for i in range(0, 10):
	print(str(i) + ' ' + str(h(i)))