let puissance x n = let p = ref 1 in
  for k = 1 to n do
    p := !p * x
  done;
!p;;

let rec puissance_rec x n = match n with
| 0 -> 1
| _ -> x * puissance_rec x (n-1);;

let rec exponentiation_rapide x n = match n with
| 0 -> 1
| _ -> let y = exponentiation_rapide x (n/2) in
  if n mod 2 = 0 then y * y else x * y * y;;

let exponentiation_rapide_terminale x n =
  let rec exponentiation_rapide_aux x n acc = match n with
  | 0 -> acc
  | _ -> let y = if n mod 2 = 0 then acc else acc * x in
    exponentiation_rapide_aux (x * x) (n/2) y
  in exponentiation_rapide_aux x n 1;;

let exponentiation_rapide_iter x n =
  let p = ref 1 and x = ref x and n = ref n in
  while !n > 0 do
    if !n mod 2 = 0 then
      x := !x * !x
    else
      p := !p * !x;
    n := !n / 2
  done;
!p;;

let fibo_iter n =
  let u = ref 0 and v = ref 1 and aux = ref 0 in
  for k = 1 to !n do
    aux := !v;
    v := !u + !v;
    u := !aux
  done;
!u;;

let rec fibo_rec n = match n with
| 0 -> 0
| 1 -> 1
| _ -> fibo_rec (n-1) + fibo_rec (n-2);;

let rec fibo_aux n table =
  if table.(n) = -1 then
    table.(n) <- fibo_aux (n-1) table + fibo_aux (n-2) table;
  table.(n);;

let rec fibo_memo n =
  let table = Array.make (n+1) (-1) in
  table.(0) <- 0;
  table.(1) <- 1;
  fibo_aux n table;;

let recherche s x = let n = Array.length s and i = ref 0 in
  while !i < n && s.(!i) <> x do
    i := !i + 1
  done;
  !i <> n;;

let rec recherche_rec_aux s x i = match i with
| -1 -> false
| _ -> if s.(i) = x then true else recherche_rec_aux s x (i-1);;

let recherche_rec s x = recherche_rec_aux s x (Array.length s - 1);;

let recherche_dpr_iter s x =
  let g = ref 0 and d = ref (Array.length s - 1) in
    while !g < !d do
      let m = (!g + !d) / 2 in
      if (x <= s.(m)) then d := m else g := m + 1
    done;
  s.(!g) = x;;

let rec recherche_dpr_rec s x =
  let rec recherche_dpr_aux s x g d = match g with
  | _ when g > d -> false
  | _ -> let m = (g + d) / 2 in
    if x = s.(m) then true
    else if x < s.(m) then recherche_dpr_aux s x g (m-1)
    else recherche_dpr_aux s x (m+1) d
  in recherche_dpr_aux s x 0 (Array.length s - 1);;

(*Addition de 2 polynomes*)

let rec addition a b = let n = Array.length a in
 let c = Array.make n 0 in
  for i = 0 to n-1 do
    c.(i) <- a.(i) + b.(i)
  done;
c;;

let multiplication a b = let n = Array.length a in 
  let c = Array.make (2*n-1) 0 in
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      c.(i+j) <- c.(i+j) + a.(i) * b.(j)
    done
  done;
c;;