How to use boost bisection?

Question

Yesterday I had problems with another boost functions but luckily you guys helped me to solve them. Today I would need to know how to use bisection function properly.

So here is how I think it should work but never the less it seems that I'm getting this also wrong. Okay so I would like to use:

template <class F, class T, class Tol>
 std::pair<T, T> 
 bisect(
    F f, 
    T min, 
    T max, 
    Tol tol);

from here but my problem is with tolerance because I don't know how to set it right. I've tried

double value = boost::math::tools::eps_tolerance<double>(0.00001);

and how to I return the value when the bisection has found ? Should the result be pair of numbers as std::pair in the function and after that just calculate min+max/2?

Thanks !

Causative

Answer 1

This is an example use of bisect. Consider solving the equation x^2 - 3x + 1 = 0:

struct TerminationCondition  {
  bool operator() (double min, double max)  {
    return abs(min - max) <= 0.000001;
  }
};

struct FunctionToApproximate  {
  double operator() (double x)  {
    return x*x - 3*x + 1;  // Replace with your function
  }
};

// ...
using boost::math::tools::bisect;
double from = 0;  // The solution must lie in the interval [from, to], additionally f(from) <= 0 && f(to) >= 0
double to = 1;
std::pair<double, double> result = bisect(FunctionToApproximate(), from, to, TerminationCondition());
double root = (result.first + result.second) / 2;  // = 0.381966...

EDIT: Alternatively, this is how you can use it with custom functions:

double myF(double x)  {
  return x*x*x;
}

double otherF(double x)  {
  return log(abs(x));
}

// ...
std::pair<double, double> result1 = bisect(&myF, from, to, TerminationCondition());
std::pair<double, double> result2 = bisect(&otherF, 0.1, 1.1, TerminationCondition());

Reina

I assume I can replace FunctionToApproximate() which ever function I want to use as long as it just returns a value ? Or do I just replace return xxx to call another function like return Eval() <= 0.000001; ? Anyway I just realized that I don't know how to test bisection using a clause e.g. x^2-3x+1=0 or is that even possible with this bisection function ? Thanks ! – Causative

To the first question - you can change FunctionToApproximate to anything that can be called with one double parameter and returns double. A cleaner way thugh is to replace xxx with your own function and keep FunctionToApproximate as is. To the second question - do you want to enter the clause as a string or have it hardcoded as a C++ expression? – Reina

To the second question, basically it doesn't matter is the clause string or hard coded at the moment. The purpose of the example clause is just to test that the bisection function works as it should. – Causative

Edited my answer to reflect your testing expression. – Reina

Thank you for your answer now I got the idea! Anyway I still have a one thing that bothers me. I need to call bisection in different situations and so I would like to pass a function to FunctionToApproximate() because I have a few different functions to solve different values. E.g I would like to pass eval(double t) or eval2(double t).. If I add double ValueToPass inside of struct FunctionToApproximate, I can pass the value as FunctionToApproximate.valueTopass = 2; right ? But how about with function ? – Causative

If you ensure that the various functions you use all take one double argument and return double, you can get rid of FunctionToApproximate and pass those directly to bisect. bisect accepts any function or class with overloaded () operator that meets this criteria. Edited my post to reflect that. – Reina

Thank you so much Charlie, you have definitely saved my day! – Causative

Now I'm implementing the bisection into my class... The test class worked great as your example but now I have a following problem. The functions that I want to pass to bisection looks like same as double otherF(double x) but I still get following error: ISO C++ forbids taking the address of an unqualified or parenthesized non-static member function to form a pointer to member function. Say ‘&class::Function’. As far I have searched I think I would need to make everything static but I really don't want to do that, so is there any other solution available ? – Causative

What about if I want to add a certain policy let's say 1e-10, can I call bisect just bisect(&otherF, 0.1, 1.1, TerminationCondition(),1e-10) or is there some other way to set the used precision when calculating the result ? – Causative

If you want member functions, you will need to use some wrapper such as Boost Bind to use them with bisection - the difference is that you need to pass the this pointer somehow. You can set the precision in TerminationCondition, it's the value 0.000001 in my answer. – Reina

Yeah bind solved the problem thanks! About precision, I was mixing precision value and precision location. I got that 0.000.. in your answer was the value but it seems that in certain functions I would need to use precision location also. In some cases the difference between min and max goes very small like 1e-13. I mean the exact value at that point is irrelevant and I could just pick max-min/2 at that point. Or maybe it doesn't matter and I just calculate the exact value anyway ? – Causative

The value is never exact - that's the point of midpoint algorithm. You can only get arbitrarily close to the solution, where arbitrarily means you can specify the precision. The value of 0.000001 means that at the current iteration, value of the function is already very close to 0 and is often a good tolerance value. – Reina

Is this right way to use and call bind and member function ? std::pair<double, double> result = bisect(boost::bind(&CLASS::Function,this, _1), 0.0, 1.000000, TerminationCondition()); Because for some reason this line crashes my program :( – Causative

somewhere inside the function what I'm calling because I got a following error: terminate called after throwing an instance of 'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::math::evaluation_error> >' what(): Error in function boost::math::tools::bisect<d>: No change of sign in boost::math::tools::bisect, either there is no root to find, or there are multiple roots in the interval (f(min) = -0.0032916729090909091). So I'm not sure should I perform binding some other way e.g. radmangames.com/programming/how-to-use-boost-bind. – Causative

I did post a new topic #8299607 I thought it may be easier to follow and comment. – Causative

Answer 2

Note that bisect also supports lambdas:

using boost::math::tools::bisect;
auto root = bisect
(
    [](double x){return x;},
    -1.0, 1.0,
    [](double l, double r){return abs(l-r) < 1e-8;}
);

Foliated