Paradigmes algorithmiques (schématiquement) :
for
et while
Paradigmes de programmation :
But : Calculer $x^n$
def exp_imp(x, n):
r = 1
y = x
for i in len(n):
r *= y**(n[i])
y **= 2
return y
def exp_imp(x, n):
r = 1
while n > 0:
if n & 1: # Bit n_0
r *= x
x *= x
n >>= 1 # Suppr. n_0
return r
exp_imp(2,10)
1024
« La quantité $x^n \times r$ est invariante dans l'algorithme »
($x_i$, $n_i$, $r_i$ : valeurs après $i$-ème passage dans la boucle)
But : Calculer $x^n$
$$x^n = \begin{cases} x\times (x\times x)^{\lfloor n/2\rfloor} &\text{si $n$ impair}\\ (x\times x)^{\lfloor n/2\rfloor} & \text{sinon}\end{cases}$$def exp_fct(x, n):
if n == 0: return 1
if n % 2 == 1: return x * exp_fct(x*x, n//2)
return exp_fct(x*x, n//2)
exp_fct(2, 10)
1024
%timeit _ = exp_imp(1, 100000000000)
%timeit _ = exp_fct(1, 100000000000)
5.25 µs ± 36 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 8.93 µs ± 8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
import sys
sys.getrecursionlimit()
3000
def somme(a, b): return a if b == 0 else somme(a+1, b-1)
somme(0, 3000)
--------------------------------------------------------------------------- RecursionError Traceback (most recent call last) <ipython-input-10-62ad9e8264f5> in <module>() 1 def somme(a, b): return a if b == 0 else somme(a+1, b-1) ----> 2 somme(0, 3000) <ipython-input-10-62ad9e8264f5> in somme(a, b) ----> 1 def somme(a, b): return a if b == 0 else somme(a+1, b-1) 2 somme(0, 3000) ... last 1 frames repeated, from the frame below ... <ipython-input-10-62ad9e8264f5> in somme(a, b) ----> 1 def somme(a, b): return a if b == 0 else somme(a+1, b-1) 2 somme(0, 3000) RecursionError: maximum recursion depth exceeded in comparison
Répartition de l'effort sur plusieurs processeurs
Réaction à des évènements extérieurs
Programmation déclarative, comme la prog. fonctionnelle
exp_log(X, 0, 1).
exp_log(X, N, R):- M is N mod 2,
M == 1,
D is (N-1)/2,
exp_log(X, D, R1),
R is R1*R1*X.
exp_log(X, N, R):- M is N mod 2,
M == 0,
D is N/2,
exp_log(X, D, R1),
R is R1*R1*X.