/* Bisection Method for Finding the Square Root of a Positive Number */

#include <stdio.h>

const double ACCURACY = 0.0001;  /* desired accuracy of result */

int
main (void)
{
  /* pre-conditions:  t will be a positive number
   * post-conditions:  code will print an approximation of the square root of t
   */
 
  double value;        /* we approximate the square root of this number */
  double left, right, midpoint;  /* root will be in interval [left,right] */

  /* for f(x) = x^2 - t, differences represent values 
     f(left), f(right), and f(midpoint) */
  double diffLeft, diffRight, diffMid;  

  int numAssigned; /* return value for user input from scanf */

  /* Getting started */
  printf ("Program to compute a square root\n");
  printf ("Enter positive number: ");
  numAssigned = scanf ("%lf", &value);

  /* Validate user input */
  if (numAssigned == 0) {
    printf ("Error: Unable to read number\n");
    return 1;
  } else if ( value <= 0) {
    printf("Error: A positive number is required; %lf was entered.\n", value);
    return 1;
  }
   
  /* Set up initial interval for the bisection method */
  left = 0;
  right = (value < 2.0 ? 2.0 : value );
   
  diffLeft = left*left - value;
  diffRight = right*right - value;

  /* Iterate interval shrinking until sufficiently small */
  while ( (right - left) > ACCURACY)
  {
    midpoint = (left + right) / 2.0;  /* midpoint of range [left,right] */

    diffMid = midpoint*midpoint - value;
    
    if (diffMid == 0.0) break;  /* stop loop if we have the exact root */
    
    if ((diffLeft * diffMid) < 0.0) {
      /* f(left) and f(mid) have opposite signs */
      right = midpoint;
      diffRight = diffMid;
    } else {
      left = midpoint;
      diffLeft = diffMid;
    }
  } // while
  
  printf ("The square root of %lf is approximately %lf\n", value, midpoint);
  return 0;
} // main