TP : implanter la fonction exponentielle (5/5)

Partie 5 : optimisation ♣¶

Dans ce cas précis, il n’est pas très efficace de réutiliser les fonctions puissance et factorielle : on effectue les calculs plusieurs fois! En effet, tel que nous avons écrit notre fonction exponentielle, pour calculer $x^{r+1}$ on reprend le calcul du début (nouvel appel à la fonction puissance) sans utiliser le fait qu’on a déjà calculé $x^r$ et que $x^{r+1} = x^r \times x$ (et de même pour le calcul de la factorielle qui est repris du début à chaque appel à la fonction factorielle alors que $(r+1)! = r! \times (r+1)$). On va écrire une nouvelle version plus efficace de la fonction exponentielle, qui ne fait pas appel aux fonctions puissance ou factorielle pour éviter ce problème de calculs faits plusieurs fois.

Copiez-collez ici la fonctions egal de la partie 3 :

### BEGIN SOLUTION
def egal(x, y, epsilon):
    v = abs(x - y)
    return (v < epsilon * abs(x)) and (v < epsilon * abs(y))


### END SOLUTION

Complétez la fonction ci-dessous qui calcule l’exponentielle à précision donnée sans utiliser de fonction annexe (sauf egal), et en procédant de façon plus efficace. Pour cela, vous aurez besoin de trois variables d’accumulation : celle de la puissance, celle de la factorielle et celle de l’exponentielle.

def expRapide(x, epsilon):
    """Calcul rapide de la fonction exponentielle à précision donnée
    * Parametre x un nombre de type double
    * Parametre epsilon un nombre de type double
    * Parametre e^x avec précision epsilon
    """
    ### BEGIN SOLUTION
    e1 = 0
    e2 = 1
    p = 1
    f = 1
    i = 1
    while not egal(e1, e2, epsilon):
        e1 = e2
        p *= x
        f *= i
        e2 += p / f
        i += 1
    return e2
    ### END SOLUTION

TODO en dessous : verifier le niveau de precision, a pas l’air de marcher

expRapide(5, 0.000000001)  # 148.413159

expRapide(3, 0.000000001)  # 20.085537

expRapide(1, 0.000000001)  # 2.718282

Évaluez la performance de la fonction expRapide en utilisant à nouveau timeit. Est-ce vraiment plus rapide?

import time

start = time.time()
expRapide(10, 0.00000001)
print(time.time() - start)

6.29425048828125e-05

Bilan¶

Vous avez maintenant une implantation nettement plus rapide de la fonction exponentielle. Faut-il pour autant toujours tout réimplanter plutôt que de réutiliser ? Non, surtout pas :

Ici, on pourrait par exemple obtenir les mêmes performances sans duplication de code par mémoïsation (conserver les valeurs déjà calculées de $n!$ et $x^n$ pour éviter de les recalculer). En général, c’est à traiter au cas par cas, en tenant compte du compromis entre temps de dévelopement et performances requises, des questions de complexité (cf cours à venir), etc.