#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Nov 16 09:52:24 2017

@author: valerie
"""

#TP2 Recherche de racines
#Merci à Diego CONDORI pour ce corrigé 


import matplotlib.pyplot as plt
import numpy as np
from scipy.optimize import fsolve
import time

#Exercice 1: Retour sur le TD
#Se reporter au fichier 'TD2 Python starring V. Monbet.py'

#Exercice 2: Recherche de racines par dichotomie

#Afin de simplifier la lisibilité de l'exercice, on se propose de définir
#une fonction d'affichage de graphe pour chaque question de l'exercice.


#1. On défini la fonction f.

def f(x):
    return(x**2-1)


x1 = np.linspace(0,5,100)
plt.plot(x1,f(x1))
plt.grid()

#2. On implémente la méthode de dichotomie.

def dichotomie(f, a, b, epsilon = 10**(-15)):
    """Zéro de f sur [a,b] à epsilon près, par dichotomie Préconditions : 
    f(a) * f(b) <= 0 et epsilon > 0"""
    c, d = a, b
    fc = f(c)
    while abs(d-c) > 2 * epsilon:
        m = (c + d) / (2.)
        fm = f(m)
        if fc * fm <= 0:
            d = m
        else:
            c, fc = m, fm
    return (c + d) / 2.

#On s'assure de bien marquer le point ou f s'annule par un point rouge.

d1 = dichotomie(f,0,5)
x1 = np.linspace(0,5,100)
plt.plot(x1,f(x1))
plt.plot(d1,f(d1),"r+")
plt.grid()

#3. On trace le polynome p et on matérialise la solution de p(x)=0.

def p(x):
    return(x**3-2*x-5)


d2 = dichotomie(p,-5,5)
x2 = np.linspace(-5,5,100)
plt.plot(x2,p(x2))
plt.plot(d2,p(d2),"r+")
plt.grid()

#Exercice 3: Recherche de racines par la méthode de Newton - Dérivée connue

#1. Implémentation de la méthode de Newton

def newton(x0,f,df, epsilon = 10**(-12),maxiter = 30):
    """Zéro de f par la méthode de Newton départ : x0, f’ = fp, 
    critère d’arrêt epsilon et le nombre maximum d'itérations."""
    u = x0
    n = 0
    v = u - f(u)/df(u)
    while abs(v-u) > epsilon:
        n = n+1
        if n > maxiter:
            chn = "Échec après {} itérations.".format(maxiter)
            raise RuntimeError(chn)
        u, v = v, v - f(v)/df(v)
    print("La solution par la méthode de Newton de la fonction ",f.__name__," est: ",v," réalisé en ",n," itérations.")

#On défini la dérivée de p.

def dp(x):
    return(3*x**2-2)
#On récrit une méthode par dichotomie qui affiche la solution trouvée avec
#le nombre d'itérations réalisées pour trouver cette solution.

def dichotomie2(f, a, b, epsilon = 10**(-15),maxiter = 100):
    """Zéro de f sur [a,b] à epsilon près, par dichotomie Préconditions : 
    f(a) * f(b) <= 0 et epsilon > 0 et le nombre maximum d'itérations."""
    n = 0
    c, d = a, b
    fc = f(c)
    while abs(d-c) > 2 * epsilon:
        n = n+1
        if n > maxiter:
            chn = "Échec après {} itérations.".format(maxiter)
            raise RuntimeError(chn)
        m = (c + d) / (2.)
        fm = f(m)
        if fc * fm <= 0:
            d = m
        else:
            c, fc = m, fm
    print("La solution par dichotomie de la fonction ",f.__name__,"  est: ",(c + d) / 2.," réalisé en ",n," itérations.")

    
#2. et 3. En lancant les deux fonctions dichotomie2 et newton pour p, on 
#remarque que l'on utilise beaucoup moins d'itérations pour la méthode de 
#Newton. En effet, on utilise environ moitié moins d'itérations qu'avec la 
#méthode par dichotomie.


#4. On défini la fonction dont on va étudier ses racines, ainsi que sa dérivée:

def g(x):
    return(np.cos(x)-x**3)           #On utilise pas math.cos car plus tard
                                     #numpy ne reconnait pas le cosinus et le
def dg(x):                           #le traite comme une matrice.
    return(-np.sin(x)-3*x**2)
    
    
#Puis on utilise la méthode de Newton qui semble être plus rapide afin de
#trouver les racines de notre fonction g.
#(Faire attention cependant à ne pas poser un x0 tel que df(x0) s'annule)


#Exercice 4: Recherche de racines par la méthode de Newton - Dérivée inconnue

#1. Sur une meme figure, on trace la fonction p et sa dérivée, de meme pour p.

plt.subplot(221)
x1 = np.linspace(-5,5,100)
plt.plot(x1,p(x1),"r-",label="Cp")
plt.plot(x1,dp(x1),"b-",label="Cp'")
plt.legend()
plt.grid()
plt.subplot(222)
x2 = np.linspace(-3,4,100)
plt.plot(x2,g(x2),"r-",label="Cg")
plt.plot(x2,dg(x2),"b-",label="Cg'")
plt.legend()
plt.grid()

#2. On défini la fonction sécante pour trouver la racine sans dérivée explicite.
#On commence par définir la dérivée au sens du taux d'accroissement.

def fp(x0,x1):
    return((f(x1)-f(x0))/(x1-x0))

def secante(x0,x1,f, epsilon = 10**(-12),maxiter = 30):
    """Zéro de f par la méthode de la sécante sans connaitre la dérivée; 
    départ : x0,x1, critère d’arrêt epsilon et le nombre maximum d'itérations."""
    t = x0
    u = x1
    n = 0
    v = u - f(u)*(u-t)/(f(u)-f(t))
    while abs(v-u) > epsilon:
        n = n+1
        if n > maxiter:
            chn = "Échec après {} itérations.".format(maxiter)
            raise RuntimeError(chn)
        u, v = v, v-f(v)*(v-u)/(f(v)-f(u))
    print("La solution par la sécante de la fonction ",f.__name__," est: ",v," réalisé en ",n," itérations.")
    


#3. On utilise la fonction secante pour approcher les racines de p et de g.

print(secante(0,1,p))
print(secante(0,1,g))

    

#4. On utilise la fonction fsolve pour les fonctions définies précédemment et
#on compare avec nos résultats précédents.

s1 = fsolve(p,1)
s2 = fsolve(g,1)
print("La solution par la fonction fsolve de p est: ",s1)
print("La solution par la fonction fsolve de g est: ",s2)
plt.subplot(221)
x1 = np.linspace(-5,5,100)
plt.plot(x1,p(x1),"b-",label="Cp")
plt.plot(s1,p(s1),"r*")
plt.legend()
plt.grid()
plt.subplot(222)
x2 = np.linspace(-3,4,100)
plt.plot(x2,g(x2),"b-",label="Cg")
plt.plot(s2,g(s2),"r*")
plt.legend()
plt.grid()
    
#Par rapport aux valeurs précédentes on peut dire que l'on est assez proche.
#Reste a voir si la fonction fsolve est plus rapide en terme d'itérations que
#nos fonctions naïves.

    
#Exercice 5: Temps d'éxecution

#1. On compare les temps d'éxecution des différentes méthodes.


def meth1(toto):
    start = time.time()
    for i in range(len(toto)):
        a = toto[i] 
    return("{0:2f}".format(time.time()-start))

def meth2(toto):    
    start = time.time()
    for ele in toto:
        a = ele
    return("{0:2f}".format(time.time() - start))
    
def meth3(toto):
    start = time.time()
    for i in range(len(toto)):
        a = toto[i]
    return("{0:2f}".format(time.time() - start))
    
def meth4(toto):
    start = time.time()
    for idx, ele in enumerate( toto ):
        a = ele
    return("{0:2f}".format(time.time() - start))

def compa(taille):
    """Fonction qui compare le temps d'éxecution pour chacune des 4 méthodes,
    prennant en argument la taille d'une liste et renvoyant la méthode la
    plus adaptée."""
    toto = range(taille)
    l = [float(meth1(toto)),float(meth2(toto)),float(meth3(toto)),float(meth4(toto))]
    print("La méthode la plus rapide est la numéro ", l.index(min(l))+1," avec une vitesse de ", min(l)," secondes.")
       
    
#On remarque que la méthode 1 marche bien pour les petites tailles, mais que
#la méthode 2 marche mieux pour les grandes tailles.


#2. Pour cette question on se propose de modifier toutes les fonctions
#   des méthodes prédédentes afin qu'elles ne renvoient rien en sortie.

def dichotomiemodifie(f, a, b, epsilon = 10**(-15),maxiter = 100):
    """Zéro de f sur [a,b] à epsilon près, par dichotomie Préconditions : 
    f(a) * f(b) <= 0 et epsilon > 0 et le nombre maximum d'itérations."""
    n = 0
    c, d = a, b
    fc = f(c)
    while abs(d-c) > 2 * epsilon:
        n = n+1
        if n > maxiter:
            chn = "Échec après {} itérations.".format(maxiter)
            raise RuntimeError(chn)
        m = (c + d) / (2.)
        fm = f(m)
        if fc * fm <= 0:
            d = m
        else:
            c, fc = m, fm            
            
def newtonmodifie(x0,f,df, epsilon = 10**(-12),maxiter = 30):
    """Zéro de f par la méthode de Newton départ : x0, f’ = fp, 
    critère d’arrêt epsilon et le nombre maximum d'itérations."""
    u = x0
    n = 0
    v = u - f(u)/df(u)
    while abs(v-u) > epsilon:
        n = n+1
        if n > maxiter:
            chn = "Échec après {} itérations.".format(maxiter)
            raise RuntimeError(chn)
        u, v = v, v - f(v)/df(v)
        
def secantemodifie(x0,x1,f, epsilon = 10**(-12),maxiter = 30):
    """Zéro de f par la méthode de la sécante sans connaitre la dérivée; 
    départ : x0,x1, critère d’arrêt epsilon et le nombre maximum d'itérations."""
    t = x0
    u = x1
    n = 0
    v = u - f(u)*(u-t)/(f(u)-f(t))
    while abs(v-u) > epsilon:
        n = n+1
        if n > maxiter:
            chn = "Échec après {} itérations.".format(maxiter)
            raise RuntimeError(chn)
        u, v = v, v-f(v)*(v-u)/(f(v)-f(u))
  
        
# On défini ensuite des fonctions temps permettant de connaitre le temps que
# et chaque méthode à tourner 100 000 fois chacune.
        
def temps1():
    start = time.time()
    for i in range(100000):
        dichotomiemodifie(p,-5,5)
    return("{0:2f}".format(time.time() - start))
        
def temps2():
    start = time.time()
    for i in range(100000):
        newtonmodifie(5,p,dp)
    return("{0:2f}".format(time.time() - start))
    
def temps3():
    start = time.time()
    for i in range(100000):
        secantemodifie(-5,5,p)
    return("{0:2f}".format(time.time() - start))
    
    
# On obtient en sortie que la fonction:
# Dichotomie met 6,5 secondes à tourner 100 000 fois.
# Newton     met 1,3 secondes à tourner 100 000 fois.
# Sécante    met 2,9 secondes à tourner 100 000 fois.

#On peut conclure que la méthode de Newton est la plus efficace.