Square root function

Question

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?

Answer 1

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;
}

• Jason Heddle: 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.
• user33306: What number are you passing that creates the rounding errors?
• Jason Heddle: 13 doesn't work, not sure of other that don't, though.
• user33306: I added a fix for you to look at.
• Jason Heddle: I just tried changing it from a double to a decimal and that also seems to work.

Answer 2

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);
}