/*  A program that finds a root in a continuous function f by use of the
 *  bisection method.
 *  Programmer: Kurt Normark, Aalborg University, normark@cs.aau.dk.
 *  Version 0.9, September 15, 2010.
 */

#include <stdio.h>     // Include the standard output library
#include <math.h>      // Include the math library

/*  The function in which we search for a root */ 
double f (double x){
  /* (x - 5.0) * (x - 3.0) * (x + 7.0) */
  /* Return the value of x cubic minus x squre minus 41 times x plus 105 */
  return (x*x*x - x*x - 41.0 * x + 105.0); 
}

/*  Return whether x and y have the same sign */
int sameSign(double x, double y){
  return x * y >= 0.0;   // Return the value of x times y compared with 0.0
}

/*  Return the mid point in between x and y */ 
double middleOf(double x, double y){
  return x + (y - x)/2;  // Return the value of x plus (y - y)/2
}

/*  Is x considered to be very close to 0.0 */
int isSmallNumber(double x){
  return (fabs(x) < 0.0000001);             // Evaluate if x is smaller than 0.0000001
}   

/*  Search for a root of the continuous function f between the parameters l and u.
    A root is a double r for which f(r) is very close to 0.0.
    As a precondition it is assumed that the sign of f(l) and f(u) are different. */
double findRootBetween(double l, double u){
 while (!isSmallNumber(f(middleOf(l,u)))){  // if f applied on the middle of 
                                            // l and y is not a small number

   if(sameSign(f(middleOf(l,u)), f(u)))     // if f(middle) and f(u) have same sign
     u = middleOf(l,u);                     // u becomes the middle of l and u.
                                            // l is not changed.
   else 
     l = middleOf(l,u);                     // l becomes the middle of l and u.
                                            // u is not changed.
 }
 return middleOf(l,u);                      // the result is the middle of l and u.
}  

/*  A sample interactive driver of the root searching for f. */ 
int main (void){
  double x, y;        // x and y are doubles.
  int numbers;        // numbers is an int.

  do{
      printf("%s","Find a ROOT between which numbers: ");  // Prompt for an interval
      numbers = scanf("%lf%lf", &x, &y);                   // Input x and y.

      if (numbers == 2 && !sameSign(f(x),f(y))){           // Do we get both x and y, and
                                                           // are f(x) and f(y) are not of the same sign
          double solution = findRootBetween(x,y);          // Find the root of f between x and y
          printf("\nThere is a root in %lf\n", solution);  // Print the root
        }
      else if (numbers == 2 && sameSign(f(x),f(y)))        // We got x and y, but
                                                           // f(x) and f(y) are of the same sign
          printf("\nf must have different signs in %lf and %lf\n",
                 x, y);                                    // Print error message
      else if (numbers != 2)                               // We did not read x and y. Exit!
          printf("\nBye\n\n");
    }
  while (numbers == 2);                                    // Run the program as long 
                                                           // as we read x and y
  return 0;
}