# -*- coding: utf-8 -*-
#
# bisseccao.py
#
#
# Autor: Pedro Garcia Freitas <sawp@sawp.com.br>
# License: Creative Commons
#      <http://creativecommons.org/licenses/by-nc-nd/2.5/br/>
#

from math import fabs, pow

def Bissecc(F, xl, xr, imax=500, errto=0.01):
    """
    Return the root of a function using Bissection Method

    Bissecc(fun, xl, xr, imax, errto)
    
    * fun: Function where find the roots
    * xl: left bound of interval
    * xr: right bound of interval
    * imax: max of iterations allowed
    * errto: tolerated error 

    Author: Pedro Garcia <sawp@sawp.com.br>
    License: Creative Commons
         <http://creativecommons.org/licenses/by-nc-nd/2.5/br/>
    """

    x = 0
    iterCount = 0
    errno = 1

    while errno > errto and iterCount < imax:
        xold = x
        x = (xl+xr)/2
        iterCount += 1

        if x != 0:
            errno = fabs( (x - xold)/x ) * 100

        test = F(xl)*F(x)

        if test < 0:
            xr = x
        elif test > 0:
            xl = x
        else:
            # test == 0 is when the F(x) is the root 
            errno = 0

    return x

if __name__ == "__main__":
    fun = lambda x: pow(x,4) - 26.0*pow(x,3) + 131.0*pow(x,2) \
         - 226.0*x + 120.0;

    print Bissecc(fun, 1.2, 2.99, 2000, 0.001);