Remember being in high school? I do. Maybe that is just because it was a short time ago. However, my most dreaded thought each day in high school was waking up and going to math class to learn about various concepts and formulas. At the time I found absolutely no relevance to what I wanted to do in regards to what was being taught. Unfortunately, at that time I was more focused on developing business applications and not really getting into the core computer science. However, life goals have changed and I look back now and remember my math teachers constantly telling me that if I wanted to become a good programmer I must be an excellent mathematician – yet I constantly argued the point. Now if I was told this today, I would still argue that knowing a much larger understanding of mathematics other then basic arithmetic and minimal algebra is not necessary. I would argue this for many of reasons, but I would also argue on the other side (for agreeing what teachers had said). Anyways, this article is about a brief overview of Newton’s Methods for finding roots and applying that to programming and computation.
Throughout this article, I will explain and demonstration the mathematics along with the appropriate C++ source code to find the square root of a number using the Newton-Raphson’s method. Below is the completed function for finding the square root of a specified number x using Newton-Raphon’s methods; hence the NR on the end of the function name.
#include <algorithm>
#include <cassert>
#include <cmath>
double SquareRootNR(double x, double epsilon)
{
/* Added for the sake of assuring we have appropriate input of x and epsilon */
assert(x >= 0);
assert(epsilon > 0);
x = (double) x;
double guess = x / 2.0;
double diff = pow(guess, 2) - x;
while( fabs(diff) > epsilon )
{
guess = guess - (diff / (2.0 * guess));
diff = pow(guess, 2) - x;
}
return guess;
}
As you can see that this function takes two arguments; one being the number x which we want to find the root of and the other is the epsilon. But what the heck is an epsilon you ask? Well an epsilon is the fifth Greek letter that is typically used for many of things. However, in this case epsilon is used for the precision of the numeric data type. More information on the Greek letter Epsilon can be found here.
Within this function SquareRootNR, you can also see that we perform some mathematical equations. Well, the mathematics used within this function are actually extremely well known but are also mathematical derivatives. But what the heck does this mean? In short form, the derivative is a measure of how a function changes as its input changes. For this function, we are using what is known as a Geometric Interpretation of a Derivative. The derivative of a function at a chosen input value describes the best linear approximation of the function near the input value. For a real-valued function of a single real variable, the derivative at a point equals the slope of the tangent line to the graph of the function at that point. This is typically categorized as Single Variable Calculus. More information can be found here.
Alright, let’s start analyzing the SquareRootNR function and the mathematics used within it. First, we will note that we will be using x to represent the number 16. Therefore, we will find the square root of 16 (which we already know to be four. However, for sake of explanation pretend we do not).
Here is the graph that represents the function Æ’(g) = g2-x and in the sense of the SquareRootNR function, the calculation of pow(guess, 2) + 16.
The initial idea for this method (Newton’s method that is) is as follows: one starts with an initial guess which is reasonably close to the true root, then the function is approximated by its tangent line, and one computes the x-intercepts of this tangent line. The x-intercept will typically be a better approximation of the function’s root then the original guess, and the method can be iterated.
[ Cited from Wikipedia ]
To relate Newton’s method to our function SquareRootNR, you can see that our initial guess is x divided by two. From there, we get the difference between the guess to the power of two and the value of x. Once we do that, we enter into an iterative stage that will continue iterations while the absolute value of the difference is greater then the specified epsilon value. During the iterations, we will continuously re-calculate the values of guess and the difference.
Below is some base knowledge and formulas required to find the square root for the specified number x. I have also provides an example of the calculations to find the square root of the number 16. However, please note that the calculations are not inline with the SquareRootNR function as my initial guess was 3 instead of 5.333 of what it would be within the SquareRootNR function.
So mathematically we are doing some basic calculus and algebra to solve the square root. More information regarding Newton’s method can be found here.
One cool fact about Newton’s Method, is that this method for finding the square root of a number is typically the base functionality that a calculator uses to find a square root. Cool eh?
I hope that I have provides a base understanding of Newton’s method and how to compute the square root of a specified number using this method. I look forward to hearing comments, questions and or concerns. If areas within this article need to be explained further – please let me know and updates will be done.
One Comment