Editing Bisection method (section)

==Algorithm==
{{cleanup|date=May 2025|reason=This section includes raw source code instead of an algorithm description. Please rewrite using pseudocode or clear steps.}}<pre>import numpy as np
import math


def bisect(f, a, b, tol, bound=9.8813129168249309e-324):
    ############################################################################E
    # input: Function f,
    #        endpoint values a, b,
    #        tolerance tol, (if tol = 5e-t and bound = 9.0e-324 the function 
    #                        returns t significant digits for a root between the 
    #                        minimum normal and the maximum normal),
    #         bound (if bound=9.8813129168249309e-324, the algorithm continues  
    #                until the interval cannot be further divided, a larger value 
    #                may result in termination before t digits are found).
    # conditions: f is a continuous function in the interval [a, b],
    #             a < b,
    #             and f(a)*f(b) < 0.
    # output:    [root, iterations, convergence, termination condition]    
    #############################################################################N
    if b <= a:
        return [float("NAN"), 0, "No convergence", "b < a"]
    fa = f(a)
    fb = f(b)
    if np.sign(fa) == np.sign(fb):
        return [float("NAN"), 0, "No convergence", "f(a)*f(b) > 0"]
    en = 0
    while en < 2200:
        en += 1
        if np.sign(a) == np.sign(b):  # avoid overflow
            c = a + (b - a)/2
        else:
            c = (a + b)/2
        fc = f(c)
        if b - a <= bound:
            return [bound, en, "No convergence", "Bound reached"]
        if fc == 0:
            return [c, en, "Converged", "f(c) = 0"]
        if b - a <= abs(c) * tol:
            return [c, en, "Converged", "Tolerance"]
        if np.sign(fa) == np.sign(fc):
            a = c
            fa = fc
        else:
            b = c

    return [float("NAN"), en, "No convergence", "Bad function"]</pre>
The first 2 examples test for incorrect input values:
<pre>
 1 bisect(lambda x: x -                  1, 5, 1, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root =                nan 
No convergence after 0 iterations with termination b < a
Final interval [               nan,                nan]

 2 bisect(lambda x: x -                  1, 5, 7, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root =                nan 
No convergence after 0 iterations with termination f(a)*f(b) > 0
Final interval [               nan,                nan]</pre>
Large roots:
<pre>
 3 bisect(lambda x: x -  12345678901.23456, 0, 1.23457e+14, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root =  12345678901.23454 
Converged after 62 iterations with termination Tolerance
Final interval [1.2345678901234526e+10, 1.2345678901234552e+10]

 4 bisect(lambda x: x - 1.23456789012456e+100, 0, 2e+100, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root = 1.234567890124561e+100 
Converged after 50 iterations with termination Tolerance
Final interval [1.2345678901245599e+100, 1.2345678901245619e+100]
</pre>
The final interval is computed as [c - w/2, c + w/2] where <math>w = {\frac{b - a}{2^n}}</math>. This can give good measure as to the accuracy of the approximation

Root near maximum:
<pre>
 5 bisect(lambda x: x - 1.234567890123456e+307, 0, 1e+308, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root = 1.234567890123454e+307 
Converged after 52 iterations with termination Tolerance
Final interval [1.2345678901234535e+307, 1.2345678901234555e+307]
</pre>
Small roots:
<pre>
 6 bisect(lambda x: x - 1.234567890123456e-05, 0, 1, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root = 1.234567890123455e-05 
Converged after 65 iterations with termination Tolerance
Final interval [1.2345678901234537e-05, 1.2345678901234564e-05]

 7 bisect(lambda x: x - 1.234567890123456e-100, 0, 1, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root = 1.234567890123454e-100 
Converged after 381 iterations with termination Tolerance
Final interval [1.2345678901234532e-100, 1.2345678901234552e-100]
</pre>
Ex. 8 is beyond the minimum normal but gives a fairly good result because the approximation has a small interval. Calculations for values in the subnormal range can produce unexpected results.
<pre>
 8 bisect(lambda x: x - 1.234567890123457e-310, 0, 1, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root = 1.234567890123457e-310 
Converged after 1071 iterations with termination f(c) = 0
Final interval [1.2345678901232595e-310, 1.2345678901236548e-310]
</pre>
If the return state is '<math>f(c) = 0</math>', then the desired tolerance may not have been achieved. This can be checked by lowering the tolerance until a return state of 'Tolerance' is achieved.
<pre>
8a bisect(lambda x: x - 1.234567890123457e-310, 0, 1, 5.000000e-13)
         Approx. root = 1.234567890123457e-310 
Converged after 1071 iterations with termination f(c) = 0
Final interval [1.2345678901232595e-310, 1.2345678901236548e-310]

8b bisect(lambda x: x - 1.234567890123457e-310, 0, 1, 5.000000e-12)
         Approx. root = 1.234567890124643e-310 
Converged after 1069 iterations with termination Tolerance
Final interval [1.2345678901238524e-310, 1.2345678901254334e-310]
</pre>

8b shows that the result has 12 digits.

Even though the root is outside the 'normal' range, it may still be possible to achieve results with good tolerance.

<pre>
 9 bisect(lambda x: x - 1.234567891003685e-315, 0, 1, 5.000000e-03, 9.8813129168249309e-324)
         Approx. root = 1.23558592808891e-315 
Converged after 1055 iterations with termination Tolerance
Final interval [1.2342907646422757e-315, 1.2368810915355439e-315]
1.2368810915355439e-315]
</pre>
Ex. 10 shows the maximum number of iterations that should be expected:
<pre>
10 bisect(lambda x: x - 1.234567891003685e-315, -1e+307, 1e+307, 5.000000e-15, 9.8813129168249309e-324)
         Approx. root = 1.234567891003685e-315 
Converged after 2093 iterations with termination f(c) = 0
Final interval [1.2345678910036845e-315, 1.2345678910036845e-315]

</pre>
There may be situations in which a 'good' approximation is not required. This can be achieved by changing the 'Bound':
<pre>
11 bisect(lambda x: x - 1.234567890123457e-100, 0, 1, 5.000000e-15, 4.9999999999999997e-12)
         Approx. root =              5e-12 
No convergence after 39 iterations with termination Bound reached
Final interval [4.0905052982270715e-12, 5.9094947017729279e-12]

</pre>
Evaluation of the final interval may assist in determining accuracy.

The following show the behavior of subnormal numbers And shows how the significant digits are lost:
<pre>
print(1.234567890123456e-310)
1.23456789012346e-310
print(1.234567890123456e-312)
1.234567890124e-312
print(1.234567890123456e-315)
1.23456789e-315
print(1.234567890123456e-317)
1.234568e-317
print(1.234567890123456e-319)
1.23457e-319
print(1.234567890123456e-321)
1.235e-321
print(1.234567890123456e-323)
1e-323
print(1.234567890123456e-324)
0.0
</pre>

These examples show that this method gives 15 digit accuracy for functions of the form <math>f(x) = (x - r) g(x)</math> for all <math>r</math> in the range of normal numbers.