2
\$\begingroup\$

I'm working on a program to program the bisection method: https://www.calculushowto.com/bisection-method/

I know there's questions similar to this one but I want to see if my own one works.

double func(double x) {
    return x * x - 3 * x - 1;
}
    
double bisect(double (*f)(double), double a, double b, double e) {
    double mid = (a + b) / 2;
    while (abs(mid) > e) {
        if (f(mid) < 0) {
            mid = a;
        } else {
            mid = b;
        }
    }
      
    return mid;       
}

func() is the function I'm using to test the bisection method. In the other function, a is the left point, b is the right point and e is the error bound.

Any mistakes that I didn't catch?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$
  • You seem to assume that there is a root between a and b. If it is not the case, bisect will never terminate. Assuming that f is well-behaving, it would be prudent to test that f(a) and f(b) have different signs before proceeding.

    Also, consider the case f(a) > 0 && f(b) < 0

  • bisect doesn't find the approximation of the root. It finds an argument at which f is reasonably small. It could be quite far from the root. A prudent termination condition is b - a < e.

  • a + b may overflow, and then all bets are off. Consider mid = a + (b - a)/2.

\$\endgroup\$
3
  • \$\begingroup\$ a and b are floating-point numbers, which makes the overflow less likely. But does mean we ought to be checking for non-finite values (infinities and NANs) before we do any arithmetic. \$\endgroup\$ Feb 3, 2021 at 8:50
  • \$\begingroup\$ "bisect will never terminate." --> Likely the integer truncation of abs(mid) will readily cause the loop to quit. \$\endgroup\$ Feb 5, 2021 at 23:33
  • \$\begingroup\$ Given a,b are unordered, b - a can overflow like a + b. Alternate a/2 + b/2; \$\endgroup\$ Feb 5, 2021 at 23:35
0
\$\begingroup\$

Any mistakes that I didn't catch?

Bug: wrong function

abs() is for int. Use fabs(). abs(mid) is a problem when mid out of int range and not mathematical the desired algorithm as it truncates. Slower to converting to and from int too.

double mid = (a + b) / 2;
// while (abs(mid) > e) {
while (fabs(mid) > e) {

Subtle

(x - 3)*x - 1; is more computational stable than x * x - 3 * x - 1.

\$\endgroup\$

Your Answer

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