let fiboiter n = let x = ref 0 and y = ref 1 and aux = ref 0 in
  for i = 1 to n do
    aux := !y;
    y := !y + !x;
    x := !aux;
  done;
  !y
;;

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

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

let fibo2 n = let table = Array.make (n+1) (-1) in
  table.(0) <- 0;
  table.(1)<- 1;
  aux n table
;;

let m = Array.make_matrix 3 3 3;;
m.(1).(2) <- 5

(* let produitmatriciel a b = 
  if Array.length a <> Array.length b.(0) then
    print_endline ("error");
  let result = Array.make_matrix (Array.length a) (Array.length b.(0)) 0 in
  for i = 0 to (Array.length a)-1 do
    let aux = ref 0 in
    for j = 0 to Array.length a.(0)-1 do
      
    done;
  done;
  result
;; *)


let produit a b =
  let p = Array.length a and ra = Array.length a.(0)
    and rb = Array.length b and q = Array.length b.(0) in
      if ra <> rb then
        failwith "pb de dimension"
      else
        begin
          let c = Array.make_matrix p q 0 in
            for i = 0 to p-1 do
              for j = 0 to q-1 do
                for k = 0 to ra-1 do
                  c.(i).(j) <- c.(i).(j) + a.(i).(k) * b.(k).(j)
                done;
              done;
            done;
            c
        end
      ;;

let identite n = let c = Array.make_matrix n n 0 in
    for i = 0 to (n-1) do
      c.(i).(i) <- 1;
    done;
    c;;

let rec exp_rapide a n = match n with
  | 0 -> identite (Array.length a)
  | _ -> let aux = exp_rapide a (n/2) in
    if n mod 2 = 0 then produit aux aux
    else produit (produit aux aux) aux;;

let fibo n =
  let a = Array.make_matrix 2 2 1 in
    a.(0).(0) <- 0;
  (exp_rapide a n).(0).(1);;

let rechercheiter t x= let ln = Array.length t and bo = ref false in
  for i = 0 to ln-1 do
    if t.(i) = x then bo := true
    done;
    !bo;;

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

let rec rechercherecu_aux s x i= match i with
| -1 -> false
| _ -> (x = s.(i)) || rechercherecu_aux s x (i-1);;

let rechrecuchap s x = rechercherecu_aux s x ((Array.length s)-1);;

let rechdicoiter s x = let a = ref 0 and b = ref s.(Array.length s-1) in
  while !a <> !b do
    let c = (!a + !b)/2 in
      if s.(c)>= x then
        b := c
      else
        a := c+1
  done;
  (s.(!a) = x);;

let rec recherchedicorecu s x g d =
  if g = d then x = s.(g)
  else
    begin
      let m = (g+d)/2 in
        if s.(m)>= x then 
          recherchedicorecu s x m d
        else 
          recherchedicorecu s x (m+1) d
        end
      ;;

let recherchedicorecuchap s x = recherchedicorecu s x 0 (Array.length s-1);;

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

(* let produitpol a b = 
  let n = Array.length a in
    let c = Array.make (2*n) 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 : unit);
      done;
      c
    ;; *)

let fusion c1 c2 c3 = 
  let n = Array.length c1 in
    let c = Array.make (2*n) 0 in
      for k = 0 to (n/2-1) do
        c.(k) <- c1.(k)
      done;
      for i = (n/2) to (n-1) do
        c.(i) <- c1.(i) + c2.(i-n/2)
      done;
      for j = n to (3*n/2-1) do
        c.(j) <- c2.(j-n/2) + c3.(j-n) 
      done;
      for l = (3*n/2) to (2*n-1) do
        c.(l) <- c3.(l-n)
      done;
      c;;

let difference a b =
  let n = Array.length a in
    let c = Array.make n 0 in
      for k = 0 to (n-1) do
        c.(k) <- a.(k) - b.(k)
      done;
      c;;
let rec karatsuba a b = 
  if (Array.length a = 1) then
    [| a.(0)*b.(0); 0 |]
  else
    begin
      let n = Array.length a in
      let a1 = Array.sub a 0 (n/2) and
          a2 = Array.sub a (n/2) (n/2) and
          b1 = Array.sub b 0 (n/2) and
          b2 = Array.sub b (n/2) (n/2) in
        let c1 = karatsuba a1 b1 and
            c3 = karatsuba a2 b2 in
        let a12 = sommepoly a1 a2 and
            b12 = sommepoly b1 b2 in
        let c2 = difference (karatsuba a12 b12) (sommepoly c1 c3) in
          fusion c1 c2 c3
    end
  ;;
karatsuba [|1;2;3|] [|4;5;6|];;