0
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ If you can use Math.abs(), then why not also use Math.sqrt()? \$\endgroup\$ Commented Nov 13, 2018 at 21:24
  • \$\begingroup\$ Agree with @200_success, try to compute the Abs(...) by yourself. Otherwise, why theses operations in the mid and diff initialization? And, it's not stated that the result must be the closest greater possible. So, why + 1 in the end init? \$\endgroup\$
    – Calak
    Commented Nov 13, 2018 at 21:41
  • \$\begingroup\$ a really efficent way to calculate approximations would be to use the Secant method (see en.wikipedia.org/wiki/Secant_method) \$\endgroup\$ Commented Nov 14, 2018 at 6:07

1 Answer 1

2
\$\begingroup\$
  • 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.

\$\endgroup\$
1
  • \$\begingroup\$ mid*mid can be x ..Eg. 2*2=4 \$\endgroup\$ Commented Nov 21, 2018 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.