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 de même pour le calcul de la factorielle qui est repris du début à chaque appel à la fonction factorielle). 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.

Copier-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

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’accumulations : 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

É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ême 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.