/* File: sqrt3.c

Calculate the square root by successive approximation.

Use assert() to monitor our invariant.

*/

#include <stdio.h>
#include <math.h>
#include <assert.h>

#define EPSILON 0.000001

int main() {
   double x, lowEnd, highEnd ;
   double newGuess ;

   printf("This program computes the square root of x.\n") ;
   printf("x =? ") ;
   scanf("%lf", &x) ;

   if (x < 0) {
      printf("Negative numbers do not have a square root!\n") ;
      return 0 ;   // exit from main()
   }

   lowEnd = 0.0 ;
   highEnd = x ;

   // invariant: lowEnd * lowEnd <= x && x <= highEnd * highEnd

   while ( highEnd - lowEnd > EPSILON) {

      //printf("\nhighEnd = %.8f, lowEnd = %.8f\n", highEnd, lowEnd) ;
      assert ( lowEnd * lowEnd <= x && x <= highEnd * highEnd ) ;

      newGuess = (highEnd + lowEnd) / 2.0 ; 

      if (newGuess * newGuess == x) {
         printf("%.8f is the answer! lucky guess!\n", newGuess) ;
         highEnd = newGuess ;
         lowEnd = newGuess ;

      } else {
         if (newGuess * newGuess > x) {
            printf("%.8f is too big\n", newGuess) ;
            highEnd = newGuess ;
         } else {
            printf("%.8f is too low\n", newGuess) ;
            lowEnd = newGuess ;
         }
      }
   
   }

   printf("\n\nThe square root of %.8f is approximately %.8f (within %.8f)\n",
     x, (highEnd + lowEnd)/2.0, EPSILON) ;

   printf("The \"real\" answer is: %.8f\n", sqrt(x) ) ;
   return 0 ;
}