Cfrtjryk

I am working on below problem:

Given an integer, how do you find the square root of the number
without using any built-in function?

  private static double computeSquareRootBinarySearch(double x, double precision) {

    double start = 0;

    double end = x / 2 + 1;

    double mid = (start + ((end - start) / 2));

    double prevMid = 0;

    double diff = Math.abs(mid - prevMid);



    while ((mid * mid != x) && (diff > precision)) {

      if (mid * mid > x) {

        end = mid;

      } else {

        start = mid;

      }

      prevMid = mid;

      mid = (start + end) / 2;

      diff = Math.abs(mid - prevMid);

    }

    return mid;

  }

I came up with above binary search algo but wanted to see if there is any optimization I can do in above algorithm?

• It is unlikely that mid * mid would ever be equal to x, so the opportunistic mid * mid != x consumes more cycles than it may save. I recommend to drop it entirely.




• The convergence rate is not the best. Your algorithm adds (approximately) one bit of precision per iteration. Compare it to a classic Newton-Raphson, which doubles the amount of correct bits per iteration.




• As mentioned in the comment, without using any built-in function part of assignment rules out using Math.abs.




• You may want to check the input for correctness: both x and precision must be positive.