Generalized root function

Consider the equivalence of the following two questions:

• What is the square root of 81?
• What number, when squared, gives us 81?

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:

• What is 18 divided by 2?
• What number, when multiplied by 2, gives us 18?

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:

• What is the square root of 11?
• What number, when squared, gives us 11?

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)))