/**
 * A divide-and-conquer square root algorithm.  Written as part of 
 * the answer key for HW3 in CSC152.2000S.  Note that the main method 
 * was copied nearly verbatim from SquareRoot.java, which was given 
 * in HW3.  Thanks to Paul Bailey for catching an error in the 
 * preconditions.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 2000
 */
public class NewRoot
{
  // +------+----------------------------------------------------
  // | Main |
  // +------+

  public static void main(String[] args) {
    double val = 0;
    long n = 0;
    double root;
    SimpleOutput out = new SimpleOutput();   
    // Sanity check.
    if (args.length != 2) {
      out.println("Usage: java NewRoot value n");
      System.exit(1);
    }
    // Get the value.
    try { val = (new Double(args[0])).doubleValue(); }
    catch (NumberFormatException e) {
      out.println("The steps must be a number.");
      System.exit(2);
    } // catch
    // Get the n.
    try { n = (new Long(args[1])).longValue(); }
    catch (NumberFormatException e) {
      out.println("N must be an integer.");
      System.exit(3);
    } // catch
    // Verify that the preconditions are met.
    if (val < 1) {
      out.println("The value must be at least zero.");
      System.exit(4);
    } // if (val < 0)
    if (n <= 0) {
      out.println("N must be positive.");
    } // if (n <= 0)
    // Compute the square root
    root = sqrt(val,n);
    out.println("The square root of " + val + " is " + root);
    out.println("Java says that it is " + Math.sqrt(val));
  } // main(String[])


  // +---------+-------------------------------------------------
  // | Helpers |
  // +---------+

  /**
   * Compute the square root of val to accuracy 1/n.
   * Pre: (1) val >= 1
   *      (2) n >= 1
   *      (3) The square root of val can be represented.
   * Post: (1) Returns a value v such that |v-sqrt(val)| &lt; 1/n.
   */
  public static double sqrt(double val, long n) {
    // Compute 1/nth of the range of possible values
    double accuracy = 1.0/((double) n);
    // Set up a lower bound and an upper bound for the root
    double lowerBound = 0;
    double upperBound = n;
    // Determine a midpoint
    double guess = (lowerBound + upperBound)/2;
    // Keep going until things are accurate enough.
    while (upperBound-lowerBound > accuracy) {
      // If the guess is correct, then we're done.
      if (guess*guess == val)
        return guess;
      // If the guess is too small then
      else if (guess*guess < val) {
        // Make it the lower bound of possible values
        lowerBound = guess;
      }
      // Otherwise, the guess is too large
      else {
        // So make it the upper bound of possible values.
        upperBound = guess;
      }
      // Move on to the next guess
      guess = (lowerBound + upperBound) / 2;
    } // while
    // That's it, we're done
    return guess;
  } // sqrt(double, long)
} // class NewRoot