Back to Basics – Newton’s Method

I recently joined the Dream In Code family, and found that there’s a higher than expected number of responses from (university freshman) students asking for programming help. Then I read this article about classic computer science puzzles. There’s mention of an expert go player who still reads through fundamental go problems. The goal of rereading? To solve the problems faster than before.

This gave me the cool idea of revisiting my freshman computer science textbook. I graduated from a computational science course, as opposed to a computer science course. My lecturer gave this explanation for the distinction:

Computational science students use programming to solve scientific problems. Computer science students focus more on the programming.

For computational scientists, the main goal is to understand and solve science problems, be they from the realm of mathematics, physics or other sciences. Programming is just a tool to the solution, because using a computer to do calculations is so much faster than doing it by hand.

After years of programming and real world application experience, I wanted to find out how I would have solved those textbook problems. So I dusted off my textbook, and flipped through the programming exercises and found something interesting. The given problem was to use the following formula to find approximate roots:
Newton's method
The function provided was
f(x) = x3 – 3
and the derivative function was
f'(x) = 3x2
So basically we’re finding the cube root of 3.

There’s a brief mention that it’s the Newton’s method for finding roots of equations in the exercise question. Since a derivative of the function is required, I think the lecturer gave it to us back then, in case some of the students weren’t familiar with math differentiation. All that’s left was to code it.

The textbook was based on the C language, but I’m adapting it to C#. Here’s the code (download the full project)

const double epsilon = 0.000001;
double currentx, nextx;
double fx, fprimex;
int i = 1;

currentx = 1234;
// our best guess for cube root of 3
nextx = 1.5;
while (Math.Abs(currentx - nextx) > epsilon)
    Console.WriteLine("Iteration {0}: {1}", i.ToString("d2"), nextx);
    currentx = nextx;
    fx = currentx * currentx * currentx - 3.0;
    fprimex = 3 * currentx * currentx;
    nextx = currentx - (fx / fprimex);

I remember some key points about these kinds of assignments discussed during university days. They usually revolve around some sort of iteration process. So while loops and for loops were my constant companions. Loops were used to slowly refine a solution to a better one, hence the iteration process.

You might have noticed I used a const variable epsilon. Solutions at one iteration step are compared with the solution at the next step. The comparison usually involves comparison of their difference with zero. Since doubles are used, and zeroes don’t usually play nice with floating point variables, a small number is used, such that if the difference is smaller than this small number, then it’s deemed to be accurate enough.

Then comes the next pitfall: the infinite loop. If the difference never becomes small enough to terminate the loop, the program crashes. Sometimes, you might have to solve an equation where you don’t know if the iteration can terminate.

So comes the additional loop terminator: the number of iterations as an upper limit. I can’t tell you how many iterations to run before declaring it a failure. 10000 is usually a big enough number to try though. If the loop terminates when you know the solution can be further refined, then try increasing the iteration limit. I didn’t add this for the given code because I know the iteration process is very stable, and terminates after few iterations.

There’s also usually variables invariably named current, previous and/or next. It’s a characteristic of the iterative methods to be coded.

So what can you get out of this?

As a programmer, you will eventually come across something where the theory behind the (business) logic is unknown to you. Take heart that you might not even have to understand it! You only have to transform whatever it is into code.

This ability to bring theory into code is more important than understanding the theory itself.

There’s always a mathematician who can explain why Newton’s method works, but you’re the only one who can code it.