CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 13 of 13
  1. #1
    Join Date
    Feb 2009
    Location
    USA
    Posts
    68

    Lightbulb Newtons Method for Approximating Roots

    Hi, i have this method here that approximates square roots. I was wondering what ppl thought about it and whether it is following a correct algorithm. It seems to work good and gave pretty close approximations for all my test casses. The only issue is on the very first call to the function, if 1 is passed in as a guess it returns bogus numbers.

    Code:
    /*
     * Newtons Method for Approx. square roots.
     * Accepts 2 doubles.
     * Argument 1 is the number to take the square root of.
     * Argument 2 is the approximation/guess of the square root.
     * x =  1/2( x + A/x)  <-- Formula being used.
     */
    double approxSQRT(double A, double approx)
    {
        double previous=approx;  
    
        approx = (0.5)*(approx + ( A/approx));
    
        //When sequential approximations have a negligable difference the
        //   approximation should be very close to the actual square root.
        if(previous - approx < 0.0000001 )
            return(approx);
    
        return( approxSQRT(A,approx));
    }
    Google is your friend.

  2. #2
    Join Date
    Feb 2009
    Location
    USA
    Posts
    68

    Re: Newtons Method for Approximating Roots

    The full driver prog.

    Code:
    /*
        Gerald Eckert
    
        Using Newtons Method for Approximating Roots
    
        Formula.
         x =  1/2( x + A/x)
    
         x represents the square root or the approximation.
    
         Continue running through this formula untill the
            difference in sequential x values becomes negligable.
    */
    
    #include <iostream>
    using namespace std;
    
    
    double approxSQRT(double,double);
    
    int main()
    {
        double numA=0;     // numA represents the number under the square root.
        double guess=0;    // guess represents the users guess at the square root.
        double sqrt=0;
    
        cout<<"Take the square root of what number? : ";
        cin>>numA;
    
        cout<<"Please take a guess at the square root of "<<numA<<" : ";
        cin>>guess;
    
        sqrt= approxSQRT(numA,guess);
    
        cout<<"The square root of "<<numA<<" is approximatly "<< sqrt <<endl;
    
        return(0);
    }
    
    
    /*
     * Newtons Method for Approx. square roots.
     * Accepts 2 doubles.
     * Argument 1 is the number to take teh square root of.
     * Argument 2 is the approximation/guess of the square root.
     * x =  1/2( x + A/x)  <-- Formula being used.
     */
    double approxSQRT(double A, double approx)
    {
        double previous=approx;  
    
        approx = (0.5)*(approx + ( A/approx));
    
        //When sequential approximations have a negligable difference the
        //   approximation should be very close to the actual square root.
        if(previous - approx < 0.0000001 )
            return(approx);
    
        return( approxSQRT(A,approx));
    }
    Google is your friend.

  3. #3
    Join Date
    Feb 2009
    Location
    USA
    Posts
    68

    Re: Newtons Method for Approximating Roots

    I was doing some more testing and found some weird bugs. The bugs pop up when a user would enter really bad guesses. Like if they guess 34030 for the square root of 125. If anyone knows the algorithm would you let me know if i am using it right. Thanks
    Google is your friend.

  4. #4
    Join Date
    Feb 2009
    Location
    USA
    Posts
    68

    Re: Newtons Method for Approximating Roots

    It returns bogus answers. Like I try approxSQRT(555 , 3) and it returns 94. Ill have to do the math by hand and see what is going on.
    Google is your friend.

  5. #5
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

    Re: Newtons Method for Approximating Roots

    Your program only works if the initial guess is above the result.

    try
    Code:
         if(fabs(previous - approx) < 0.0000001 )
    Kurt

  6. #6
    Join Date
    Feb 2009
    Location
    USA
    Posts
    68

    Re: Newtons Method for Approximating Roots

    Ok, stupid error on my part.
    Code:
     
    approxSQRT(555 , 3)
    
    use the formula
    
    (1/2)*(3 + 555/3)  =  94
    
    find the difference
    
    3 - 94 =  - 91
    
    compare the difference
    
    is  -91 < 0.000001    //Should be using absolute value here.
    
    XD..
    I think using absolute value would solve the issue.

    Thanks ZuK, was writing this when you replied
    Google is your friend.

  7. #7
    Join Date
    Jan 2009
    Posts
    596

    Re: Newtons Method for Approximating Roots

    It would make more sense to use an iterative method here, rather than recursion. With recursion it would be possible to get a stack overflow.

    Try this instead:

    Code:
    double approxSQRT(double A, double approx)
    {
    	double previous = 0.0;
    	do {
    		previous = approx;
    		approx = (0.5)*(approx + (A/approx));
    
    	} while( fabs(previous - approx) < 0.0000001 );
    
    	return approx;
    }
    Or you might want to change the while condition to keep going until the actual value is close enough to the square root, rather than just not changing by much, i.e.

    Code:
    while( fabs( (approx * approx) - A ) < some constant )

  8. #8
    Join Date
    Jan 2009
    Location
    Salt Lake City, Utah
    Posts
    82

    Re: Newtons Method for Approximating Roots

    This one may give you better performance, and it's generic and detects non-real answers:
    Code:
    template<class T> static inline T root(T base, T root)
    {
        if((base < 0) && ((root &#37; (T) 2) - 1))
        {
            // Error: non-real answer
            return (T)0;
        }
        double Number = base / 2;
        const double Tolerance = 1.0e-7;
        do Number = (Number + base / Number) / 2;
        while(abs(pow(Number, (double)root) - base) > Tolerance);
        return Number;
    }
    If you really want to wait for the user's input, though, it wouldn't be hard to add a third parameter to this one, which is the initial guess:

    Code:
    template<class T> static inline T root(T base, T root, double guess = 0.d)
    {
        if((base < 0) && ((root % (T) 2) - 1))
        {
            // Error: non-real answer
            return (T)0;
        }
        if(guess == 0.d)
            guess = base / 2;
        const double Tolerance = 1.0e-7;
        do guess = (guess + base / guess) / 2;
        while(abs(pow(guess, (double)root) - base) > Tolerance);
        return guess;
    }
    Peter_B is absolutely right. It's not so much as a worry of stack overflow, but performance. For example, a recursive fibonacci function could take thousands of times longer than an iteration one, in very extreme situations
    Last edited by Etherous; March 22nd, 2009 at 10:39 AM.
    Intel Core Duo Macbook w/ Mac OS 10.5.6
    gcc 4.2.1 (i386-apple-darwin9.1.0) and Xcode 3.1.1

  9. #9
    Join Date
    Mar 2009
    Posts
    51

    Re: Newtons Method for Approximating Roots

    You should be able to automatically generate a decent first guess:

    Quickly determine the number of digits and then use something like pow(10, (numberOfDigits-1)/2) as the initial guess.

    For example a value of 100 should give you 10 as the first guess which is exactly right.

  10. #10
    Join Date
    Jan 2009
    Posts
    596

    Re: Newtons Method for Approximating Roots

    Quote Originally Posted by Zaccheus@Work View Post
    You should be able to automatically generate a decent first guess:

    Quickly determine the number of digits and then use something like pow(10, (numberOfDigits-1)/2) as the initial guess.

    For example a value of 100 should give you 10 as the first guess which is exactly right.
    If you are going to use the pow function with non-integral powers, you might as well just calculate:

    Code:
    double root = pow( number, 0.5 );
    Your method for calculating a first guess rather defeats the point of this thread
    If you have a set of pre-computed values of pow(10,(numberOfDigits-1)/2) for the possible values of 'numberOfDigits', however, your idea would make sense.

  11. #11
    Join Date
    Mar 2009
    Posts
    51

    Re: Newtons Method for Approximating Roots

    I did say 'something like'.

    Implementing a ten-to-the-power-of function for integers is quite trivial:

    Code:
    double tenToThePowerOf(unsigned n)
    {
        double result = 1.0;
    
        for(unsigned i = 0; i < n; ++i) result *= 10.0;
    
        return result;
    }
    Last edited by Zaccheus@Work; March 23rd, 2009 at 07:47 AM.

  12. #12
    Join Date
    Jan 2009
    Posts
    596

    Re: Newtons Method for Approximating Roots

    Quote Originally Posted by Etherous View Post
    Peter_B is absolutely right. It's not so much as a worry of stack overflow, but performance. For example, a recursive fibonacci function could take thousands of times longer than an iteration one, in very extreme situations
    Yes, the performance is an issue also, due to all the function calls and stack manipulation. It won't be anywhere near 'thousands' of times slower though. The recursive fibonacci function is a pathological case due to the recursion having two branches, each of which is of the same order as the original problem, giving a running time of O(2^n).
    In code:
    Code:
    Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2);
    The iterative fibonacci solution, however, just calculates the fibonacci numbers in order up to n - giving an O(n) solution.

    I didn't mention this before, but a bigger reason not to use recursion for the present case is actually that the problem isn't naturally recursive. Recursive solutions are best used when you can break the problem down into subproblems, which are of the same type as the original problem but smaller. That is not the case for the square root problem.

  13. #13
    Join Date
    Jan 2009
    Posts
    596

    Re: Newtons Method for Approximating Roots

    Quote Originally Posted by Zaccheus@Work View Post
    I did say 'something like'.

    Implementing a ten-to-the-power-of function for integers is quite trivial:

    Code:
    double tenToThePowerOf(unsigned n)
    {
        double result = 1.0;
    
        for(unsigned i = 0; i < n; ++i) result *= 10.0;
    
        return result;
    }
    That would work nicely

    Having a function like your suggestion to give a good first guess also has the benefit of removing this responsibility from the caller of the approxSQRT function, making it much simpler to use - which is always a good thing.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured