Finding square roots without sqrt() to .000001 precision

Question

I'm working on making a method that will calculate the square root of a supplied integer without using Math.sqrt(). I believe everything is working except for meeting the condition of the while loop.
As of right now perfect squares will work however non perfect squares seem to loop infinitely. I'm not sure how to get it meet the conditions of the loop to break and find the square root of a non perfect square to a precision of .000001.

public static double findSquareRoot(int value)
{
    value = Math.abs(value);
    double mid = value / 2.0, answer = 0;
    // loop until sqrt is found
    while (answer * answer != value)
    {
        // if middle value is sqrt
        if (mid * mid == value)
        {
            return mid;
        }
        // if middle value is too big to be sqrt
        else if (mid * mid > value)
        {
            mid = mid / 2.0;
            answer = mid;
        }
        // if middle value is too small to be sqrt
        else
        {
            mid = (mid + value) / 2.0;
            answer = mid;
        }
    }
    return answer;
}

It's the equality check. What you want to do is look at the difference being within your tolerance. — shawnt00, Aug 30 '19 at 03:28
something like `while ( Math.abs(value-(answer*answer)) > tolerance) ` — Subir Kumar Sao, Aug 30 '19 at 03:53
Related: https://stackoverflow.com/questions/588004/is-floating-point-math-broken — Code-Apprentice, Aug 30 '19 at 23:08
There is no such thing as '.000001 precision' in floating point. You can get slightly better, or slightly worse, depending on which negative power ot two gets used in the mantissa. — user207421, Sep 02 '19 at 04:41

score 1 · Answer 1 · answered Aug 30 '19 at 04:10

You need to check with given precision:

public static double findSquareRoot(int value)
{
    private static final double PRECISION = 0.000001;
    value = Math.abs(value);
    double mid = value / 2.0, answer = 0;
    // loop until sqrt is found
    while (Math.abs(answer * answer - value) < PRECISION)
    {
        // if middle value is sqrt
        if (Math.abs(mid * mid - value) < PRECISION)
        {
            return mid;
        }
        // if middle value is too big to be sqrt
        else if (mid * mid > value)
        {
            mid = mid / 2.0;
            answer = mid;
        }
        // if middle value is too small to be sqrt
        else
        {
            mid = (mid + value) / 2.0;
            answer = mid;
        }
    }
    return answer;
}

lovington · Answer 2 · 2019-08-31T20:17:57.640

-1

This should work for non perfect square. Basically, as @Andronicus indicated, you need to check against the precision in the while condition clause.

   private static double getSqrt(int x) { 
       final double PRECISION = 0.000001;

       x = Math.abs(x);
       double start = 1, end = (double )x, ans=0.0, mid = 0.0; 
       while (Math.abs(mid*mid - x)  > PRECISION) { 
           //use binary search
           mid = (start + end) / 2.0; 

           // continue to narrow the range 
           if (mid * mid < x) { 
               start = mid + 0.5; 
               ans = mid; 
           } 
           else  {
               end = mid - 0.5;
           }    
       } 
       return ans; 
   }

edited Aug 31 '19 at 20:17

answered Aug 30 '19 at 21:18

lovington

21
6

Float offers very poor precision; using it for this kind of mathematical algorithm is not recommended. – Neil Coffey Aug 30 '19 at 22:38
True. I agree. the code is meant to illustrate the point of how precision can be checked. I will change the data type to double. – lovington Aug 31 '19 at 20:14

Finding square roots without sqrt() to .000001 precision

2 Answers2