Skip to content

Instantly share code, notes, and snippets.

@Jay-davisphem
Created December 12, 2022 17:45
Show Gist options
  • Save Jay-davisphem/80c9604ae2ac78b68ea4492252d87936 to your computer and use it in GitHub Desktop.
Save Jay-davisphem/80c9604ae2ac78b68ea4492252d87936 to your computer and use it in GitHub Desktop.
'''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()
@Jay-davisphem
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment