TD exponentiation

Résumé du cours

L’exponentiation est une opération mathématique que l’on peut traduire par plusieurs algorithmes. $$a^n=\underbrace{a ×….× a}_{n~fois}\qquad et\ a^0=1$$

Algorithme itératif

def puissance_perso(x:int, n:int) -> int:
    res = 1
    while not n == 0:
        res = res * x
        n = n - 1
    return res

Algorithme récursif

Première formulation mathématique récursive: $$ puissance(x,n) = \left{ \begin{array}{ll} 1 & si~ n=0 \ x.puissance(x,n-1) & si~ n>0 \end{array} \right. $$

def puissance_recursif(x: int, n: int) -> int:
    if n == 0: # cas limite
        return 1
    else: # appel récursif
        return x*puissance_recursif(x, n-1)

Le coût temporel reste linéaire: la fonction effectue n appels récursifs.

Seconde formulation récursive: $$ puissance(x,n) = \left{ \begin{array}{ll} 1 & si~ n=0 \ puissance(xx,n/2) & si~ n>0 ~ et~ n~pair\ x.puissance(xx,(n-1)/2) & si~ n>0 ~ et ~n~ impair
\end{array} \right. $$

def puissance_recursif_rapide(x: int, n: int) -> int:
    if n == 0: # cas limite
        return 1
    elif n % 2 == 0: # pair
        return puissance_recursif_rapide(x*x, n//2)
    else: # impair
        return x*puissance_recursif_rapide(x*x, n//2)

L’exposant est divisé par 2 à chaque appel. Si $n=2^p$ alors il y a p appels récursifs. Le coût temporel est logarithmique.