bisection_method.py

'''By David Oluwafemi(davisphem)'''
from typing import List, Callable
from math import log2, ceil


def get_n_max(a: float, b: float, tol: float) -> int:
    '''get the number of iteration(number of times of bisecting)'''
    return ceil(log2(abs(b - a) / tol))


def bisect(f: Callable[[float], float], interval: List[float], tol: float,
           n_max: int) -> float:
    '''bisect given the number of iteration and tolerance'''
    a, b = interval
    if f(a) == 0:
        return a
    elif f(b) == 0:
        return b
    if a >= b:
        raise Exception(
            f"arg 'a' should be smaller than arg 'b', but {a} >= {b}")
    if not ((f(a) < 0 and f(b) > 0) or (f(a) > 0 and f(b) < 0)):
        raise Exception(
            f'The function is not continuous on in interval [{a}, {b}]')
    n = 0
    while n < n_max:
        c = (a + b) / 2
        if f(c) == 0 or (b - a) / 2 < tol:
            return c
        n += 1
        if f(c) * f(a) < 0:
            b = c
        elif f(c) * f(a) > 0:
            a = c
    raise Exception('Method failed')


def bisection_method(f: Callable[[float], float], a: float, b: float,
                     tol: float) -> float:
    '''bisect given the tolerance only'''
    n_max = get_n_max(a, b, tol)
    return bisect(f, [a, b], tol, n_max)


def main():
    '''test using given only tolerance'''
    f = lambda x: x**3 - 3 * x + 1
    a, b = [0, 1]
    tol = 1e-5
    print(bisection_method(f, a, b, tol))


if __name__ == '__main__':
    main()

Numerical computations of non-linear equations using bisection method in 0(n) time complexity. It's accurate but not performant.