0
double _sqrt(double n)
{
    double sqrt = 0, c = 0, prec = 1;

    for (;; sqrt += prec) //increments sqrt per precision
    {
        c = sqrt * sqrt;
        if (c == n)
        {
            return sqrt;
        }
        if (c > n) // if square is greater then..
        {
            sqrt -= prec; // decrement squareroot by previous precision
            prec *= 0.1; // increase precision eg. 1, 0.1, 0.01, 0.001 .....INF
        }
    }
}

This is the square root function that I've done. It works for some numbers but for others its just blank, doesn't return a thing. Where am I getting this wrong?

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
D_W
  • 39
  • 5
  • 1
    Not all of your paths in that function return a value, so you have _undefined behavior_. Anything can happen. – πάντα ῥεῖ Nov 20 '22 at 17:20
  • 1
    Your compiler should have warned that not all control paths return a value. – drescherjm Nov 20 '22 at 17:20
  • 8
    Comparing doubles for exact equality rarely works. You need to compare the absolute difference against a tolerance to detect "close enough". – Retired Ninja Nov 20 '22 at 17:21
  • 5
    `if (c == n)` is problematic in floating point math. You may want to use some epsilon value here. – drescherjm Nov 20 '22 at 17:21
  • 2
    Do not tag C for C++ questions. – Eric Postpischil Nov 20 '22 at 17:22
  • 1
    Voted to reopen. The question is quite clear, and the problem is obviously not the result of a typo. The fix has been suggested in two comments, both of which have been upvoted. – Pete Becker Nov 20 '22 at 17:43
  • 2
    @πάνταῥεῖ -- I don't see it; the only return path is via the `return sqrt;` statement. The problem, of course, is the potential infinite loop, but that's not another return path. – Pete Becker Nov 20 '22 at 17:45
  • 1
    Floating point numbers are not exact, they are only an approximation of the real values (only so much bits to hold information in). That means that when you do calculations small errors are always present either in the representation of the number or the actual calculation. Also see : [is-floating-point-math-broken](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). And that is what @RetiredNinja's answer comes from. – Pepijn Kramer Nov 20 '22 at 18:11
  • 1
    If `double` had unlimited precision, that would take an infinite amount of time for all irrational roots and you would still have to settle for a "close enough" result. – molbdnilo Nov 20 '22 at 18:13
  • 1
    1) You have a possibly infinite loop; as Retired Ninja and drescherjm have said, `==` is not recommended for doubles. 2) Newton-Raphson is a better algorithm, and may well be faster. – rossum Nov 20 '22 at 18:28
  • Thanks everyone for the reply. So @rossum are there other algorithms for doing such comparisons that I should look for to get this problem solved. I'll check Newton-Raphson thanks! – D_W Nov 20 '22 at 18:35
  • See Retired Ninja's comment. You need to pick a small tolerance, delta, and compare against that: `if (abs(c - n) < delta) then ...` – rossum Nov 20 '22 at 20:38

2 Answers2

3

Your code has a few problems in it, the first one being that your code may infinitely loop as you try to have an infinite accuracy for a (possibly) irrational number. Although doubles do not have an infinite accuracy, I certainly wouldn't recommend trying to evaluate that function to that high of a degree of accuracy. The solution to this is to add some sort of 'precision' or 'epsilon' value (as mentioned in the comments below). Or even better to break out of the loop when increment becomes too small (as @Pete Becker suggested):

double _sqrt(const double& n)
{
    const double precision = 0.000001;
    double increment = 1.0, sqrt = 0.0;

    while (true)
    {
        if (increment <= precision)
            break;
        else if (sqrt * sqrt > n)
        {
            sqrt -= increment;
            increment *= 0.1;
        }
        else 
            sqrt += increment;
    }

    return sqrt;
}

You can of course do this with the standard library, using std::sqrt, but I assume you are doing this for fun.

If you are interested in other square root algorithms, there are some scary looking ones on Wikipedia here.

One that I personally like is Newton's Method, but this is for finding the root's of functions in general. An application of this for the square root function that I copied and modified from here is:

double _sqrt(const double& n)
{
    const double precision = 0.00001;
    double sqrt, x = n;

    while (true)
    {
        sqrt = 0.5 * (x + (n / x));

        if (std::abs(sqrt - x) < precision)
            break;

        x = sqrt;
    }

    return sqrt;
}
UniformSoup
  • 44
  • 5
2

What you are trying to do is similar to binary search. Mine main concern is with prec = 1; and sqrt += prec because once the sqrt is really big number the expression sqrt += prec will not change the sqrt in any way due to rounding and your for loop get stuck...

so what you should do is realize the starting prec value and how many times the precision should increase by prec *= 0.1;

for numbers |x|>1 we now that magnitude of sqrt(x) has half of integer bits that are needed for int(x) so we can derive the prec from that

y = log2(|x|)
prec = y*0.1

the log2 does not need to be real log2 you can simply take exponent and divide it by 2 and construct y as:

y = 2^((exponent_extracted_from_x>>1)+1)

for (|x|<=1) start with for example: prec = 0.5

Now the ending condition you are missing is to stop once sqrt stops changing for example:

...
for (sqrt0=sqrt-prec; sqrt!=sqrt0; sqrt0=sqrt,sqrt+=prec)
 {
 ... your original code ...
 }
return sqrt;
}

Also I do not see any sign handling (you know in case x<0)

for more info see:

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Really helpful. Thanks a lot. I could've made yours answer if I had two answer quotas. – D_W Nov 24 '22 at 12:37