TP 6 : Types construits

Dépassement d'entier (integer overflow)¶

On considère le type suivant :

In [2]:

type entier = Infini | MoinsInfini | Entier of int
type entier = Infini | MoinsInfini | Entier of int

Out[2]:

type entier = Infini | MoinsInfini | Entier of int

On rappelle que max_int est le plus grand entier représentable en OCaml et min_int le plus petit :

In [24]:

max_int;;
min_int;;
max_int + 1;;  (* un dépassement du plus grand entier donne le plus petit *)
max_int;;
min_int;;
max_int + 1;;  (* un dépassement du plus grand entier donne le plus petit *)

Out[24]:

- : int = 4611686018427387903

Out[24]:

- : int = -4611686018427387904

Out[24]:

- : int = -4611686018427387904

Exercice

On voudrait pouvoir additionner deux entier $a$ et $b$ en prennant en compte les dépassements d'entier, et en donnant Infini dans ce cas.

Pourquoi ne peut-on pas tout simplement tester si $a + b >$ max_int ?
Pourquoi peut-on tester à la place si max_int $ - ~a \leq b$ avec $a \geq 0$ ?
Quel test similaire pourrait-on utiliser pour savoir si $a + b <$ min_int ?
Écrire une fonction add_int : int -> int -> entier telle que add_int ajoute 2 inten tenant compte des dépassements (on renvoie Infini s'il y a un dépassement de max_int et MoinsInfini s'il y a un dépassement de min_int par le bas).
Écrire une fonction add : entier -> entier -> entier ajoutant 2 entiers en tenant compte des dépassements.
On pourra écrire failwith "Indeterminé" dans le cas d'une forme indéterminé.
Écrire une fonction oppose : entier -> entier renvoyant l'opposé d'un entier. Par exemple, oppose Infini renvoie MoinsInfini, oppose (Entier a) renvoie Entier (-a)...
Écrire une fonction sub effectuant la soustraction.

Solution

Par définition, aucun entier ne peut être supérieur à max_int.
Déjà, $a + b >$ max_int implique que $a \geq 0$ (car $b$ est un entier dans est inférieur à max_int). De plus max_int $- a$ n'effectue pas de dépassement. Donc le test fonctionne sans risque de dépassement.
$a + b < $min_int se réécrit en $a < 0$ et min_int$ - a > b$.

Solution

In [3]:

(* 4. *)

let add_int a b =
  if a >= 0 && max_int - a <= b then Infini 
  else if a <= 0 && min_int - a >= b then MoinsInfini
  else Entier (a + b);;

add_int 4611686018427387900 2;;
add_int 4611686018427387900 5;;
add_int 4611686018427387900 (-5);;
add_int (-4611686018427387904) 5;;
add_int (-4611686018427387904) (-1);;

(* 5. *)

let add n p = match n, p with
  | Infini, MoinsInfini | MoinsInfini, Infini -> failwith "Indeterminé"
  | Infini, _ | _, Infini -> Infini  
  | MoinsInfini, _ | _, MoinsInfini -> MoinsInfini
  | Entier a, Entier b -> add_int a b;;

add Infini (Entier 10);;
add (Entier 10) (Entier 4611686018427387895);;

(* 6 *) 
let oppose n = match n with
    | Infini -> MoinsInfini
    | MoinsInfini -> Infini
    | Entier a -> Entier (-a);;
    
(* 7 *)
let sub n p = add n (oppose p);;

sub Infini (Entier 10);;
sub (Entier (-4611686018427387899)) (Entier 10);;
(* 4. *)

let add_int a b =
  if a >= 0 && max_int - a <= b then Infini 
  else if a <= 0 && min_int - a >= b then MoinsInfini
  else Entier (a + b);;

add_int 4611686018427387900 2;;
add_int 4611686018427387900 5;;
add_int 4611686018427387900 (-5);;
add_int (-4611686018427387904) 5;;
add_int (-4611686018427387904) (-1);;

(* 5. *)

let add n p = match n, p with
  | Infini, MoinsInfini | MoinsInfini, Infini -> failwith "Indeterminé"
  | Infini, _ | _, Infini -> Infini  
  | MoinsInfini, _ | _, MoinsInfini -> MoinsInfini
  | Entier a, Entier b -> add_int a b;;

add Infini (Entier 10);;
add (Entier 10) (Entier 4611686018427387895);;

(* 6 *) 
let oppose n = match n with
    | Infini -> MoinsInfini
    | MoinsInfini -> Infini
    | Entier a -> Entier (-a);;
    
(* 7 *)
let sub n p = add n (oppose p);;

sub Infini (Entier 10);;
sub (Entier (-4611686018427387899)) (Entier 10);;

Out[3]:

val add_int : int -> int -> entier = <fun>

Out[3]:

- : entier = Entier 4611686018427387902

Out[3]:

- : entier = Infini

Out[3]:

- : entier = Entier 4611686018427387895

Out[3]:

- : entier = Entier (-4611686018427387899)

Out[3]:

- : entier = MoinsInfini

Out[3]:

val add : entier -> entier -> entier = <fun>

Out[3]:

- : entier = Infini

Out[3]:

- : entier = Infini

Out[3]:

val oppose : entier -> entier = <fun>

Out[3]:

val sub : entier -> entier -> entier = <fun>

Out[3]:

- : entier = Infini

Out[3]:

- : entier = MoinsInfini

Pour savoir si $a \times b$ fait un dépassement, on propose la façon suivante :

Calculer $c = a \times b$
Regarder si $c/a$ est égal à $b$

Pourquoi cela fonctionne ? À quelle autre erreur faut-il faire attention dans cette méthode ?
En déduire une fonction mult : entier -> entier -> entier multipliant 2 entiers en tenant compte des dépassements.

Tableaux dynamiques¶

Il est impossible d'ajouter ou supprimer un élément dans tableau (array) en OCaml.
Les tableaux dynamiques (ou : redimensionnables) permettent d'ajouter un élément e, en recréant un tableau plus grand dans lequel on recopie tous les éléments ainsi que e.
Voici la définition de tableau dynamique que nous allons utiliser :

In [40]:

type 'a array_dyn = {mutable t : 'a array; mutable n : int};;
type 'a array_dyn = {mutable t : 'a array; mutable n : int};;

Out[40]:

type 'a array_dyn = { mutable t : 'a array; mutable n : int; }

n indique le nombre de cases du tableau t que l'on considère comme faisant partie du tableau dynamique. Les indices au delà de n dans t sont ignorés.
À chaque fois que l'on voudra ajouter un élément e à un tableau dynamique d :

s'il reste de la place dans d.t (c'est à dire si d.n < Array.length t), on met e dans e dans d.t.(n) et on met à jour d.n
sinon, on créé un nouveau tableau t' de taille 2n, on recopie d.t dedans, on ajoute e puis on remplace d.t par t'.

Exercice

Écrire une fonction add ajoutant un élément dans un array_dyn.
Quelle est la complexité dans le pire cas de add ?
On suppose que l'on ajoute $n$ éléments (avec add à un tableau dynamique de taille initiale 1. Montrer que la complexité totale de ces $n$ opérations est O($n$) (autrement dit, la complexité moyenne ou complexité amortie d'une opération est O(1))

Solution

In [53]:

(* 1 *)
let copy t1 t2 = (* copie t1 dans t2 *)
  for i = 0 to Array.length t1 - 1 do
    t2.(i) <- t1.(i)
  done;;

let add e d =
  if d.n < Array.length d.t then (d.t.(d.n) <- e; d.n <- d.n + 1)
  else if d.n = 0 then (d.t <- [|e|]; d.n <- 1)
  else (let t' = Array.make (2*d.n) d.t.(0) in
        copy d.t t';
        t'.(d.n) <- e;
        d.t <- t';
        d.n <- d.n + 1);;

let d = {t = [||]; n = 0};;
for i = 0 to 10 do
  add i d
done;
d
(* 1 *)
let copy t1 t2 = (* copie t1 dans t2 *)
  for i = 0 to Array.length t1 - 1 do
    t2.(i) <- t1.(i)
  done;;

let add e d =
  if d.n < Array.length d.t then (d.t.(d.n) <- e; d.n <- d.n + 1)
  else if d.n = 0 then (d.t <- [|e|]; d.n <- 1)
  else (let t' = Array.make (2*d.n) d.t.(0) in
        copy d.t t';
        t'.(d.n) <- e;
        d.t <- t';
        d.n <- d.n + 1);;

let d = {t = [||]; n = 0};;
for i = 0 to 10 do
  add i d
done;
d

Out[53]:

val copy : 'a array -> 'a array -> unit = <fun>

Out[53]:

val add : 'a -> 'a array_dyn -> unit = <fun>

Out[53]:

val d : '_weak10 array_dyn = {t = [||]; n = 0}

Out[53]:

- : int array_dyn =
{t = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 0; 0; 0; 0; 0|]; n = 11}

Solution

Dans le pire cas, add e d demande de recopier les n valeurs de d.t, d'où une complexité O(n).
Il y a des recopies quand d.n sera égal à 1, 2, 4, 8, ... c'est à dire pour les puissances de 2. $$\sum_{k=0}^{\lfloor \log_2(n) \rfloor} 2^k = ... = O(2^{\lfloor \log_2(n) \rfloor}) = O(n)$$ (on a utilisé la formule de la somme des termes d'une suite géométrique)