TP: Implementing the Exponential Function (5/5)

TP: Implementing the Exponential Function (5/5)#

Attention

This exercise is marked with a ♣ and is therefore of a more advanced level; do not hesitate to skip it if it seems difficult to you in order to not waste too much time, and to come back to it later.

Part 5: Optimization ♣#

In this specific case, it is not very efficient to reuse the functions puissance and

factorielle: the calculations are performed several times! Indeed, as we have written our exponential function, to calculate \(x^{r+1}\) we restart the calculation from the beginning

(new call to the power function) without using the fact that we have already calculated \(x^r\)

and that \(x^{r+1} = x^r \times x\) (and similarly for the calculation of the factorial which is restarted from the beginning with each call to the factorial function, while

\((r+1)! = r! \times (r+1)\)). We will write a new, more efficient version of the exponential function, which does not call the power or factorial functions to avoid this problem of calculations being performed multiple times.

Copy and paste here the egal function from part 3:

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

Complete the function below that calculates the exponential to a given precision without

using an auxiliary function (except egal), and doing so more efficiently. To

do this, you will need three accumulation variables: that of the power, that

of the factorial and that of the exponential.

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 below: verify the level of precision, doesn’t seem to work

expRapide(5, 0.000000001) # 148.413159

148.41315907883663

expRapide(3, 0.000000001) # 20.085537

20.085536921517665

expRapide(1, 0.000000001) # 2.718282

2.7182818282861687

Evaluate the performance of the expRapide function again using timeit. Is it

really faster?

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

0.00012564659118652344

Summary#

You now have a significantly faster implementation of the exponential function.

However, should you always reimplement everything rather than reuse it? No, especially

not:

“Early optimisation is the root of all evil”

– Donald Knuth

Here, one could, for example, obtain the same performance without code duplication by

memoization (storing the already calculated values of \(n!\) and \(x^n\) to avoid

recalculating them). In general, it should be treated on a case-by-case basis, taking into account the trade-off

between development time and required performance, complexity issues (see

future courses), etc.

Contents