(* Correction TP1

- Auteur : Lilian Besson
- Date : 05 février 2019
*)

(* On utilise OCaml et pas Caml. *)
Sys.command "ocaml -version";;

(* Exercice 0 *)
print_endline "\n\nExercice 0 :";;

let a = 3 in
  a + 5
;;

let a = 3 in a + 5;;


(* Exercice 1 *)
print_endline "\n\nExercice 1 :";;

let mot1 = "Bonjour " in
let mot2 = "et au revoir" in
let concat = mot1 ^ mot2 in (* il faut changer + en ^ *)
print_string concat;;

let a = 1515 in
let b = a*a in
b - 1;;

let rec a (n : int) : float =
  if n = 0 then 1.0
  else sin( a (n-1))
;;

a 5;;

let carre (n : int) : int = n * n;;
let puissance_quatre (n : int) : int = carre (carre n);;
let puissance_huit (n : int) : int = carre (puissance_quatre n);;
let f = puissance_huit;;

f 2;;

(* autre solution *)

let pow_int (n : int) (expo : int) : int =
  int_of_float ((float_of_int n) ** (float_of_int expo))
;;

let f (n : int) : int = pow_int n 8;;

f 2;;

(* autre solution, question b) *)

let f (n : int) : int =
  let a = n * n in
  let b = a * a in
  b * b
;;

f 2;;


(* Exercice 2 *)
print_endline "\n\nExercice 2 :";;

let rec u (n : int) : int =
  if n = 0 then 1
  else 3 * (u (n-1)) - 1
;;

u 15;;

let rec h (n : int) : float =
  if n = 0 then 0.0
  else (h (n-1)) +. (1.0 /. (float_of_int n))
;;

h 15;;

let rec b (n : int) (k : int) : int =
  match k with
  | _ when k > n -> 0
  | 0 -> 1
  | _ -> (n * (b (n-1) (k-1))) / k
;;

b 15 8;;

let rec f (n : int) : int =
  if n < 2 then n
  else (f (n - 2)) + (f (n - 1))
;;

f 34;;
f 35;;
f 36;;
f 37;;

let rec expo (a : int) (n : int) : int =
  match n with
  | 0 -> 1
  | n when n mod 2 = 0 -> expo (a*a) (n / 2)
  (* en fait, cette premiere solution n'est pas optimale, l'appel suivant n'est pas terminal récursif *)
  | n when n mod 2 = 1 -> a * (expo (a*a) (n / 2))
  | _ -> failwith "Erreur : ce cas ne doit pas arriver."
;;

expo 13 4;;

let expo (a : int) (n : int) : int =
  let rec aux (acc : int) (a : int) (n : int) : int =
    match n with
    | 0 -> acc
    | n when n mod 2 = 0 -> aux acc (a*a) (n / 2)
    | n when n mod 2 = 1 -> aux (a * acc) (a*a) (n / 2)
    | _ -> failwith "Erreur : ce cas ne doit pas arriver."
  in
  aux 1 a n
;;

expo 13 4;;

(* deuxième version question b) *)



let rec expo (a : int) (n : int) : int =
  match n with
  | 0 -> 1
  | n when n mod 2 = 0 ->
    begin
      let tmp = expo a (n / 2) in
      tmp * tmp
    end
  (* en fait, cette premiere solution n'est pas optimale, l'appel suivant n'est pas terminal récursif *)
  | n when n mod 2 = 1 ->
    begin
      let tmp = expo a (n / 2) in
      a * tmp * tmp
    end
  | _ -> failwith "Erreur : ce cas ne doit pas arriver."
;;

expo 13 4;;


let compose f g =
  let h x = f (g x) in
  h
;;

let compose f g = fun x -> f (g x);;

let rec compiter (f : 'a -> 'a) (n : int) (x : 'a) : 'a =
  match n with
  | _ when n < 0 -> failwith "Erreur : n < 0 n'est pas possible."
  | 0 -> x
  | 1 -> f x
  | _ -> compiter f (n-1) (f x)
;;

let a x = 2*x - 1 in
let b = compiter a 3 in
b 2;;

let rec u (k : int) : int =
  if k = 0 then 1
  else 3 * (u (k-1)) - 1
;;

let rec s (n : int) : int =
  match n with
  | _ when n < 1 -> 0
  | 1 -> u 1
  | _ -> (s (n - 1)) + (u n)
;;

s 15;;

let s (n : int) : int =
  let rec a (unmk : int) (k : int) : int =
    if k = 0 then unmk
    else unmk + (a (3*unmk-1) (k-1))
  in
  a 1 n
;;

(* Exercice 3 *)
print_endline "\n\nExercice 3 :";;

let rec nb_chiffres (n : int) : int =
  match n with
  | _ when n < 0 -> nb_chiffres (-n)
  | 0 -> 1
  | _ -> 1 + (nb_chiffres (n / 2))
;;

nb_chiffres 12309;;

let nb_chiffres (n : int) : int =
  (* on calcule les 1+ dans l'accumulateur acc *)
  let rec aux (acc : int) (k : int) : int =
    match k with
    | _ when k < 0 -> aux acc (-k)
    | 0 -> acc
    | _ -> aux (1 + acc) (k / 2)
  in
  aux 0 n
;;

nb_chiffres 1;;
nb_chiffres 12;;
nb_chiffres 123;;
nb_chiffres 1230;;
nb_chiffres 12309;;


let rec chiffre (n : int) (i : int) : int =
  if i = 0 then n mod 2
  else chiffre (n / 2) (i - 1)
;;

let n = 12309;;
print_string "Chiffres (en binaire) de n = ";
print_int n;
print_endline ":";
for i = 0 to (nb_chiffres n) - 1 do
  print_int (chiffre n i);
  print_string " ";
done;;

let montgomery (a : int) (n : int) : int =
  let a1 = ref a in
  let a2 = ref (a * a) in
  let p = nb_chiffres n in
  let i = ref (p-2) in
  while !i >= 0 do
    if chiffre n !i = 0 then begin
      a2 := !a1 * !a2;
      a1 := !a1 * !a1;
    end else begin
      a1 := !a1 * !a2;
      a2 := !a2 * !a2;
    end;
    decr i;
  done;
  !a1
;;

let montgomery (a : int) (n : int) : int =
  let rec aux (a1 : int) (a2 : int) (i : int) : int =
    match i with
    | _ when i < 0 -> a1
    | _ when chiffre n i = 0 -> aux (a1*a1) (a1*a2) (i-1)
    | _ -> aux (a1*a2) (a2*a2) (i-1)
  in
  aux a (a*a) ((nb_chiffres n) - 2)
;;

montgomery 13 4;;