content: package math;
  
  public class CalculateRoot {
  
  
      /*
       *
       * Given a double number, write a function to calculate its square root.
       * Eg: Square root of 16 is 4 (4 x 4 = 16)
       *
       * Runtime Complexity:
       * Logarithmic, O(logn)
       *
       * Memory Complexity:
       * Constant, O(1)
       *
       * Set low = 0 and high = 1 + n / 2
       *   while True:
  	 *              mid = (low + high) / 2
  	 *               square = mid * mid
       *               If square is equal to 'n' then
       *                       return mid (mid is the square root)
       *               Else If square is less than n:
       *                       low = mid (square root lies in upper half i.e. between mid and high)
       *               Else If square is greater than n then
       *               high = mid (square root lies in lower half i.e. between low and mid)
       *
       * */
  
      private static final double EPSILON = 0.00001;
  
      protected static double squareRootIterative(double num) {
          double low = 0;
  
  
          // square root can never be more than
          // half of number except if number is <= 1
          // so square root of any number always lie
          // between 0 and 1 + (num / 2)
          double high = 1 + num / 2;
  
          while (low < high) {
  
              double mid = (low + high) / 2;
              double sqr = mid * mid;
  
              // we can't do a == b for doubles because
              // of rounding errors, so we use error threshold
              // EPSILON. Two doubles a and b are equal if
              //  abs(a-b) <= EPSILON
  
              double diff = Math.abs(num - sqr);
  
              if (diff <= EPSILON) {
                  return mid;
              }
  
              if (sqr < num) {
                  low = mid;
              } else {
                  high = mid;
              }
          }
  
          return -1;
      }
  
  
      public static void main(String[] args) {
          int x = 100;
          double res1 = squareRootIterative(x);
          System.out.println("Square Root: " + res1);
      }
  }
  