(* Exercice 1 *)

(* Question 1 : on doit trouver 1.02530490368186422 *)

let r2 = sqrt 2. in
(1. +. r2 +. r2 ** 3.) /. (1. +. exp r2) ;;

let th x =
  let e = exp x in
  let e' = 1. /. e in
  (e -. e') /. (e +. e')
;;

th 1. ;; (* 0.761594155955764851 *)

(* Exercice 2 *)

let a f = (f 0. +. f 1.) /. 2. ;;

(* avec des fonctions anonymes *)

let b f = fun x -> (f x) ** 2. ;;

let c f = fun x -> f (f x) ;;

let d f = fun x -> f (x +. 1.) ;;

(* avec la curryfication *)

let b f x = (f x) ** 2. ;;

let c f x = f (f x) ;;

let d f x = f (x +. 1.) ;;

(* Exercice 3 *)

let rec s n = 
  if n = 0 then 0
  else n + s (n-1)
;;

let s n =
  let rec aux n acc =
    if n = 0 then acc
    else aux (n-1) (acc+n)
  in aux n 0
;;

(* Exercice 4 *)

let rec puiss x n =
  if n = 0 then 1
  else x * puiss x (n-1)
;;

let puiss_term x n =
  let rec aux n acc =
    if n = 0 then acc
    else aux (n-1) (x*acc)
  in aux n 1
;;

puiss_term 2 10 ;; (* 1024 *)

let rec expo_rapide x n =
  if n = 0 then 1
  else let p = expo_rapide x (n/2) in
  if n mod 2 = 0 then p * p
  else x * p * p
;;

expo_rapide 2 10 ;; (* 1024 *)

(* Exercice 5 *)

let rec pgcd u v =
  if v = 0 then u
  else pgcd v (u mod v)
;;

pgcd 189 231 ;; (* 21 *)

(* Exercice 6 *)

let rec nb_chiffres b n =
  if n = 0 then 0
  else 1 + nb_chiffres b (n/b)
;;

nb_chiffres 10 999 ;; (* 3 *)

nb_chiffres 10 1000 ;; (* 4 *)

let rec mystere f n m =
  if n > m then 1.
  else f (float_of_int n) *. mystere f (n+1) m
;;

let rec fibo n =
  if n <= 1 then 1
  else fibo (n-1) + fibo (n-2)
;;

fibo 5 ;; (* 8 *)

(* #trace fibo ;; *)

fibo 5 ;;

(* #untrace fibo ;; *)

(* Exercice 9 : Algorithme de Floyd *)

let f x = (x*x + 92) mod 32069 ;;

f 8 ;;

(* Q1 *)
let rec itere f x0 n =
  if n = 0 then x0
  else f(itere f x0 (n-1))
;;

(* Q2 *)
let rec itereBis f x0 n =
  if n = 0 then x0
  else itereBis f (f x0) (n-1)
;;

(* Q3 *)
let floyd1 f x0 =
  let rec floydAux f x y =
    if x = y then x
    else floydAux f (f(x)) (f(f(y)))
  in floydAux f (f(x0)) (f(f(x0)))
;;

floyd1 f 33 ;; (* 11326 *)

(* Q4 *)
let floyd2 f x0 =
  let rec floydAux f x y acc =
    if x = y then acc
    else floydAux f (f(x)) (f(f(y))) (acc+1)
  in floydAux f (f(x0)) (f(f(x0))) 1
;;

floyd2 f 33 ;; (* 320 *)

(* Q6 *)
let periode f x0 =
  let i = floyd2 f x0 in
  floyd2 f (itere f x0 i)
;;

periode f 33 ;; (* 8 *)

(* Q7 *)
let prePeriode f x0 =
  let xi = floyd1 f x0 in
  let rec aux mu x y =
    if x = y then mu
    else aux (mu+1) (f x) (f y)
  in aux 0 x0 xi
;;

prePeriode f 33 ;; (* 313 *)

(* Q8 *)
let brent f x0 =
  let rec brentAux f i j xi xj =
    if xi = xj then (i,j)
    else if j <= 2*i then brentAux f i (j+1) xi (f xj)
    else brentAux f j (j+1) xj (f xj)
  in brentAux f 0 1 x0 (f x0)
;;

brent f 33 ;; (* 511, 519 *)