(* Fractions continues *)

(* On part d'une réel x : il s'écrit x=E+f
	avec E sa partie entière
        f sa partie fractionnaire : f<1 donc f=1/y avec y>1
On recommence avec y jusqu'à la précision voulue (f<=epsilon) *)

(* On définit un type rationnel et les fonctions qui permettent de récupérer le numérateur et le dénominateur d'un rationnel *)
type ratio={n:int;d:int};;

let affich_rat q = print_int q.n; print_string " / "; print_int q.d; print_newline();;
let eval_rat q = (float_of_int q.n) /. (float_of_int q.d);;

(* On définit la fonction e qui renvoie la partie entière d'un réel *)
let e = function x ->
	let t=int_of_float x in
		if x>=0. then t
		else if x=float_of_int t then t
					   	 else t-1
;;
(* Quelques tests !!! *)
List.map e [1.;-.3.;5.2;-.6.3];;

(* On définit la fonction pgcd qui renvoie le pgcd de deux entiers *)
let rec pgcd m n = let r= m mod n in
	if r = 0 then n else pgcd n r
;;
(* Quelques tests !!! *)
List.map2 pgcd [1; 6; 5; 2; -6] [13; 3; 25; 24; 3];;

(* On définit la fonction simply qui met un rationnel sous forme irréductible *)
let simply {n=a; d=b} = let c=pgcd a b in {n=a/c; d=b/c};;

(* Définition de quelques constantes
	_ nmax : Nbre maxi d'itérations (au delà de 15, ça ne marche plus) !!!
	_ eps : Précision demandée *)
let nmax=11 and eps=1e-12;;

(* Algorithme de fractions continues récursif *)
let frac_con x =
	let rec rfc x n= let t=e(x) and frac=x-.(float_of_int (e(x))) in
		if (frac<=eps or n=nmax) then {n=t;d=1}
		else let y=rfc (1./.frac) (n+1) in {n=t*y.n + y.d; d=y.n} 
in rfc x 0;;

let temp=frac_con (4.*.atan(1.)) in
	affich_rat temp;
	eval_rat temp
;;