from math import pi, sqrt

def f(t):
    return 4 / (1 + t**2)

## Rectangles
# h * somme des f(x_k). Gauche : k = 0 .. n-1 ; droite : k = 1 .. n ;
# milieu : x_k + h/2.

def rectangles_gauche(f, a, b, n):
    h = (b - a) / n
    s = 0
    for k in range(n):
        s = s + f(a + k * h)
    return h * s

def rectangles_droite(f, a, b, n):
    h = (b - a) / n
    s = 0
    for k in range(1, n + 1):
        s = s + f(a + k * h)
    return h * s

def rectangles_milieu(f, a, b, n):
    h = (b - a) / n
    s = 0
    for k in range(n):
        s = s + f(a + (k + 0.5) * h)
    return h * s

## Trapèzes : moyenne des rectangles gauche et droite.

def trapezes(f, a, b, n):
    h = (b - a) / n
    s = (f(a) + f(b)) / 2
    for k in range(1, n):
        s = s + f(a + k * h)
    return h * s

## Newton : x <- x - f(x)/f'(x) tant que |x_{n+1}-x_n| >= eps.

def newton(f, fprime, x, eps, max_iter=100):
    n = 0
    delta = eps + 1
    while delta >= eps and n < max_iter:
        x_suivant = x - f(x) / fprime(x)
        delta = abs(x_suivant - x)
        x = x_suivant
        n = n + 1
    return x
    # n contient le nombre d'itérations effectuées

def g(x):
    return x**2 - 2

def gprime(x):
    return 2 * x

# newton(g, gprime, 1, 1e-12) approche sqrt(2)

## Dichotomie : on retient le sous-intervalle où f change de signe.

def dichotomie(f, a, b, eps):
    while b - a >= eps:
        m = (a + b) / 2
        if f(a) * f(m) <= 0:
            b = m
        else:
            a = m
    return (a + b) / 2