6
\$\begingroup\$

This code below is supposed to calculate the root of a function using bisection method. I am a newbie to Python, so I do not know how to raise errors. Also, I would like to have a general review on this algorithm design, where I could have optimised, utilised some tricks or any sort of improvements. I feel like I am really not using the full funcionality of Python somehow.

Any comments on how to write a succinct code is appreciated. Thanks.

"""
Program to find root of a function using bisection method
"""
import sys
import math

def is_equal(a,b):
    return abs(b-a) < sys.float_info.epsilon

def bisection(f, a, b, TOL=0.01, MAX_ITER=100):
    """
    f is the cost function, [a,b] is the initial bracket, 
    TOL is tolerance, MAX_ITER is maximum iteration.
    """
    f_a = f(a)
    f_b = f(b)

    iter = 0
    while iter < MAX_ITER:
        c = (a+b)/2
        f_c = f(c)

        if math.isclose(f_c,0.0,abs_tol=1.0E-6) or abs(b-a)/2<TOL:
            return (c, iter)
        else:
            if f_a * f_c < 0:
                b = c
                f_b = f_c
            else:
                a = c
                f_a = f_c
            iter = iter + 1
    return None

def func(x):
    """
    The cost function: f(x) = cos(x) - x
    """
    return math.cos(x) - x

root, iter = bisection(func, -1, 1, TOL=1.0E-6)
print("Iteration = ", iter)
print("root = ", root, ", func(x) = ", func(root))

\$\endgroup\$
3
\$\begingroup\$

Type hints

They can help; an example:

def is_equal(a: float, b: float) -> bool:

The return type of bisection should probably be Optional[float].

Argument format

MAX_ITER and TOL should be lower-case because they are the arguments to a function, not a global constant.

Early-return

        return (c, iter)
    else:

does not need the else, so you can drop it.

In-place addition

        iter = iter + 1

can be

        iter += 1

Return parens

This does not need parentheses:

        return (c, iter)

The tuple is implied.

\$\endgroup\$
0
3
\$\begingroup\$
  • I don't see the point of passing MAX_ITER. Bisection is guaranteed to terminate in \$\log \dfrac{b - a}{TOL}\$ iterations.

  • I strongly advise against breaking the loop early at math.isclose(f_c,0.0,abs_tol=1.0E-6). It only tells you that the value at c is close to 0, but doesn't tell you where the root is (consider the case when the derivative at root is very small). After all, tolerance is passed for a reason!

    If you insist on early termination, at least return the (a, b) interval as well. The caller deserves to know the precision.

  • You may want to do this test right before returning (like, is there a root at all):

    if math.isclose(f_c,0.0,abs_tol=1.0E-6):
        return None
    return c
    

    but I'd rather let the caller worry about that.

  • abs in abs(b - a) seems excessive.

    if a > b:
        a, b = b, a
    

    at the very beginning of bisection takes care of it once and forever.

  • (a + b) may overflow. c = a + (b - a)/2 is more prudent.

  • I don't see where is_equal(a,b) is ever used.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.