Roots of Functions for Programmers
Writing code to find the roots of functions is more common than we think. This task is so commonplace that programmers often implement it without realizing what they are actually doing. Check out the definition below:
The roots of a function f(x) are the values of x such that f(x) is zero.
— Root of a function, Wikipedia
Maybe you’re not associating this definition with anything practical. Check out some application examples then:
- Calculate if two objects collide in a game or VR environment
- Calculate the maximum number of requests/sec to consume all the server’s resources
- Calculate the minimum area of a given component in a responsive visual layout
Sometimes, solving a problem like this is as simple as a single division. Sometimes, however, the solution is more elaborate.
In this story, we will briefly talk about finding the roots of functions from a practical algorithm implementation perspective.
PS.: this story is a continuation of this story.
A visual insight
We can easily visualize the root of functions by just checking the function’s plot. For example:
The roots are the intersection points • of the f(x) curve and the x-axis. In this case, f(x) is a generic function with only three roots.
Common analytical examples
If f(x) is linear such as f(x) = ax + b, the only root is given by x = -b/a
PS: Note that a must differ from zero in the formula x = -b/a.
But what if f(x) is not linear? We can pick several trivial examples:
- if f(x) is a second-degree polynomial, we can use the famous Bhaskara’s formula:
to find the two possible roots:
- if f(x) is the sine function f(x) = sin(ax), then every x such that x = nπ/a for n ∈ ℤ = {…-3, -2, -1, 0, 1, 2, 3, …} is a root:
Numerical Root-finding methods
In the previous three examples, we found the roots of f(x) using well-known analytical properties. However, this is not always possible. Consider the following function:
f(x) = ln(x) + sin(x)
At first glance, there is no analytical way to find x such that f(x) = 0. We can try to get some insight by plotting the function:
The plot suggests that f(x) = ln(x) + sin(x) has only one root located inside the interval [0,1]. However, only looking at the plot cannot accurately determine the actual value of this single root.
In cases like this, where an analytical solution is not available, and we have some idea about the existence and location of the root, we can use numerical root-finding methods.
Instead of providing exact values, numeric methods provide good approximations for real function roots using an iterative process.
The most famous numerical method for finding a function root is the Newton-Raphson method, a procedure that every programmer should know. I will explain this method in another story soon.
About the existence of roots
Before finishing this talk, let’s visit Bolzano’s Theorem:
If a continuous function has values of opposite sign inside an interval, then it has a root in that interval.
— Intermediate value theorem, Wikipedia
What this theorem states is that, for a continuous function f(x), if f(a) is positive and f(b) is negative (or vice versa), then there exists at least one root between a and b.
This is similar to the scenario of someone walking on one side of the road. If this same person is lately seen on the other side of the road, then we can deduce that at some moment that person crossed the road.
More formally, if f(a) x f(b) < 0, then there exists at least one real root of f(x) inside the interval [a,b].
Of course, in Bolzano’s theorem, f(x) must be continuous. This is not true for f(x) = 1/x, for example:
which is not continuous on x = 0.
If f(x) is always positive or always negative, it has no real root. For example f(x) = exp(x):
Even though f(x) = exp(x) is very close to zero when x → -∞, in fact, f(x) is never equal to zero.
Finally, f(x) = ln(x) is a legitimate example of a continuous function with one real root:
About this story
This story was written using the old-style clickety-clack sound of the keyboard. If you enjoyed the reading, give a clap and/or comment.
