(* 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 |
let evaluer p x = List.fold_left (fun r m -> r + m.coeff * puissance x m.degre) 0 p |
Avec les polynômes creux, l'application directe donne plus ou moins ceci (en remplaç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édent *) 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 |
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 |