Calculs d'intervalles d'entiers, opérations arithmétiques (projet no. 1)

C possède 8 types entiers: int, char, short, long qui sont des types signés, et leurs équivalents non signés, précédés du mot-clé unsigned. (Bon, en réalité char n'est pas spécifié en ANSI C comme étant signé ou non; on suppose ici qu'il est signé. On a fait d'autres hypothèses ici, comme le fait que les entiers étaient représentés en complément à deux.)

Les entiers d'un type entier T signé sont des entiers dans l'intervalle [-2N-1, 2N-1-1], où N est le nombre de bits du type T. Par exemple, int est typiquement 32 bits sur les ordinateurs actuels. Les entiers d'un type entier T non signé sont eux dans l'intervalle [0, 2N-1], où N est encore le nombre de bits de T.

Les types C T sont définis sous forme du type Caml q_ctype dans le module cparse.ml. Les types entier sont TINT, ..., TUNSIGNED_LONG. Un autre module fournissant des fonctions utiles à ce projet est arith.ml. Notamment, Arith.int_type_info T retourne un record, de type int_type, dont les champs sont: Ces constantes sont de type float en OCaml, et non int comme on aurait pu s'y attendre. La raison principale est que le type int de OCaml ne permet pas de représenter tous les entiers machines: ils ne vont que de -230 à 230-1 sur une architecture 32 bits.

Remarque Il faut faire attention à certains aspects du calcul en flottant en OCaml (en fait, en général). En premier, il y a deux nombres flottants nuls, 0.0 et -0.0; si vous voulez tester qu'un nombre flottant x est nul, utilisez la fonction float_is_zero du module Arith, n'écrivez pas ``x=0.0''. Ensuite, quand vous effectuez des calculs en flottants pour représenter des calculs d'entiers, n'oubliez pas que la division entière calcule le quotient de la division réelle, c'est-à-dire la partie entière de la division réelle.

La fonction round_to_int arrondit un flottant en entier, et effectue le cast y = (int)x où x est un flottant (de type C float ou double). Les débordements ne sont pas vérifiés; pour vérifier les débordements, utiliser round_to_int_range, qui calcule modulo la largeur du type entier considéré: round_to_int_range it x, où it est un int_type et x un float, retourne le résultat du cast de x à un entier décrit par it.

Remarque L'intervalle [a,b] est représenté par la valeur Caml ITV (a,b), si a£ b; sinon, par ITV_EMPTY. La fonction itv, du module Intervalle, prend a et b en argument et retourne la bonne représentation de l'intervalle [a,b]: utilisez-la donc, de préférence au constructeur ITV, pour construire des intervalles.

Votre but est de réaliser les fonctions décrites dans itv_int.mli. La sémantique des opérations arithmétiques de C est la suivante. Dans certains cas, on a précisé la sémantique telle qu'elle est réalisée sur les plateformes Linux à processeur Intel.

Addition
Étant donnés deux entiers x et y, x+y calcule la somme de x et de y, modulo la largeur du type de x, y et du résultat---au sens de la fonction round_to_int_range décrite plus haut.

Calcul de l'opposé
-x calcule l'opposé de x, modulo la largeur du type T de x, au sens de la fonction round_to_int_range décrite plus haut. Noter que, dans le cas où T est signé, l'opposé d'un nombre x négatif est positif, sauf quand x=T.it_min, auquel cas -x vaut encore Tit_min. Lorsque T est non signé, -x calcule T.it_range-x---de nouveau modulo la largeur de T.

Multiplication
x*y calcule le produit de x et y, modulo la largeur du type T de x, y et du résultat, encore au sens de la fonction round_to_int_range décrite plus haut. On pourra calculer le produit de deux intervalles [a,b] et [c,d] en calculant l'intervalle produit en ignorant les débordements dans un premier temps, et en retournant l'intervalle [T.it_min, T.it_max] s'il y a eu débordement.

Quotient
x/y calcule le quotient de x par y. Ceci déclenche une exception dans les deux cas suivants: soit y=0 (division par zéro), soit le type est non signé, x=c_minint et y=-1 (débordement arithmétique, cf. le calcul de -x quand x=c_minint, sauf qu'ici une exception est déclenchée). On demande d'écrire une fonction calculant le quotient d'intervalles [a,b] par [c,d] en retournant l'intervalle des valeurs possibles des quotients dans les cas ne déclenchant pas d'exception, et un booléen vrai si et seulement si l'un des quotients possibles x/y, xÎ [a,b], yÎ [c,d], déclenche une exception. Pour l'intervalle des quotients sans exception, on pourra distinguer les cas signé/non signé. Dans le cas signé, les cas c³ 1, d£ -1, puis le cas général c£ 0 et d³ 0, en remarquant qu'alors [a,b] /#[c,d] est le sup de [a,b] /#[c,-1] et de [a,b] /#[1, d]. Noter que la partie entière utilisée dans le calcul du quotient est telle que celle de 31 / 4 est 7 mais celle de -31 / 4 est -7, alors que la partie entière mathématique de 31 divisé par 4 serait -8: l'idée c'est que la division entière de m par -n doit être l'opposé de celle de m par n.

Reste
x%y calcule le reste de la division de x par y. Cette opération est notoirement difficile à abstraire. On pourra se contenter de calculer une approximation correcte comme suit. D'abord, une approximation correcte de [a,b] %#[c,d] est [a,b] -#([a,b] /#[c,d]) *#[c,d]. (Pourquoi? Justifier.) Une autre approximation correcte est que, dans les cas ne déclenchant pas d'exception, [a,b] %#[c,d] est au plus [min (0, c+1), max (0, d-1)]; ceci est parce que x % y est entre 0 et y-1 si y>0, entre y+1 et 0 si y<0. On pourra alors retourner l'infimum des deux approximations. Pouvez-vous trouver plus précis?

Conversion entre types entiers
La fonction itv_int_convert doit convertir un intervalle d'entiers vers un type spécifié par un int_type. Ceci consiste à ramener les entiers de l'intervalle donné modulo la largeur du type donné, au sens de la fonction round_to_int_range.

Conversion d'intervalle flottant vers entier
C'est la fonction itv_int_convert_float. Pour plus de détails sur les intervalles flottants, voir le projet des intervalles flottants. Noter qu'un NaN se convertit toujours en un entier unique, mais celui-ci peut varier: on considérera donc qu'un NaN peut se convertir en n'importe quel entier.

This document was translated from LATEX by HEVEA.