TP : implanter la fonction exponentielle (5/5)

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

Attention

Cet exercice est marqué d’un ♣ et est donc d’un niveau plus avancé ; n’hésitez pas à le passer s’il vous paraît difficile afin de ne pas perdre trop de temps, et à revenir dessus ultérieurement.

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

148.41315907883663

expRapide(3, 0.000000001) # 20.085537

20.085536921517665

expRapide(1, 0.000000001) # 2.718282

2.7182818282861687

É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)

0.0001628398895263672

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.

Contenu