Commençons donc par la fonction puissance réputée efficace.
Ce principe de division par deux est tellement classique que je ne
sais que dire.
(* Puissance efficace, suppose n ≥ 0 *)
let rec puissance x n = match n with
| 0 -> 1
| _ ->
let y = puissance x (n/2) in
if n mod 2 = 0 then
y * y
else
x * y * y
;; |
La solution la plus simple consiste ensuite à bêtement calculer la
somme de la valeur des monômes.
let evaluer p x =
List.fold_left
(fun r m -> r + m.coeff * puissance x m.degre)
0 p
;; |
Mais on peut faire un peu mieux (c'est à dire faire moins de
multiplications) en s'inspirant de la règle dite de Horner.
Rappelons la règle:
an xn + ⋯ + a1 x1 + a0 = (an xn−1 + ⋯ + a1) * x + a0
Puis on explicite l'évaluation :
E(an xn + ⋯ + a1 x1 + a0, X) =
E(an xn−1 + ⋯ + a1, X) * X + a0
Avec les polynômes creux, l'application directe donne plus ou moins
ceci (en replaçant les monômes absents par des monômes de coefficient
nul)
(* Méthode dite de Horner, pdeg est le degré du monome précédant *)
let rec horner pdeg r x p = match p with
| [] ->
if pdeg = 0 then
r
else
horner (pdeg-1) (r*x) x []
| m::rem ->
if pdeg = m.degre then
horner m.degre (r + m.coeff) x rem
else
horner (pdeg-1) (r*x) x p
;;
let evaluer p x = match p with
| [] -> 0
| m::rem ->
horner m.degre m.coeff x rem
;; |
Mais on peut employer notre function puissance en
réflechissant un peu:
let rec horner pdeg r x p = match p with
| [] -> r * puissance x pdeg
| m::rem -> horner m.degre (r * (puissance x (pdeg-m.degre)) + m.coeff) x rem
;; |