4 Replies - 774 Views - Last Post: 04 April 2013 - 08:25 PM Rate Topic: -----

#1 Yuriy M  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 43
  • Joined: 05-September 07

Incorrect root value being returned in recursive bisection program

Posted 02 April 2013 - 07:24 PM

Hi guys. I have a problem with a recursive bisection program that does not seem to be returning a proper root value. Here is the code:
#include <stdio.h>

#include <math.h>
double bisect(double, double, double, double(double), int *);                                 /* Implements bisection method for finding a root of a function */

double g(double);                                                                             /* Test function 'g' */

double h(double);                                                                             /* Test function 'h' */

double find_root(double, double, double, double, double, double, double, double(double), int);/* Finds root or new interval of a function */
int main(void)

{

    /* Declare variables */

    double x_left,                                                                            /* Left endpoint of interval */

           x_right,                                                                           /* Right endpoint of interval */

           epsilon,                                                                           /* Error tolerance value */

           root;                                                                              /* The root of the function */

    int    error;                                                                             /* The error value used in case of no root */

   

    /* Get endpoints and error tolerance from user */

    printf("\nEnter interval endpoints> ");

    scanf("%lf%lf", &x_left, &x_right);

    printf("\nEnter tolerance> ");

    scanf("%lf", &epsilon);

   

    /* Use bisect function to look for roots of g and h */

    printf("\n\nFunction g");

    root = bisect(x_left, x_right, epsilon, g, &error);

    if (!error)

     printf("\n   g(%.7f) = %e\n", root, g(root));

    

    printf("\n\nFunction h");

    root = bisect(x_left, x_right, epsilon, h, &error);

    if (!error)

     printf("\n   h(%.7f) = %e\n", root, h(root));

    return 0;

}
double bisect(double x_left, double x_right, double epsilon, double f(double farg), int *errp)

{

    double x_mid,                                                                             /* Midpoint of interval */

           f_mid,                                                                             /* f(x_mid) */

           f_left,                                                                            /* f(x_left) */

           f_right;                                                                           /* f(x_right) */

    int    root_found = 0;                                                                    /* Value that determines found or unfound roots */

   

    /* Computes function values at initial endpoints of interval */

    f_left = f(x_left);

    f_right = f(x_right);

   

    /* If no change of sign occurs on the interval there is not a unique root. Searches for the unique root if there is one. */

    if (f_left * f_right > 0) /* Same sign */

    {

     *errp = 1;

     printf("\nMay be no root in [%.7f, %.7f]", x_left, x_right);

    }

    else

    {

     *errp = 0;

     /* Call recursive function */

     x_mid = find_root(x_right, x_left, f_right, f_left, x_mid, f_mid, epsilon, f, root_found);

    }

   

    /* If there is a root, it is the midpoint of [x_left, x_right] */

    return x_mid;

}
double g(double x)

{  

    /* Test function 5x - 2x + 3 */

    return (5 * pow(x, 3.0) - 2 * pow(x, 2.0) + 3);

}
double h(double x)

{

    /* Test function x - 3x - 8 */

    return (pow(x, 4.0) - 3 * pow(x, 2.0) - 8);     

}
double find_root(double x_right, double x_left, double f_right, double f_left, double x_mid, double f_mid, double epsilon, double f(double farg), int root_found)

{          

     /* Searches as long as interval size is large enough and no root has been found */

     if ((fabs(x_right - x_left) > epsilon) && !root_found)

     {

      /* Computes midpoint and function value at midpoint */

      x_mid = (x_left + x_right) / 2.0;

      f_mid = f(x_mid);

     

      if (f_mid == 0.0) /* Here is the root */

       root_found = 1;

      else if (f_left * f_mid < 0.0) /* Root in [x_left, x_mid] */

       x_right = x_mid;

      else /* Root in [x_mid, x_right] */

      {

       x_left = x_mid;

       f_left = f_mid;

      }

     

      /* Prints root and interval or new interval */

      if (root_found)

      {

       printf("\nRoot found at x = %.7f, midpoint of [%.7f, %.7f]", x_mid, x_left, x_right);

       return x_mid;

      }

      else

      {

       printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);

       /* Call recursive function */

       x_mid = find_root(x_right, x_left, f_right, f_left, x_mid, f_mid, epsilon, f, root_found);

      }

     }

     else

      return (x_mid + x_right) / 2.0;

}


The program should be returning a proper midpoint result that should be stored in the root variable in function main() but is instead returning a random number. For instance, if I were to enter interval endpoints -1.0, 1.0 and an error tolerance epsilon value of 0.001, I should be getting a root result of -0.7290039 but instead I am getting a result of 6.0000000. I am baffled as to why I am getting this random result. What could be wrong? :eh:/>

Is This A Good Question/Topic? 0
  • +

Replies To: Incorrect root value being returned in recursive bisection program

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3168
  • View blog
  • Posts: 9,581
  • Joined: 05-May 12

Re: Incorrect root value being returned in recursive bisection program

Posted 02 April 2013 - 09:15 PM

Also posted:
http://forum.codecal...gram/#gsc.tab=0

The non-recursive versions of your code posted here:
http://www.cis.templ...ter%205/05.19.c
seems to work without any problems. Do you really need a recursive solution?

It looks like in 2011, you already had a non-recursive solution:
http://forum.codecal...tion/#gsc.tab=0
Was This Post Helpful? 1
  • +
  • -

#3 Yuriy M  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 43
  • Joined: 05-September 07

Re: Incorrect root value being returned in recursive bisection program

Posted 03 April 2013 - 08:34 AM

View PostSkydiver, on 02 April 2013 - 10:15 PM, said:

Also posted:
http://forum.codecal...gram/#gsc.tab=0

The non-recursive versions of your code posted here:
http://www.cis.templ...ter%205/05.19.c
seems to work without any problems. Do you really need a recursive solution?

It looks like in 2011, you already had a non-recursive solution:
http://forum.codecal...tion/#gsc.tab=0

The textbook question that I am currently on has asked me to revisit this program and provide a recursive function to it. I've completed the recursive function programming but now the last piece of output before program termination just won't print the correct result and I am dumbfounded as to why.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3168
  • View blog
  • Posts: 9,581
  • Joined: 05-May 12

Re: Incorrect root value being returned in recursive bisection program

Posted 03 April 2013 - 08:28 PM

Turn up the warnings on your compiler. If it's a pretty modern compiler, it should be warning you that there are code paths inside find_root() that do not return a value.

If you don't have a smart enough compiler, clean up the line spacing/indenting of your code. Tighten up the extra line breaks that are there. I think that on lines 177-197 you have a case where you don't return a value after making your recursive call.
Was This Post Helpful? 0
  • +
  • -

#5 Yuriy M  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 43
  • Joined: 05-September 07

Re: Incorrect root value being returned in recursive bisection program

Posted 04 April 2013 - 08:25 PM

All right. After fiddling around with the program, I finally found the solution. All it took was a midpoint calculation for "x_mid" to be done just prior to the recursive call to function find_root(). Here is the completed version.
#include <stdio.h>
#include <math.h>

double bisect(double, double, double, double(double), int *);                                 /* Implements bisection method for finding a root of a function */
double g(double);                                                                             /* Test function 'g' */
double h(double);                                                                             /* Test function 'h' */
double find_root(double, double, double, double, double, double, double, double(double), int);/* Finds root or new interval of a function */

int main(void)
{
    /* Declare variables */
    double x_left,                                                                            /* Left endpoint of interval */
           x_right,                                                                           /* Right endpoint of interval */
           epsilon,                                                                           /* Error tolerance value */
           root;                                                                              /* The root of the function */
    int    error;                                                                             /* The error value used in case of no root */
    
    /* Get endpoints and error tolerance from user */
    printf("\nEnter interval endpoints> ");
    scanf("%lf%lf", &x_left, &x_right);
    printf("\nEnter tolerance> ");
    scanf("%lf", &epsilon);
    
    /* Use bisect function to look for roots of g and h */
    printf("\n\nFunction g");
    root = bisect(x_left, x_right, epsilon, g, &error);
    if (!error)
     printf("\n   g(%.7f) = %e\n", root, g(root));
     
    printf("\n\nFunction h");
    root = bisect(x_left, x_right, epsilon, h, &error);
    if (!error)
     printf("\n   h(%.7f) = %e\n", root, h(root));
    return 0;
}

double bisect(double x_left, double x_right, double epsilon, double f(double farg), int *errp)
{
    double x_mid,                                                                             /* Midpoint of interval */
           f_mid,                                                                             /* f(x_mid) */
           f_left,                                                                            /* f(x_left) */
           f_right;                                                                           /* f(x_right) */
    int    root_found = 0;                                                                    /* Value that determines found or unfound roots */
    
    /* Computes function values at initial endpoints of interval */
    f_left = f(x_left);
    f_right = f(x_right);
    
    /* If no change of sign occurs on the interval there is not a unique root. Searches for the unique root if there is one. */
    if (f_left * f_right > 0) /* Same sign */
    {
     *errp = 1;
     printf("\nMay be no root in [%.7f, %.7f]", x_left, x_right);
    }
    else
    {
     *errp = 0;
     /* Call recursive function */
     x_mid = find_root(x_right, x_left, f_right, f_left, x_mid, f_mid, epsilon, f, root_found); 
    } 
    
    /* If there is a root, it is the midpoint of [x_left, x_right] */
    return x_mid;
}

double g(double x)
{   
    /* Test function 5x - 2x + 3 */
    return (5 * pow(x, 3.0) - 2 * pow(x, 2.0) + 3);
}

double h(double x)
{
    /* Test function x - 3x - 8 */
    return (pow(x, 4.0) - 3 * pow(x, 2.0) - 8);      
}

double find_root(double x_right, double x_left, double f_right, double f_left, double x_mid, double f_mid, double epsilon, double f(double farg), int root_found)
{           
     /* Searches as long as interval size is large enough and no root has been found */
     if ((fabs(x_right - x_left) > epsilon) && !root_found)
     {
      /* Computes midpoint and function value at midpoint */
      x_mid = (x_left + x_right) / 2.0;
      f_mid = f(x_mid);
      
      if (f_mid == 0.0) /* Here is the root */
       root_found = 1;
      else if (f_left * f_mid < 0.0) /* Root in [x_left, x_mid] */
       x_right = x_mid;
      else /* Root in [x_mid, x_right] */
      {
       x_left = x_mid;
       f_left = f_mid;
      }
      
      /* Prints root and interval or new interval */
      if (root_found)
      {
       printf("\nRoot found at x = %.7f, midpoint of [%.7f, %.7f]", x_mid, x_left, x_right);
       return x_mid;
      }
      else
      {
       printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
       x_mid = (x_left + x_right) / 2.0;
       /* Call recursive function */
       x_mid = find_root(x_right, x_left, f_right, f_left, x_mid, f_mid, epsilon, f, root_found);
      }
     }
     
     return x_mid;
}


Thanks for your help, Skydiver. :)/>
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1