type poly == int list;; let rec clean = function | [] | [0] -> [] | [_] as p -> p | 0::t -> ( match clean t with [] -> [] | p -> 0::p ) | h::t -> h::clean t;; clean [];; clean [0];; clean [0;0;0;0;0;0];; clean [0;0;1;0;0;0];; clean [0;0;0;0;64;-8;0;3;0;0;0;0];; (* * QUESTION 2 *) let rec degre = function [] | [0] -> -1 | [_] -> 0 | h::t -> 1 + degre t;; degre [];; degre [0];; degre [-1; 0; 1];; degre [0;0;0;0;64;-8;0;3];; (* * QUESTION 3 *) let rec eval x = function [] -> 0 | h :: t -> h + x * (eval x t);; (* * QUESTION 4 *) let rec decale (p:poly) = function 0 -> p | n -> 0::decale p (n-1);; let rec mult x = function [] -> [] | h::t -> h*x :: mult x t;; let monomial_mult (p:poly) a n = decale (mult a p) n ;; (* * QUESTION 5 *) let rec add = fun [] p -> p | p [] -> p | (h1::t1) (h2::t2) -> (h1 + h2)::add t1 t2;; let rec poly_mult p = function [] -> [] | h :: t -> add (mult h p) (0::poly_mult p t);; poly_mult [-1;1] [1;1];; (* * QUESTION 7 *) let rec split = fun p 0 -> [],p | [] n -> raise (invalid_arg "split") | (h::t) n -> let p1,p2 = split t (n-1) in h::p1, p2;; split [] 0;; split [0;0;0] 1;; split [1;2;3;4;5] 3;; split [1;2;3;4;5;6] 3;; let rec DaC_mult = fun [] _ -> [] | _ [] -> [] | [x] [y] -> [x*y] | p q -> let n = max (list_length p) (list_length q) / 2 in let p1,p2 = split p n and q1,q2 = split q n in add (add (DaC_mult p1 q1) (decale (add (DaC_mult p1 q2) (DaC_mult p2 q1)) n)) (decale (DaC_mult p2 q2) (2*n));; DaC_mult [-1;1] [1;1];; DaC_mult [-1;0;1] [1;0;1];; DaC_mult [0;-1;0;1] [0;1;0;1];; (* * QUESTION 8 *) let rec sub p q = add p (mult (-1) q);; let rec Karatsuba = fun [] _ -> [] | _ [] -> [] | [x] [y] -> [x*y] | p q -> let n = max (list_length p) (list_length q) / 2 in let p1,p2 = split p n and q1,q2 = split q n in let l = Karatsuba p1 q1 and h = Karatsuba p2 q2 and m = Karatsuba (add p1 p2) (add q1 q2) in add (add (decale h (2*n)) (decale (sub (sub m h) l) n)) l;; Karatsuba [-1;1] [1;1];; Karatsuba [-1;0;1] [1;0;1];; Karatsuba [0;-1;0;1] [0;1;0;1];; (* * QUESTION 11 *) let make_matrix n m e = let r = make_vect n [||] in for i = 0 to n-1 do r.(i) <- make_vect m e; done; r;; let make_matrix_2 n m e = init_vect n (fun _ -> make_vect m e);;