Partie 1 Question 4

[Yaya0312]

Programmer cette méthode en OCaml en passant α en paramètre.

[Yaya0312]

(*----Fonction karatsuba entre le poly1 et poly2----*)
let rec karatsuba poly1 poly2 x =
  if max (degre poly1) (degre poly2) <= 1 then
    let a = coefficient poly1 1 in
    let b = coefficient poly1 0 in
    let c = coefficient poly2 1 in
    let d = coefficient poly2 0 in
    reduc [(0, b *. d); (1, a *. d +. b *. c); (2, a *. c)]
  else
    let i = 1 + max (degre poly1) (degre poly2) / 2 in
    let (a0, a1) = cut poly1 i in
    let (b0, b1) = cut poly2 i in
    let c0 = karatsuba a0 b0 x in
    let c2 = karatsuba a1 b1 x in
        let c3 = (multCoeff a1 x) in 
        let c4 = (multCoeff b1 x) in 
    let c1 = (((karatsuba (a0 +@ c3) (b0 +@ c4) x) -@ c0) -@ (multCoeff c2 (x*.x))) in
        let c1 = multCoeff (c1) (1./.x) in
    c0 +@ (multXn c1 i) +@ (multXn c2 (2 * i));;