/* 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;
  if (t > 2.0)
    b = 2.0;
  else
    b = t;

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

  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 ()
{
  double square;        /* we approximate the square root of this number */
  double root;
  /* Getting started */
  printf ("Program to compute a square root\n");
  printf ("Enter positive number: ");
  scanf ("%lf", &square);

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

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

  return 0;
}