TP : implanter la fonction exponentielle (5/5)

TP : implanter la fonction exponentielle (5/5)#

Partie 5 : optimisation ♣#

Dans notre cas, il n’est pas très efficace de réutiliser les fonctions puissance et factorielle : on refait en effet certains calculs de nombreuses 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)\)).

Pour éviter ces recalculs, nous allons maintenant définir une nouvelle version plus efficace de la fonction exponentielle qui ne fait pas appel aux fonctions puissance ou factorielle.

Exercice 1

  1. Copiez-collez ici les fonctions abs et egal de la partie 3 :

/// BEGIN SOLUTION
double abs(double x) {
    if (x < 0) {
        return -x;
    }
    return x;
}
/// END SOLUTION

/// BEGIN SOLUTION
bool egal(double x, double y, double epsilon) {
    double v = abs(x-y);
    return ((v < epsilon * abs(x)) and (v < epsilon * abs(y)));
}
/// END SOLUTION

Exercice 1 (suite)

  1. 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.

/** Calcul rapide de la fonction exponentielle à précision donnée
 * @param x un nombre de type double
 * @param epsilon un nombre de type double
 * @return e^x avec précision epsilon
**/
double expRapide(double x, double epsilon) {
    /// BEGIN SOLUTION
    double e1 = 0;
    double e2 = 1;
    double p = 1;
    double f = 1;
    int i = 1;
    while(not egal(e1,e2,epsilon)) {
        e1 = e2;
        p *= x;
        f *= i;
        e2 += p / f;
        i += 1;
    }
    return e2;
    /// END SOLUTION
}

expRapide(5, 0.000000001) // 148.413159

expRapide(3, 0.000000001) // 20.085537

expRapide(1, 0.000000001) // 2.718282

Exercice 1 (suite)

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

%timeit expRapide(10, 0.00000001);

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 :

«Early optimisation is the root of all evil»

– Donald Knuth

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.

Vous pouvez maintenant passer à la suite du TP.

Contenu