/* Bisection Method for Finding the Square Root of a Positive Number */
	  
#include <stdio.h>
#include <assert.h>

/* square_root - Calculate the square root of a positive number
 *
 *  pre-conditions:  t>0
 *  post-conditions:  returns m such that |m*m - t| <= accuracy
 */
double
square_root (double t)
{
  double a, b, m;  /* desired root will be in interval [a,b] with midpoint m */
  double fa, fb, fm;  /* values f(a), f(b), f(m), resp., for f(x) = x^2 - t, */
  double accuracy = 0.0001;  /* desired accuracy of result */

  /* Set up initial interval for the bisection method */
  a = 0;
  b = ( t > 2.0 ? 2.0 : t);

  fa = a*a - t;
  fb = b*b - t;

  /* Iterate interval shrinking until sufficiently small */
  while (b - a > accuracy)
  {
    assert (fa * fb < 0);  /* x^2 - t must have opposite signs at a and b */
      
    m = (a + b) / 2.0;  /* m is the midpoint of [a,b] */
    fm = m*m - t;
    if (fm == 0.0) break;  /* stop loop if we have the exact root */
      
    if ((fa * fm) < 0.0) { /* f(a) and f(m) have opposite signs */
      b = m;
      fb = fm;
    } else {
      a = m;
      fa = fm;
    }
  } // while

  return t;
  
} // square_root


/* Prompt the user for a number, calculate and print its square root */
int
main (void)
{
  double square;        /* we approximate the square root of this number */
  double root;
  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", &square);

  /* Verify user input */
  if (numAssigned == 0) {
    printf ("Error: Unable to read number\n");
    return 1;
  } else if (square <= 0) {
    printf ("Error: A positive number is required; %lf was entered.\n", square);
    return 1;
  }

  /* Calculate result */
  root = square_root (square);
  printf ("The square root of %lf is approximately %lf\n", square, root);

  return 0;
} // main