# Solving for the zero of an arbitrary function

This methods solves for the zero of an arbitrary function using the Bisection Method. It works as desired, but I want to know if the code can be improved or made more readable and if I'm properly dealing with the various error conditions that might arise.

/// <summary>
/// Finds the input value of a function such that the output is zero within the range of min and max
/// </summary>
/// <param name="function">The function to zero</param>
/// <param name="min">The lower bound of the "zero search"</param>
/// <param name="max">The upper bound of the "zero search"</param>
/// <param name="counter">The amount of iterations to convergence</param>
/// <param name="eps">Desired precision</param>
/// <returns>An input value such that 'function' returns 0 zero within the desired precision eps</returns>
public static double Zero(this Func<double, double> function, double min, double max, out int counter, double eps = .001) {
double lowerBound = min,
upperBound = max;
counter = 0;
double range = double.MaxValue;
double tryIndex = double.MinValue;
double tryEval = double.MinValue;
while (Math.Abs(tryEval) > eps && counter < 10000) {
counter++;
range = upperBound - lowerBound;
double maxEval = function(upperBound);
double minEval = function(lowerBound);
bool signMax = (maxEval > 0);
bool signMin = (minEval > 0);
if (signMax == signMin) {
throw new Exception("Failed to converge");
}
tryIndex = lowerBound + (range / 2);
tryEval = function(tryIndex);
bool trySign = tryEval > 0;
if (trySign == signMax) {
upperBound = tryIndex;
} else lowerBound = tryIndex;
}
return tryIndex;
}

-
so what exactly is your problem with how this code looks? What should we keep a close eye on when reviewing? What's the overall plan? –  Vogel612 Aug 14 '14 at 13:54
Please note that this doesn't find zeroes of arbitrary functions. Only arbitrary continuous functions, which is a small subset of all functions. –  progo Aug 15 '14 at 6:05

### Wall of declarations

double lowerBound = min,
upperBound = max;
counter = 0;
double range = double.MaxValue;
double tryIndex = double.MinValue;
double tryEval = double.MinValue;


Nobody likes being greeted by a wall of declarations like that. Let's see what can be done to reduce them.

lowerBound and upperBound merely rename the parameters. You could just use min and max directly everywhere.

counter is strongly related to the loop. You could write the loop as

for (counter = 0; Math.Abs(tryEval) > eps && counter < 10000; counter++)
{
…
}


range is also local to the loop, and should be declared inside the loop. It's also annoying that it's initialized on the 4th line of the function, redefined on the 9th line, and used 17th line. In fact, I wouldn't bother making a variable for it at all:

tryIndex = lowerBound + (min - max) / 2;


In general, you have a lot of expressions that don't need to be assigned to variables.

### Loop structure

Initializing tryIndex and tryEval to double.MinValue is a code smell. First of all, you should probably prefer double.NaN. Secondly, it raises the question, under what circumstances might double.MinValue "leak" out as a result? It's worth restructuring the program to avoid having those special values at all.

Restructuring the program will also reveal that there are two possible error conditions: failure to converge because the two endpoints evaluate to the same sign, and failure to converge because it took too many iterations.

public static double Zero(this Func<double, double> function, double min, double max, out int counter, double eps = .001)
{
for (counter = 0; counter < 10000; counter++)
{
bool signMax = (function(max) > 0);
if ((function(min) > 0) == signMax)
{
// Same sign
throw new Exception("Failed to converge (same sign)");
}

double tryIndex = min + (max - min) / 2;
double tryEval = function(tryIndex);
if (Math.Abs(tryEval) <= eps)
{
return tryIndex;
}
else if ((tryEval > 0) == signMax)
{
max = tryIndex;
}
else
{
min = tryIndex;
}
}
throw new Exception("Failed to converge (too many iterations)");
}

-

with this part of the code you could shorten it up quite a bit.

    double maxEval = function(upperBound);
double minEval = function(lowerBound);
bool signMax = (maxEval > 0);
bool signMin = (minEval > 0);
if (signMax == signMin) {
throw new Exception("Failed to converge");
}


Here is what I would do with this

if ((function(upperBound) > 0) == (function(lowerBound) > 0)) {
throw new Exception("Failed to converge");
}


This eliminates 4 variables, getting straight to the point of the whole if statement.

After looking at your code some more I realized that you are using the boolean variables, let's change this a little bit and still use the booleans.

bool signMax = (function(upperBound)) > 0;
bool signMin = (function(lowerBound)) > 0;

if (signMax == signMin) {
throw new Exception("Failed to converge");
}


And then down here:

    tryIndex = lowerBound + (range / 2);
tryEval = function(tryIndex);
bool trySign = tryEval > 0;
if (trySign == signMax) {
upperBound = tryIndex;
} else lowerBound = tryIndex;


Don't one line the else block, it is not pretty or easy to read

tryIndex = lowerBound + (range / 2);
tryEval = function(tryIndex);
bool trySign = tryEval > 0;
if (trySign == signMax) {
upperBound = tryIndex;
} else {
lowerBound = tryIndex;
}


you didn't do it with the if statement either, so be consistent with your coding practices.

And don't do this either

double lowerBound = min,
upperBound = max;


this is the only place that you did this, easy solution is don't do this, it's not pretty a lot of people don't like it, neither do I.

double lowerBound = min;
double upperBound = max;

-
"This eliminates 4 variables, saving memory" - this isn't true for even the most trivial optimizing compiler and certainly not for the C# JIT. I wouldn't nitpick such a little detail, but I've seen people inline everything to "optimize code" which I guess originates with such sayings. –  Voo Aug 14 '14 at 21:37
@Voo maybe I used the wrong terminology, there are less calls and assignments when those 2 variables are removed (I added the 2 booleans back in after I read more of the question), Less Typing, Less Code, less assigning variables, less confusing trying to follow the flow of data, etc. –  Malachi Aug 14 '14 at 21:54
Oh I agree that the two variables don't really make the code clearer, just the justification of "using less memory" could start people down a bad road. –  Voo Aug 14 '14 at 22:00
@Voo I removed that statement. –  Malachi Aug 14 '14 at 22:02

I would replace maxEval and minEval with the function invocation. I don't think they add much value.

Probably replacing the while loop with recursive calls could help you express better the nature of the problem and it could simplify the code. C# compiler does not perform tail-call optimisation so you should be careful because recursion could cause a stack overflow.

I would define range in the body of the loop, so you can get rid of its assignment to MaxValue.

Finally, I'd move the logic to compute the bounds for the next iteration to a separate function

-
With recursive calls, you've got to be careful about stack overflows, though the max 10000 iterations would largely mitigate this. And the counter is presumably there to say how many iterations it took (it's an out parameter), though I'm not sure what the point of that is. –  Ben Aaronson Aug 14 '14 at 14:13
You're right. I'll edit my answer. –  mariosangiorgio Aug 14 '14 at 14:15
@Ben 10000 method invocations could easily overflow the stack. A single stack frame should be around 100 bytes give or take, so 10k calls would put it at around 1MB which is the standard stack size for 64bit .NET iirc. –  Voo Aug 14 '14 at 21:42

You could declare all your double variables the way you did it for the first 2, you just need to move counter out like this.

counter = 0;
double lowerBound = min,
upperBound = max,
range = double.MaxValue,
tryIndex = double.MinValue,
tryEval = double.MinValue;


Also, you should never throw Exception, but a derived exception (say... InvalidOperationException, NotSupportedException maybe ArithmeticException in your case)

-