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 les fonctions abs et egal de la partie 3 :

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

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) {
    // REMPLACER CETTE LIGNE ET LA SUIVANTE PAR VOTRE RÉPONSE
    throw std::runtime_error("À faire");
}

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