Tuesday 15 March 2011

Newtons Method of Square Roots

Today i will be talking about Newtons method for finding square roots. This is somewhat important in the computing world if while programming you have no access to a direct built in function that allows you to calculate the square root of a number. This should never be the case for almost any language will have this function built into some sort of header/library for use. In my case an assignment for my computer science class wanted me to compute a square root using this method. So to start off we first need to know what Newtons Method is.

Newtons method needs your radian(the number you want to take the square root of) and an approximation of what you think the square root is. Now of course your radian has to be a non negative real number as well as your approximation. Your approximation should also logically be less than your radian. This should be a no brainer.

So now we set the equation Newton laid out for use nicely in his method.
Okay i lied to you. I will not use Newtons Method completely for i find for computing the square root we can skip some math steps if we are programming. Anyhow here is my layout.

Let a  = your approximation , x = your radian, epsilon = nothing at the moment.

1. If   a*a-x = 0 then a is obviously your square root.

2.  else  (a*a+x)/(2*a)  = e

Now a  = e. Then go back to the first step and plug away to see if you get a root. 

As an example lets try and find the square root of 5. Our approximation will be 2.

1. 2*2-5  = -1 which does not equal 0.

2. 2*2+5/(2*2) = 9/4 = 2.25. Let a  = 2.25.

 Now back to 1.

1. 2.25*2.25 - 5 = 5.0625 - 5 = .0625 which does not equal 0.

2. 2.25*2.25 +5/(2*2.25) = 10.0625/4.5 = 2.2361111.

Now we can keep doing this as many times as possible until we feel we have a close enough number to the square root of 5. As i pull out the calculator, as this was an on the spot example. The square root of 5 is 2.236067977 which rounded is 2.2361. So our answer suffices for this equation. Hooray for Newton.

Programming applications. Here is a function i wrote that will display this in terms of C++ code for viewing pleasure.


 root = squareRoot(20,radian,1); //function call
/*Function call passing the number of times i would like the formula to simplify answer or try and find it,
The radian(number we want the square root of), and just a basic approx of 1. Doesn't really matter for this.

double squareRoot(int n,double radian,double approx)
{
    if((approx*approx-25)==0)//if our root is a then we will return the root.
    {
        return approx;
    }
    else
    {
        if(n==0)
        {
            return approx;
        }
//if the root was not found above gets a new approximation to work with.
        approx = (approx*approx+radian)/(2*approx);

        return squareRoot(n-1,radian,approx);
    }
}


Now this code example is using recursion, but upon inspection we can see the formula i laid out for you in action. Now using my program that i created for my assignment with the above code being apart of it. Lets calculate some ridiculous large square root.

Lets say 696969696. My program says 26400.2.
Using a calculator we get 26400.18364. Which is just not a simplified answer. 
Thus you can see how accurate you can find the square root of a number using Newtons Method and programming.

Hope you enjoyed this.

DisposedCheese

15 comments:

  1. Oh wow very nicely explained! Thanks!

    ReplyDelete
  2. I think it's actually quite interesting that this method works no matter if the approximation is smaller or larger than the actual square root.

    ReplyDelete
  3. nice
    you should check this out
    http://www.siafoo.net/snippet/17

    ReplyDelete
  4. niffty stuff but even at my level of programming skilsl i understand barely anything

    ReplyDelete
  5. I should probably save this stuff and read it later, when i'll acquire some background knowledge in this area

    ReplyDelete
  6. You can totally pick up shit tons of chicks with this....lol

    ReplyDelete
  7. I've always wondered what the code behind the square root button was. thanks for this :P

    ReplyDelete
  8. I'm definitely gonna save this and read it all when I have the time later it's very interesting stuff.

    ReplyDelete
  9. god i wish i was smart like you /: because i know these things are important and pertinent but like... gahhh good for you!

    ReplyDelete
  10. man, so smart:P I had to figure this out on my own for a computer science assignment this term, not fun:P

    ReplyDelete
  11. Man I can't stand math but you made it pretty interesting :D

    ReplyDelete
  12. uhhhhhhhhhhhhhh wow. I'll take your word for it.

    ReplyDelete