As you see the Bi Section method is really simple, however, it's not that effective.

This time I will introduce a different method to calculate square roots, this method is called "Newton-Raphson's method", it's named after Issac Newton, and Joseph Raphson.

This method is known to be really effective --especially when the initial guess is near from the correct answer-- and it's considered to be

*the*

*best known method for finding successively better approximations to the zeroes (or*

*roots*

*) of a*

*real*

*-valued*

*function.*

Explaining this method will require a certain amount of familiarity with Calculus and Algebra, so I'm not going to delve into this here. However, I will show you the code to do it in Python and C# (which, surprisingly you will find very simple).

First, the code in Python:

def sqrtWithPrecisonNR(x, precision): assert x >= 0, 'x must be non-negative, not' + str(x) assert precision > 0, 'epsilon must be positive, not' + str(precision) x = float(x) guess = x/2.0 diff = guess**2 -x ctr = 1 while abs(diff) > precision and ctr <= 100: guess = guess - diff/(2.0*guess) diff = guess**2 -x ctr += 1 assert ctr <= 100, 'Iteration count exceeded' print 'NR method. Num. iterations:', ctr, 'Estimate:', guess return guessSecond, the code in C#:

float SqrtWithPrecisonNR(float x, float precision) { if (x < 0 || precision <= 0) throw new ArgumentException("x, and precission gotta be non negative numbers"); float guess = x/2.0f; float diff = guess*guess - x; int counter = 1; while(Math.Abs(diff) > precision && counter <= 100) { guess = guess - diff/(2.0f*guess); diff = guess*guess - x; counter++; } if(counter > 100) throw new Exception("100 iterations done with no good enough answer"); Console.WriteLine("Num of Iterations: {0} , estimate: {1}", counter, guess); return guess; }

Now, I want you to try this method with the last one and see the difference.

Here's a helper function that will test the two methods with input 2 as the root and 0.000001 precision:

def testMethods(): sqrtWithPrecision(2, 0.000001) sqrtWithPrecisionNR(2, 0.000001)

You should see that the Newton's method is much faster and this difference in speed will be totally apparent when you try it on bigger numbers.

For more details about the Newton's method including the mathematical stuff see here

## No comments:

Post a Comment