// This program calculates square roots of numbers entered by the user.
// Specifically, the main program consists of a loop that reads a non-negative
// number from the user, prints its square root, and then asks the user
// if they want to do it again. This continues as long as the user wants.
// Note that this program consists of a couple of static methods, it doesn't
// use objects, as they really don't contribute much to a program this simple.

// History:
//   December 2003 -- Created by Doug Baldwin, based on an original in
//     Object Pascal.




import java.io.*;




class Root {




    private static final double INVALID = -1.0;			// Value that marks an invalid user input




    // The main method runs the loop that reads numbers from the user
    // and prints their (positive) square roots.
        
    public static void main( String args[] ) {

        try {

            BufferedReader keyboard = new BufferedReader( new InputStreamReader( System.in ) );

            String more = "y";

            while ( more.equalsIgnoreCase("y") ) {

                double number = readDouble( keyboard, "Number to find root of", 0.0, INVALID );
                

                // Compute and print the root. The lower and upper bounds for finding the
                // root are chosen based on the idea that any positive number's square
                // root lies between 0 and that number.
                
                System.out.println( "sqrt(" + number + ") = " + root( number, 0.0, number ) );

                System.out.print( "Another root (y/n)? " );
                more = keyboard.readLine();
            }
        }
        catch ( IOException error ) {
            // Abort if the program can't read from the keyboard
            System.out.println( "Unable to read from keyboard. Aborting..." );
        }
    }




    // root, the method that finds the positive square root of a number. This
    // method takes 3 parameters: the number to find the root of, a lower
    // limit that the root is known not to lie below, and an upper limit that
    // the root is known not to lie above. This method uses a divide-and-
    // conquer search for the root, based on the following recursive insight:
    // If the lower and upper bounds are very close to each other, then
    // either is a good approximation to the root. Otherwise, find the
    // number half way between the bounds, and see how its square compares
    // to the number. If greater, then the actual root lies between the lower
    // bound and that midpoint, if less then the actual root lies between
    // the midpoint and the upper bound.

    // Precondition: low <= sqrt(number) <= high

    private static double root( double number, double low, double high ) {

        final double TOLERANCE = 0.0001;		// How close is "very close"

        if ( high - low < TOLERANCE ) {
            return low;
        }
        else {

            double mid = ( low + high ) / 2.0;

            if ( mid*mid > number ) {
                return root( number, low, mid );
            }
            else if ( mid*mid < number ) {
                return root( number, mid, high );
            }
            else {					// Found the root exactly (very unlikely)
                return mid;
            }
        }
    }




    // readDouble, a method that reads a real number from the user and
    // returns it. Parameters to this method are the reader to read from,
    // a prompt to display, the lowest acceptable number, and the highest
    // acceptable number. Either the minimum or maximum numbers may be the
    // constant INVALID, in which case the corresponding bound isn't checked.
    // This method will keep prompting and reading until it gets a number in
    // the right range. If this function is completely unable to read from the
    // keyboard, it returns the minimum acceptable value as a default.

    private static double readDouble( BufferedReader keyboard, String prompt, double min, double max ) {

        double result = INVALID;

        while ( result == INVALID ) {

            System.out.print( prompt + ": " );

            try {
                String input = keyboard.readLine();
                result = Double.parseDouble( input );
            }
            catch ( NumberFormatException error ) {
                System.out.println( "Input must be a number. Try again..." );
            }
            catch ( IOException error ) {
                System.out.println( "Error reading keyboard. Using default value." );
                result = min;
            }

            if (  min != INVALID  &&  result != INVALID  &&  result < min  ) {
                System.out.println( "Input must be at least " + min + ". Try again..." );
                result = INVALID;
            }
            if (  max != INVALID  &&  result != INVALID  &&  result > max  ) {
                System.out.println( "Input must be no more than " + max + ". Try again..." );
                result = INVALID;
            }
        }

        return result;
    }
    
}