#include <library.h>

/*
  The same as the guessing game, except that the computer
  really doesn't know the answer this time.

  For the guessing game to work, it needs to be able to
  tell whether the guess is correct, too big, or too small.
  It wants to know if
                guess > sqrt(secret)
  without being able to use sqrt(). Fortunately, this test
  will always have the same result
                guess * guess > secret

  Eventually, we discovered that some numbers can't have their
  square roots completely accurately represented in digital
  form, and for them the loop never stops.

  Two solutions were found

  A.
     The range (difference between min and max) when measured
     relative to min and max themselves always gets below
     0.0000000000000001, and that is very accurate.

  B.
     Eventually the range stops shrinking

*/

double squareroot(const double secret)
{ cout << "The secret number is " << secret << "\n";
  double min = 0, max = secret+1;
  int count = 0;

//  For solution A, just use this.
  while ((max-min)/(max+min) > 1e-16)
//  For solution B, use this, plus the addition at the end of the loop
  double prev_diff = max - min + 1;
  while (true)
//  But not both

  { const double guess = (min + max) / 2;
    count = count + 1;

    if (guess * guess == secret)
      return guess;

    else if (guess * guess > secret)
      max = guess;

    else if (guess * guess < secret)
      min = guess;

//    For solution B, this is also needed
    double new_diff = max-min;
    if (new_diff >= prev_diff)
      break;
    prev_diff = new_diff;
//    but nothing extra is needed for solution A.
    }
  return (min+max)/2; }


void main()
{ cout << "number? ";
  const double num = read_double();
  const double result = squareroot(num);

  cout << "Result: " << result << "\n"; }