4
\$\begingroup\$

As a programming exercise I made a square root function in C# using recursion, here is the function:

static double root(double x, double increment, double num)
{
    num += increment;
    if ((num * num).ToString() == x.ToString())
        return num;
    else if (num * num < x)
        return root(x, Math.Abs(increment), num);
    else if (num * num > x)
        return root(x, Math.Abs(increment / 2) * -1, num);
    else
        return double.NaN;
}

static double sqroot(double x)
{
    return root(x, 10, 0);
}

It is able to do int.MaxValue without a problem, but my question is, how can this be improved?

\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

A couple of things.

Is the string conversions really necessary just for comparing 2 doubles?

Figuring the squared value on the fly seems to lead to a bit of repetition

Also, optional parameters make the initial calling simpler.

static double root(double x, double increment = 10, double num = 0)
{
    num += increment;
    double sqrdValue = num * num;
    if (sqrdValue == x)
        return num;
    else if (sqrdValue < x)
        return root(x, Math.Abs(increment), num);
    else if (sqrdValue > x)
        return root(x, Math.Abs(increment / 2) * -1, num);
    else
        return double.NaN;
}

Since it appears that integers will introduce rounding errors, you filter for that by checking if the difference is less than or equal to 0.000000000000001, instead of just equal to, which gives the same degree of accuracy in the final answer as the built-in sqrt method of the Math class.

static double root(double x, double increment = 10, double num = 0)
{
    double maxError = 0.000000000000001;
    num += increment;
    double sqrdValue = num * num;
    if (Math.Abs(sqrdValue - x) <= maxError)
        return num;
    else if (sqrdValue < x)
        return root(x, Math.Abs(increment), num);
    else if (sqrdValue > x)
        return root(x, Math.Abs(increment / 2) * -1, num);
    else
        return double.NaN;
}
\$\endgroup\$
7
  • \$\begingroup\$ Yes you need to convert it to a string otherwise floating point rounding errors will make it not work; I've tried it without and it confused me just as much as you. \$\endgroup\$ Nov 3, 2016 at 0:27
  • \$\begingroup\$ What number are you passing that creates the rounding errors? \$\endgroup\$
    – user33306
    Nov 3, 2016 at 0:29
  • \$\begingroup\$ 13 doesn't work, not sure of other that don't, though. \$\endgroup\$ Nov 3, 2016 at 0:31
  • \$\begingroup\$ I added a fix for you to look at. \$\endgroup\$
    – user33306
    Nov 3, 2016 at 0:42
  • \$\begingroup\$ I just tried changing it from a double to a decimal and that also seems to work. \$\endgroup\$ Nov 3, 2016 at 1:48
1
\$\begingroup\$

Although I strongly agree with tinstaafl in that the use of ToString() is not very beautiful from a mathematical point of view the solution he provides is rather unstable due the first if-clause (Math.Abs(sqrdValue - x) <= maxError).

On my computer the following errors are found:

x = 0.000000000345; Wrong result

x = 13 or 0.000054635 or 54.635 Stack overflow

I haven't (had the time to) found a reliable solution, so it seems that ToString() is the best choice of stop-condition.

sqroot() is missing one important input check:

x >= 0 :

double sqroot(double x)
{
  if (x < 0.0)
     return double.NaN;

  return root(x, 10, 0);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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