# -*- 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, ceil, log

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

    Bissecc_O3(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 ( for aprox. ), in percents

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

    x = 0
    iterCount = 0
    
    fl = F(xl) # used in O1

    imax = int(ceil(fabs(log(fabs(xr-xl)/errto)/log(2)))) # used in O2

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

        fx = F(x) # O1

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

        test = fl*fx # O1 reduce the funcion call: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__":
    print Bissecc_O3((lambda x: x*log(x/3) - x), 1.5, 20.2, 1e-14)