(** Exercice 1 *)

let rec randlist maxval n = match n with
    | 0 -> []
    | _ -> random__int maxval :: randlist maxval (n-1) ;;

let mesurer_temps f x =
    let n = 20 in  (* nombre d'iterations *)
    let start = sys__time () in
    for i = 1 to n do
        let _ = f x in  (* ignorer le résultat *)
        ()
    done;
    let stop = sys__time () in
    (stop -. start) /. (float_of_int n);;

let rec insert x l = match l with
    | [] -> [x]
        | y::l' -> if x <= y then x :: l else y :: insert x l';;

let rec insert_sort l = match l with
    | [] -> []
        | x :: l' -> insert x (insert_sort l');;

(** Exercice 3 *)

(** Polynomes *)

let degre p = vect_length p - 1 ;;

(* opposé *)
let opp_poly p =
  init_vect (vect_length p) (fun i -> - p.(i));;

(* quotient de la division euclidienne de p par X^m *)
let quotient_poly p m =
  let n = degre p in
  if n<m
  then [| 0 |]
  else init_vect (n-m+1) (fun i -> p.(i+m)) ;;

(* reste de la division euclidienne de p par X^m *)
let reste_poly p m =
  let degre_resultat = ref (min (degre p) (m-1)) in
  while !degre_resultat >= 0 &&  p.(!degre_resultat) = 0 do
    decr degre_resultat;
  done;
  let r = init_vect (!degre_resultat + 1) (fun i -> p.(i)) in
  r ;;

(* produit de p par X^m *)
let shift_poly p m =
  let r = make_vect (m + vect_length p) 0 in
  for i = 0 to degre p do
    r.(i+m) <- p.(i);
  done;
  r;;

(* créer une string représentant le polynome *)
let affiche_poly v =
  let s = ref "[|" in
  let first = ref true in
  for i = 0 to vect_length v - 1 do
    (if !first then first := false else s := !s ^ "; ");
    s := !s ^ string_of_int v.(i)
  done;
  !s ^ "|]"
;;

(* vérifier si p=q, en ignorant les 0 du début si l'un est plus long
 * que l'autre. *)
let egal_poly p q =
  let res = ref true in
  let m = degre p in
  let n = degre q in
  for i = 0 to min m n do
    if p.(i) <> q.(i) then res := false
  done;
  let bigger = if m > n then p else q in
  for i = min m n + 1 to max m n do
    if bigger.(i) <> 0 then res := false
  done;
  !res ;;

(* polynome aleatoire dont les coeffs sont entre -20 et 20 *)
let random_poly () =
    let degre = random__int 30 + 1 in
    let p = init_vect degre (fun _ -> random__int 41 - 20) in
    (* il faut etre sur que le dernier coefficient n'est pas 0 *)
    p.(vect_length p - 1) <- random__int 12 + 1;
    p;;

(* liste de n paires de polynomes aleatoires *)
let rec random_paires n = match n with
    | 0 -> []
    | _ ->
    (random_poly (), random_poly()) :: random_paires (n-1);;

(* tester que f1 et f2 se comportent pareillement sur des polynomes
   aleatoires *)
let tester_similaire f1 f2 =
    let l = random_paires 100 in
    (* vérifier, sur chaque paire de l, que f1 et f2 renvoient
     * le meme résultat *)
    list__for_all
        (fun (p1,p2) ->
          let ok = egal_poly (f1 p1 p2) (f2 p1 p2) in
          if not ok
            then print_endline
            ("probleme pour: " ^ affiche_poly p1 ^ " et " ^ affiche_poly p2);
          ok
        ) l;;

(* on peut tester son programme avec
tester_similaire prod_poly karatsuba_poly;;

init_vect 15 puissance_poly ;; (* pour (X+1)^n *)
*)