Partie 4 Question 21 (1)

[Yaya0312]

Complétez votre ensemble de fonctions de multiplication avec une fonction implémentant l’algorithme naïf.

[Yaya0312]

(* Complexity n²  n étant la longueur de la liste p1 *)
let rec mult_naive (p1:poly) (p2:poly) = 
  let aux p1 = match p1 with
  | [] -> []
  | e1::[] -> multCoeff (multXn p2 (degre [e1])) (snd e1)
  | e1::lst -> (mult_naive [e1] p2) ^+ (mult_naive lst p2)
  in aux p1
;;

[Yaya0312]

Version amélioré (complexité) (ps:non récursif terminal)

let get_litle_size_first (p1:poly) (p2:poly) =
    let len_p1 = List.length p1 and
        len_p2 = List.length p2 in
    if (len_p1 > len_p2) then
      p2,p1
    else
      p1,p2
;;

(* Complexity n² n étant la longueur de la liste du plus petit polynome *)
let mult_naive (p1:poly) (p2:poly) = 
  let p1, p2 = get_litle_size_first p1 p2 in
  let rec aux p1 p2 = match p1 with
  | [] -> []
  | e1::[] -> multCoeff (multXn p2 (degre [e1])) (snd e1)
  | e1::lst -> (aux [e1] p2) ^+ (aux lst p2)
  in aux p1 p2
;;