Find the square root of the number without using any built-in function?

Question

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?

Answer 1

• 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.