Finding root of strictly monotonic function by bisection I need to find a root of strictly monotonic function f (only raising or only lowering). There is only a one root of a function.
If given range from a to b doesn't contain root (fabs(f(a)*f(b) is not lower or equal than 0), we need to change range, since the assumption is that there is a one root, so we need to move on x-axis to left or right and check again, if f(a).
If it is, then (f)*f(b) (e.g (-3)*2=-6, and that means there is a root between a and b).

I've made an solution and I would like to improve performance in terms of changing ranges (obviously adding +2 is not good for huge functions) vs halving ranges further, when finding f(c).


What would be the best strategy?
Also will there be any other problem to look on?
What can I do to avoid user epsilon to be smaller than DBL_EPSILON?
Any ideas to improve my code?




#include &lt;iostream&gt;
#include &lt;cmath&gt;

double f(double x) 
{
    //double y = std::pow(2, x) - 6;
    double y = x - 10000;
    return y;
}

bool isRaising(double a, double b)
{
    if (f(a) &gt; f(b)) return false;
    return true;
}

bool areBothNumbersPositive(double a, double b)
{
    if (f(a) &gt; 0 &amp;&amp; f(b) &gt; 0) return true;
    return false;
}

void moveLeft(double &amp;a, double &amp;b)
{
    b = a;
    a = a - 2;
}

void moveRight(double&amp; a, double&amp; b)
{
    a = b;
    b = b + 2;
}

void changeRanges(double &amp;a, double &amp;b) 
{
    if (!isRaising(a, b)) 
    {
        if (areBothNumbersPositive(a, b)) 
        {
            moveRight(a, b);
        }
        else
        {
            moveLeft(a, b);
        }
    }
    else
    {
        if (areBothNumbersPositive(a, b))
        {
            moveLeft(a, b);
        }
        else
        {
            moveRight(a, b);
        }
    }
}

double findRoot(double a, double b, double epsilon)
{
    if (epsilon &lt; DBL_EPSILON) epsilon = DBL_EPSILON;
    if (a == b) throw std::exception("Range must be higher than zero!");

    double c;
    if (std::fabs(f(a)) &lt; epsilon) return a;
    if (std::fabs(f(b)) &lt; epsilon) return b;

    while (f(a) * f(b) &gt; 0)
    {
        changeRanges(a, b);
    }
    if (std::fabs(f(a)) &lt; epsilon) return a;
    if (std::fabs(f(b)) &lt; epsilon) return b;
    do
    {
        c = (a + b) / 2;
        if (f(a) * f(c) &gt; 0) a = c;
        else b = c;
    } while (!(std::fabs(f(c)) &lt; epsilon));
    return c;
}

int main()
{
    //f(a) * f(b) &gt; 0
    std::cout &lt;&lt; findRoot(-100,  -300,   0.00000000001) &lt;&lt; std::endl;
    std::cout &lt;&lt; findRoot(100, 300, 0.00000000001) &lt;&lt; std::endl;
    std::cout &lt;&lt; findRoot(-300, -100,  0.00000000001) &lt;&lt; std::endl;
    std::cout &lt;&lt; findRoot(300, 100,  0.00000000001) &lt;&lt; std::endl;

    //f(a) * f(b) &lt;= 0
    std::cout &lt;&lt; findRoot(-100, 300, 0.00000000001) &lt;&lt; std::endl;
    std::cout &lt;&lt; findRoot(100, -300, 0.00000000001) &lt;&lt; std::endl;
    std::cout &lt;&lt; findRoot(300, -100, 0.00000000001) &lt;&lt; std::endl;
    std::cout &lt;&lt; findRoot(-300, 100, 0.00000000001) &lt;&lt; std::endl;
}
1. Use established terms to make your code more readable to others

In this case, use "increasing" instead of "raising". In such a simple context it is quite obvious what you mean by "raising", but you would be surprised how much effort and how many misunderstandings you can save by using existing, well-known terms.



2. Give clear, unambiguous names to functions

When I see a function areBothNumbersPositive(double a, double b), I assume it returns a &gt; 0 &amp;&amp; b &gt; 0. A more suitable name would be areBothFuncValuesPositive(double a, double b), even though it's a bit longer.



3. Don't return true or false based on the value of a boolean expression, return the expression directly

bool isIncreasing(double a, double b)
{
    return f(a) &lt; f(b);
}

bool areBothFuncValuesPositive(double a, double b)
{
    return f(a) &gt; 0 &amp;&amp; f(b) &gt; 0;
}




4. Duplicate code in chageRanges can be reduced

void changeRanges(double &amp;a, double &amp;b) 
{
    if (isIncreasing(a, b) == areBothFuncValuesPositive(a, b))
    {
        moveLeft(a, b);
    }
    else
    {
        moveRight(a, b);
    }
}


Although I must admit, this seems a bit confusing. Maybe it would be a good idea to define a function which would figure out whether to go left or right, and then use this function in the if. This might be an overkill in this simple case, but is quite commonly used with more complex boolean expressions.

bool shouldMoveLeft(double a, double b)
{
    return (isIncreasing(a, b) &amp;&amp; areBothFuncValuesPositive(a, b))
         ||(isDecreasing(a, b) &amp;&amp; areBothFuncValuesNegative(a, b));
}

void changeRanges(double &amp;a, double &amp;b) 
{
    if (shouldMoveLeft(a, b))
    {
        moveLeft(a, b);
    }
    else
    {
        moveRight(a, b);
    }
}




5. Use functions where appropriate

Functions serve two main purposes: 1) code reuse; 2) conceptual abstraction. Even if you don't reuse them, they can make code more readable. For example, when you calculate f(a) * f(b) &gt; 0, what you really want to know is whether the function has the same sign at both values, and neither f(a) nor f(b) are zero.

bool areBothFuncValuesNonzeroSameSign(double a, double b)
{
    return f(a) * f(b) &gt; 0;
}


An even better idea would be to introduce the concept of a sign, and then build upon it (I copied the sign function from this SO answer).

template &lt;typename T&gt; int sign(T val) {
    return (T(0) &lt; val) - (val &lt; T(0));
}

bool areBothNumbersSameSign(double x, double y)
{
    return sign(x) == sign(y);
}

bool areBothNumbersNonzero(double x, double y)
{
    return x != 0 &amp;&amp; y != 0;
}

bool areBothFuncValuesNonzeroSameSign(double a, double b)
{
    const double
        fa = f(a),
        fb = f(b);

    return areBothNumbersNonzero(fa, fb) &amp;&amp; areBothNumbersSameSign(fa, fb);
}


This is not as succinct and elegantly clever as your original code. But imagine it wasn't a single line, but an entire function / class / project written in such a clever way. Then you would likely have a bit of trouble understanding it when you come back to it after some time. It would be even more trouble for someone else who has never seen your code before and now has to understand it, because you don't work at the company anymore and they inherited your code, or because they are extending your project, using your library, etc. By keeping your code simple and "stupid", you make it more readable and accessible to more people, and therefore, more maintainable.

Another two important aspects of software, besides readability and maintainability, are composability and reusability. Like readability and maintainability, these two are related. The functions sign, areBothNumbersSameSign and areBothNumbersNonzero are quite generic, so they are easily combined together (composed). This improves their reusability. Make your functions as generic as possible, so they can be reused later in different contexts, and composed to form larger abstractions. This includes the use of generic types (templates), as in the sign function. Making the function closely tailored for one specific use case prevents it from being used in other cases. You can observe that the function areBothFuncValuesNonzeroSameSign can only be used in the context of the function f, since it depends on it. We can decompose its functionality into two logically distinct parts: 1) calculating the values f(a), f(b); and 2) checking if the computed values are both non-zero and have the same sign.

bool areBothNumbersNonzeroSameSign(double x, double y)
{
    return areBothNumbersNonzero(x, y) &amp;&amp; areBothNumbersSameSign(x, y);
}

bool areBothFuncValuesNonzeroSameSign(double a, double b)
{
    return areBothNumbersNonzeroSameSign(f(a), f(b));
}


Again, this is just a simple example. But as the code grows bigger and the functionality gets more complex, such refactoring is necessary, although very often neglected.



6. Changing range in moveLeft and moveRight

As you pointed out, it is not ideal to use a constant (2) when adjusting the range. The first naive idea that would come to my mind is to simply shift the range, without changing its size.

void moveLeft(double &amp;a, double &amp;b)
{
    const double diff = b - a;
    b = a;
    a = a - diff;
}

void moveRight(double&amp; a, double&amp; b)
{
    const double diff = b - a;
    a = b;
    b = b + diff;
}


But, as you said, this is not very efficient. What you can do is increase the size of the range exponentially. I think (but I'm not sure), that this would converge more quickly on average.

void moveLeft(double &amp;a, double &amp;b)
{
    const double diff = b - a;
    b = a;
    a = a - diff*2;
}

void moveRight(double&amp; a, double&amp; b)
{
    const double diff = b - a;
    a = b;
    b = b + diff*2;
}




Note that I have not tested any of this, so I can't guarantee it works.