Background

Once humans started living sedentary, they discovered the need to figure out mathematics. As early as 1800-1600 BC, the Babylonians developed a method to solve quadratic equations. Figure below is a tablet in the Yale University’s collections. Without getting into the tablet’s details, it depicts the root finding method well known to the Babylonians, rediscovered by the Greeks and the Indians in later centuries. Algorithm is as follows:

1. Assume you want to find the root of a natural number $N$.
2. Make an initial guess, $x_0$.
3. Divide $N$ by your guess: $N/x_0$
4. Average the result with your guess and make that the new “improved guess”: $\frac{x_0 + N/x_0}{2} = x_1$
5. Repeat steps 3 and 4 with your new guess until you reach a satisfactory level of accuracy.

The iterative formula becomes $x_{i+1} = \frac{x_i + N/x_i}{2}$ and it is proven to be converging quadratically while computationally being quite cheap. (If you are interested in finding out what the specific numbers on the tablet really mean in relation to the iterative root finding formula please refer to YBC_7289.)

The Babylonian root finding method was commonly used before Newton formulated his method for root finding in the late 1600s while contemporaneously Raphson discovered a similar version for polynomials up to 10th degree. Funny enough, at least during the Newton’s lifetime, his method didn’t even include the derivative in his original writings even though Newton was having a food fight with Leibniz about the Calculus notation at the same time. The proposed root finding method was generalized beyond polynomial equations by Euler about 50 years later. Newton-Raphson method generalizes the Babylonians’ method for any function $f(x)$ as follows:

1. Assume you want to find the root $r$ of $f(x)$.
2. Make an initial guess, $x_0$ where $x_0 = r - \epsilon$ and $\epsilon \approx 0$ ($\epsilon$ as the error in your estimate).
3. As $\epsilon$ is small, using linear approximation around $r$: $$f(r) = f(x_0 + \epsilon) \approx f(x_0) + \epsilon f'(r)$$
4. Since $f(r) = 0$, rearranging gives: $$\epsilon \approx -\frac{f(x_0)}{f'(r)}$$
5. Therefore, the updated approximation for the root is: $$r = x_0 + \epsilon \approx x_0-\frac{f(x_0)}{f'(r)}$$

which brings us to the generic formula:

$$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}$$

I am sure you see how the Babylonian formula is derived from $f(x) = x^2 - N$ and $f'(x) = 2x$ with few steps of algebra. There are numerous articles and papers on the Newton-Raphson method and its convergence properties so I will not go into the details here. However, there are few important points about how to use the method efficiently:

1. Initial guess is important. If you are too far away from the root, convergence may be slow or not happen at all.
2. If the derivative is zero, due to a local minima or maxima, the method fails.
3. If the second derivative is large near the root, convergence may be slow.
4. For functions with multiple roots, depending on the initial guess, method may converge to different roots.
5. For functions with discontinuities or sharp turns, the method may fail to converge.

One of the ways to have a better understanding of these short-comings is to visualize the method that shows its iteration steps. Prefereably, we should be able to enter the function, along with our initial guess and see how it works (or it doesn’t).

Focus of Learning

Now that we have a good understanding of the root finding method, let’s see how we can implement it in a Kubernetes environment. Continuing with the use of SageMath in the previous blog Prime Jobs, I tried to do few things in terms of learning this time around:

1. Create an updated Docker image that includes SageMath, FastAPI as well as an mp4 generator and a Redis client.
2. Create a node.js based web front-end that allows a user to enter a function, initial guess and other parameters.
3. Implement a Redis reader that fetches the mp4 movies from the Redis db.

Once these components are in place. I wanted to build something as below.

My reasons for the component choices were:

1. I used FastAPI to call SageMath in the previous blog. In this case I simply extend it with some application logic to call a movie generator and a Redis client.
2. I used the same Redis db as a simple way to communicate among components.
3. I re-used the redis-cli from the previous blog to write and read from Redis.
4. I knew very little about node.js and wanted to learn more about it by building a simple front-end.

Implementation Details

In order to follow the rest of the blog, please check the GitHub repository blog-finding-roots.

Create a Container Image for Redis Reader

As shown in the architecture diagram above, I needed a simple Redis reader that fetches the generated mp4 movies from the Redis db and saves them to a local directory. This component is implemented in Python using the redis client library. Follow the instructions in the README file for the GitHub repository redis-client to build and store the image.

Eventually this image is used to instantiate a sidecar container in the same Pod as the Newton-Raphson UI so that the generated movies can be saved locally and served by the node.js front-end.

Create a Container Image for Newton-Raphson User Interface

The heart of the learning in this blog was to create a node.js based user interface. Since I knew so little about how to write such an application on my own, I consulted one of the famous vibe-coding assistants of our times, Claude’s Sonnet-4.5 (free with rate-limits).

Using the list of prompts below (somehow paraphrased a bit) and some others to troubleshoot, I was able to get a working version of the front-end application.

__ASK__: generate a React single page template for a page
that collects commands for a remote program.
__CONTEXT__: generic script language that will be interpreted
remotely and the script input will be sent from the single
page app via a REST API.
__CONSTRAINTS__: there should be one way to enter data to
start with.
__EXAMPLE__: here is a sample response from the REST API.
update the application code so that it shows what is stdout
if the return code is 0; otherwise show the stderr string.
integrate this UI with an nginx docker image

Obviously the important part was the example REST API response that guided the assistant to generate the code that would handle the response properly.

I am including a screenshot of the UI below. Surely you will be able to improve its functionality and appearance on your own. The code is available in the GitHub repository nr-root-finder-ui.

Create a Container Image for Newton-Raphson Backend

A useful constraint in a (software) project is to re-use as much as possible from earlier work. However, this has to be moderated against the necessity to prevent dependency among unrelated deliverables. In this case, I followed the same approach as in the previous blog to create a SageMath based backend service. This time, I removed unneeded endpoints and added a new endpoint to collect the root finding parameters from the front-end, generate an mp4 movie and upload the movie to the Redis db.

The code is available in the GitHub repository nr-backend-service. Because of the same image size limitations, I built the image on my laptop and ran it as a container there. The following command was used to start the container:

podman run --rm -it -p 8000:8000 -e REDIS_HOST=192.168.1.2 -e REDIS_PORT=30007 -e SCRIPT_PATH=/home/sageuser/code/sage/ localhost/nr-backend-service

As you’d expect, my Kuberenetes cluster is running on a different machine with IP 192.168.1.2 and I used a NodePort service to expose Redis to the backend service.

Deployment of the Kubernetes Resources

Assuming you happen to have access to a Kubernetes cluster, follow the instructions of the GitHub repo blog-finding-roots to simplify the generation of resource files. I’d recommend you use the demo deployment option using kustomize.

Complete the following steps for customization:

1. Create a namespace demo in your cluster.
2. Update $CONTENT/overlays/demo/kustomization.yaml to add the namespace and point to your container image registry for redis-reader and nr-root-finder-ui.
3. Update $CONTENT/overlays/demo/finding-roots-demo.env.
4. Adjust the patch files for the IP address of your host where the nr-backend-service is running.
5. Adjust the patch files for the NodePort values for the Redis and the UI services.
6. Run kubectl apply -k $CONTENT/overlays/demo to deploy all the resources.

You will be able to access the UI at http://<NODE_IP>:<UI_NODE_PORT>. Having an interactive service like this will hopefully allow you to see the inner-workings of the Newton-Raphson method better. If you happen to find interesting examples such as functions that don’t converge well, please share them with me on your preferred social media.

Here is a rather lame one to start with: $f(x) = x^3 - x^2 + 1$.

Set the initial guess to 1.7, the min and max for x-axis to -3.2 and 3.2 respectively. Iteration limit of 20 should be sufficient.

Blog’s lead image was generated from plotting roots of all 12th degree polynomials with coeeffients in {-1,1} in polar coordinates. Inspiration comes from Dan Christensen of Western University, Canada.