(* $Id: projet.sml,v 1.4 2001/12/18 22:27:35 mycroft Exp mycroft $ ANDRE Mélanie MARIE Patrick Projet de Génie Logiciel, année de License 2001-2002 Responsable de projet: Christophe Cérin * Implantation des "grands entiers" * Implantation d'un type abstrait "séquence bitonique de grands entiers" * Implantation d'un tri (facultatif) *) (* Partie I, Implantation des "grands entiers" en SML. Cette partie propose une analyse simple et logique quant à l'utilisation d'un type composé pour la représentation d'un grand entier en SML. Les nombres entiers naturels sont les éléments de la suite illimitée zéro, un, deux, trois, quatre, etc... Ils servent à compter à dénombrer les objets. Zéro (d'invention tardive) ne fait pas exception si l'on accepte de dire "il y a zéro objets" pour dire qu'il n'y en a pas. Les nombres négatifs, notés avec un signe '-' (ex: -1, -2, ..) font aussi partis des nombres entiers. Le projet d'une implantation des "grands entiers" en SML porte sur le portage des entiers qui sont par défaut non gérés par SML (ou tout simplement par le système de calcul utilisé par la machine) car ceux ci sont limités en taille (par exemple, sur un systeme x86 intel actuel tournant sous linux ou sur un systeme FreeBSD, les entiers sont codés sur: mycroft@kiev ~> cat > taille_int.c #include int main(void) { printf("Taille d'un entier signé en octets: %d\n", sizeof(signed int)); printf("Taille d'un entier (long) en octets: %d\n", sizeof(long)); printf("Taille d'un entier (long long) en octets: %d\n", sizeof(long long)); } mycroft@kiev ~> gcc -w -o taille_int taille_int.c mycroft@kiev ~> ./taille_int Taille d'un entier signé en octets: 4 Taille d'un entier (long) en octets: 4 Taille d'un entier (long long) en octets: 8 mycroft@kiev ~> Le type long long est le type le plus grand géré par GCC (qui est le compilateur C/C++ du projet GNU (issu d'egcs). Un test de compilation sur le type "long long long" renvoit une erreur: `long long long' is too long for GCC Ceci dit, de base, on peut donc utiliser des nombres entiers variants de -2^16 à (2^16 - 1) pour des nombres codés sur 4 octets; et -2^32 à (2^32 - 1) pour des nombres codés sur 8 octets. .../... *) (* Ceci dit, de base, on peut donc utiliser des nombres entiers variants de -2^16 à (2^16 - 1) pour des nombres codés sur 4 octets; et -2^32 à (2^32 - 1) pour des nombres codés sur 8 octets. .../... Hors de ces limites, il est impossible de gérer des calculs de nombres plus grand (hors l'utilisation de bibliothèques/fonctions spéciales). Notre but, alors est de gérer un type nouveau pour la gestion de ces nombres en SML. Un nombre entier est représenté par une sucession de n nombres décimaux (nombres entiers entre 0 à 9 en base 10), et par un signe: [+/-] 12345678901234567890....1234567890134567657854542643 On a à créer un type qui va devoir gérer la liste des nombres et le signe. Pour le signe, on peut créer un type simple, comprenant les valeurs POS pour positif, et NEG pour négatif: *) datatype mon_signe = NEG | POS; (* Pour la suite de nombre, il faut au préalable réfléchir à comment on va effectuer les opérations arithmétiques addition, soustraction, multiplication et division. Pour une addition simple, on la fait ainsi: 123456 + 123 ------- On commence par calculer à partir du nombre des unités, puis des dizaines .. pour arriver aux termes des plus grands rangs. Il serait logique de représenter un entier par une liste d'entier ainsi: 1234 représenté par [1,2,3,4], mais alors lors des calculs il faudrait trouver le n'ieme élément de la liste pour faire une addition puis le n'ieme - 1 puis le n'ieme - 2 ... Il est alors plus simple de dire: Le chiffre des unités sera le 1er élément de la liste, le chiffre des dizaines le 2nde élément de la liste et ainsi de suite. On aura donc: 12345 représenté par [5,4,3,2,1] Pour les calculs en fonctionnels, du moins pour l'addition (que l'on verra juste après, on aura: 123456 + 123 ------- répresenté par [6,5,4,3,2,1] + [3,2,1], soit le début d'algorithme (qui ne gère ni les nombre négatifs ni les retenues pour l'instant): On prend le 1er élément de chaque liste qu'on additionne, puis récursivement on passe les 2 listes dans la meme fonction mais sans le 1er element de la liste et ainsi de suite. Cette représentation permet d'éviter de renverser 2 fois la liste à chaque nombre (un pour utiliser hd() et tl() et l'autre pour passer le résultat à l'appel de la fonction récursivement. On peut représenter un grand entier (juste la succession des nombres) par: *) type mes_nmbrs = int list; (* On peut tester notre type 'mes_nmbrs' en utilisant des valeurs communes: *) val l_zero = []; val l_un = [1]; val l_dix = [0, 1]; val l_cent = [0, 0, 1]; val l_mille = [0, 0, 0, 1]; (* Notre type pour représenter un grand nombre entier en SML sera alors: *) datatype mon_int = mon_nombre of { signe : mon_signe, nmbrs : mes_nmbrs }; (* Test de notre nouveau type grand entier avec les valeurs communes: *) (* 0 *) val gn_zero = mon_nombre {signe=POS, nmbrs=l_zero}; (* 1 *) val gn_un = mon_nombre {signe=POS, nmbrs=l_un}; (* 10 *) val gn_dix = mon_nombre {signe=POS, nmbrs=l_dix}; (* 100 *) val gn_cent = mon_nombre {signe=POS, nmbrs=l_cent}; (* 1000 *) val gn_mille = mon_nombre {signe=POS, nmbrs=l_mille}; (* -1000 *) val gn_moins_mille = mon_nombre {signe=NEG, nmbrs=[0, 0, 0, 1]}; (* -987654321 *) val gn_moins_nbr = mon_nombre {signe=NEG, nmbrs=[1, 2, 3, 4, 5, 6, 7, 8, 9]}; (* Avant de passer à une première approche de l'addition, on peut créer des fonctions de saisie de nombre du format 'lisible par l'être humaine' à notre type (fonctions ToString et FromString) val ToString : mon_int -> string val FromString : string -> mon_int *) (* Pour ToString, on a besoin d'une fonction qui va prendre les nombres et va renvoyer une chaine avec tout ces nombres. Pour cela, on a besoin d'une fonction qui va renvoyer une liste comportant uniquement le dernier élément. (last_elem) *) fun nbr_elem (x::y) = nbr_elem (tl(x::y)) + 1 | nbr_elem (nil) = 0; fun last_elem (l as (_::_)) = if (nbr_elem (l) = 1) then l else last_elem(tl(l)) | last_elem (nil) = nil; (* val NmbrsToString : mes_nmbrs -> string Nmbrs prend une liste de nombre et en ressort une chaine de caractères. On doit procéder du dernier élément vers le premier. *) fun NmbrsToString (nil) = "" | NmbrsToString (l as _::_) = Int.toString(hd(last_elem(l))) ^ NmbrsToString(rev(tl(rev(l)))); (* Test de NmbrsToString : *) NmbrsToString l_mille; NmbrsToString l_cent; NmbrsToString l_zero; (* val it = "1000" : string val it = "100" : string val it = "" : string On remarque que NmbrsToString ne gère pas le cas 0; on le traitera dans notre fonction ToString; pareillement pour le signe. *) fun ToString (mon_nombre{nmbrs=[], ...}) = "0" | ToString (mon_nombre{signe=NEG, nmbrs}) = "-" ^ NmbrsToString nmbrs | ToString (mon_nombre{signe=POS, nmbrs}) = "+" ^ NmbrsToString nmbrs; (* tests: *) ToString gn_mille; ToString gn_moins_mille; ToString gn_zero; (* Passons à la seconde fonction, FromString *) (* on peut avoir un nombre du genre -123456 ou +12345 ou 1245566 *) (* StringToNmbrs prend "12345" et renvoit [5, 4, 3, 2, 1] StringToNmbrs ne s'occupe pas du signe. *) fun StringToNmbrs "" = [] | StringToNmbrs (es:string) = rev(valOf(Int.fromString(implode([hd(explode(es)):char])))::rev(StringToNmbrs(implode(tl(explode(es)))))); fun VireZero([]) = [] | VireZero([0]) = [] | VireZero(x::l) = if (x = 0) then VireZero(l) else l ; fun FromString "" = mon_nombre{signe=POS, nmbrs=[]} | FromString (s:string) = if (hd(explode(s)) = #"-") then mon_nombre{signe=NEG, nmbrs=StringToNmbrs (implode(tl(explode(s))))} else if (hd(explode(s)) = #"+") then mon_nombre{signe=POS, nmbrs=StringToNmbrs (implode(tl(explode(s))))} else mon_nombre{signe=POS, nmbrs=StringToNmbrs s}; FromString "1234"; FromString "+1234"; FromString "-1234567789090"; (* On peut créer, à l'instar du type Int présent en natif dans SmlNj, les autres fonctions simples comme (avant de s'attaquer aux opérations arithmétiques): val SameSign : (mon_int * mon_int) -> bool *) fun signe_de (mon_nombre{signe=NEG, ...}) = NEG | signe_de (mon_nombre{signe=POS, ...}) = POS; fun SameSign (a, b) = signe_de a = signe_de b; fun ~ (i as mon_nombre{nmbrs=[], ...}) = i | ~ (mon_nombre{signe=NEG, nmbrs}) = mon_nombre{signe=POS, nmbrs=nmbrs} | ~ (mon_nombre{signe=POS, nmbrs}) = mon_nombre{signe=NEG, nmbrs=nmbrs}; fun abs (mon_nombre{nmbrs, ...}) = mon_nombre{signe=POS, nmbrs=nmbrs}; (* fonctions de comparaisons *) (* on va commencer par comparer 2 listes de nombres, indépendament du signe *) fun cmp_nmbrs ([], []) = EQUAL | cmp_nmbrs (_, []) = GREATER | cmp_nmbrs ([], _) = LESS | cmp_nmbrs (i::ri,j::rj) = case cmp_nmbrs (ri,rj) of EQUAL => if i = j then EQUAL else if i < j then LESS else GREATER | c => c; (* On prend le 1er element de chaque nombre (donc, le plus petit chiffre) et on compare les 2 listes tl() restantes; si ces 2 listes, apres la recursivitée renvoit EQUAL ([x, y, 9, 9] et [a, b, 9, 9]), alors on teste les plus petits ... sinon, on renvoit GREATER ou LESS ... *) fun compare (mon_nombre{nmbrs=[], ...}, mon_nombre{nmbrs=[], ...}) = EQUAL | compare (mon_nombre{nmbrs=[], ...}, mon_nombre{signe=POS, nmbrs}) = LESS | compare (mon_nombre{nmbrs=[], ...}, mon_nombre{signe=NEG, nmbrs}) = GREATER | compare (mon_nombre{signe=NEG, ...}, mon_nombre{signe=POS, ...}) = LESS | compare (mon_nombre{signe=POS, ...}, mon_nombre{signe=NEG, ...}) = GREATER | compare (mon_nombre{signe=POS, nmbrs=nbr1}, mon_nombre{signe=POS, nmbrs=nbr2}) = cmp_nmbrs (nbr1, nbr2) | compare (mon_nombre{signe=NEG, nmbrs=nbr1}, mon_nombre{signe=NEG, nmbrs=nbr2}) = cmp_nmbrs (nbr2, nbr1); compare (gn_mille, ~gn_mille); compare (FromString("+0"), FromString("-0")); (* les 4 opérateurs, on envoit à 'compare' les arguments recus, et on sort les résultats par un switch/case implicite *) fun op > arg = case compare arg of LESS => true | _ => false; fun op > arg = case compare arg of GREATER => true | _ => false; fun op <= arg = case compare arg of GREATER => false | _ => true; fun op >= arg = case compare arg of LESS => false | _ => true; (* Quelques exemples: *) gn_mille > gn_mille; gn_mille >= gn_mille; gn_mille > ~ gn_mille; (* Fin des fonctions de comparaisons *) (* min et max *) fun min (a, b) = if (a > b) then b else a; fun max (a, b) = if (a > b) then a else b; (* Nous arrivons maintenant à l'analyse des opérations arithmétiques. 1) Additions et Soustractions Nous traitons addtions et soustractions d'un bloc tout simplement car une addition entre un nombre positif et un nombre négatif revient à la soustraction entre le nombre positif par la valeur absolue du nombre négatif. On devra alors gérér tout les cas pour ces deux fonctions dépendament. *) (* 1ere fonction 'utile': l'addition entre 2 listes de nombres Cette fonction donnera une liste de nombres résultant d'une addition entre deux listes de nombres au format mes_nmbrs. Avant d'écrire la fonction, il y a encore un point qu'il ne faut pas omettre, c'est l'existance de retenues. En effet, on va addition les membres des 2 listes 2 à 2, mais le fait qu'on ne doit pas dépasser le nombre 9 pour chaques éléments de la liste. On va donc créer une fonction prenant en argument 3 éléments, les 2 listes commencant au n'ième élément (à cause de la récursivitée), et la retenue (si elle existait au n - 1 ième élément.) *) fun plus ([], [], 0) = [] | plus ([], [], n) = [n] | plus ([], x::l, ret) = ((x + ret) mod 10)::plus([], l, ((x+ret) div 10)) | plus (x::l, [], ret) = ((x + ret) mod 10)::plus(l, [], ((x+ret) div 10)) | plus (x::k, y::l, ret) = ((x + y + ret) mod 10)::plus(k, l, ((x + y + ret) div 10)); (* dans le meme esprit, on a besoin d'une fonction qui fasse la soustraction en une liste positive et une liste négative, avec la liste positive plus grande que la liste négative (en effet, 23 - 123 == - (123 - 23)). *) (* Les Int.compare sont la pour juste effectuer un ((x + ret) > x) .. > a été redéfini et est maintenant incompatible pour les entiers. *) fun moins ([], [], 0) = [] | moins ([], [], n) = [1] | moins ([], x::l, ret) = [] (* Ce cas ne doit pas et ne peut arriver. *) | moins (x::l, [], ret) = if (Int.compare (ret, x) = GREATER) then (10 + x - ret)::moins (l, [], 1) else (x - ret)::moins(l, [], 0) | moins (x::k, y::l, ret) = if (Int.compare (y + ret,x) = GREATER) then (10 + x - (y + ret))::moins(k, l, 1) else (x - (y + ret))::moins(k, l, 0); (* doit renvoyer [0, 0, 1]: *) moins ([3, 2, 1], [3, 2], 0); (* doit renvoyer [6, 6, 6]: *) moins ([9, 9, 9], [3, 3, 3],0); (* doit renvoyer [9, 9, 9]: *) moins ([0, 0, 0, 1], [1], 0); (* doit renvoyer [8,6,4,2,0,8,5,3,0,0]: *) moins ([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [1, 2, 3, 4, 5, 6, 7, 8], 0); (* Maintenant qu'on possède des fonctions d'addition "simple" et de soustraction "simple", on peut maintenant s'attaquer aux additions et soustrations de notre type mon_int, et gérer tout les cas. *) fun gn_add (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = mon_nombre{signe=NEG, nmbrs=plus(a, b, 0)} | gn_add (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = if (cmp_nmbrs(a,b) = GREATER) then mon_nombre{signe=NEG, nmbrs=moins(b, a, 0)} else mon_nombre{signe=POS, nmbrs=moins(a, b, 0)} | gn_add (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = if (cmp_nmbrs(a,b) = GREATER) then mon_nombre{signe=NEG, nmbrs=moins(a, b, 0)} else mon_nombre{signe=POS, nmbrs=moins(b, a, 0)} | gn_add (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = mon_nombre{signe=POS, nmbrs=plus(a, b, 0)}; fun gn_red (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = if (cmp_nmbrs(a,b) = GREATER) then mon_nombre{signe=NEG, nmbrs=moins(a, b, 0)} else mon_nombre{signe=POS, nmbrs=moins(b, a, 0)} (* la premiere partie est ok *) | gn_red (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = mon_nombre{signe=NEG, nmbrs=plus(a, b, 0)} (* la seconde partie est ok *) | gn_red (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = mon_nombre{signe=POS, nmbrs=plus(a, b, 0)} (* la troisieme partie est ok *) | gn_red (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = if (cmp_nmbrs(a,b) = GREATER) then mon_nombre{signe=POS, nmbrs=moins(a, b, 0)} else mon_nombre{signe=NEG, nmbrs=moins(b, a, 0)}; (* la quatrieme partie est ok *) (* Multiplications et divisions entieres *) fun fois_10 ([]) = [] | fois_10 (l) = 0::l; fun produit_c_ret (_, [], 0) = [] | produit_c_ret (_, [], ret) = [ret] | produit_c_ret (a, b::c, ret) = (((a * b) + ret) mod 10)::produit_c_ret(a, c, (((a * b) + ret) div 10)); fun produit_c (0, _) = [] | produit_c (c, l) = produit_c_ret (c, l, 0); fun produit ([], []) = [] | produit ([], _ ) = [] | produit (_, [] ) = [] | produit (x::l1, y::l2) = plus (produit_c(x, y::l2), fois_10(produit(l1, y::l2)), 0); fun gn_mul (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = mon_nombre{signe=POS, nmbrs=produit(a, b)} | gn_mul (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = mon_nombre{signe=NEG, nmbrs=produit(a, b)} | gn_mul (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = mon_nombre{signe=NEG, nmbrs=produit(a, b)} | gn_mul (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = mon_nombre{signe=POS, nmbrs=produit(a, b)}; (* Voir si il n'y a pas un algorithme plus intelligent *) fun division (x, y) = if cmp_nmbrs (x, y) = EQUAL then 1 else if cmp_nmbrs (x, y) = GREATER then 1 + division (moins (x, y, 0), y) else 0; fun div_inter (x, y) = if cmp_nmbrs (x, y) = GREATER then StringToNmbrs(Int.toString(division (x, y))) else if (cmp_nmbrs (x, y) = EQUAL) then [1] else [0]; exception divparzero; fun gn_div (mon_nombre{nmbrs=[0], signe=_}, _) = raise divparzero | gn_div (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = mon_nombre{signe=POS, nmbrs=div_inter (a, b)} | gn_div (mon_nombre{signe=POS, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = mon_nombre{signe=NEG, nmbrs=div_inter (a, b)} | gn_div (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=POS, nmbrs=b}) = mon_nombre{signe=NEG, nmbrs=div_inter (a, b)} | gn_div (mon_nombre{signe=NEG, nmbrs=a}, mon_nombre{signe=NEG, nmbrs=b}) = mon_nombre{signe=POS, nmbrs=div_inter (a, b)}; val t_1 = FromString("2048"); val t_2 = FromString("1024"); ToString(gn_mul (t_2, t_1)); ToString(gn_div (t_1, t_2)); (* quelques valeurs de tests: *) (* val t_1 = FromString("-1234"); val t_2 = FromString("1234"); val t_11= FromString("-1235"); val t_12= FromString("1235"); val t_3 = FromString("999"); val t_4 = FromString("-999"); ToString(gn_red(t_1, t_2)); ToString(gn_red(t_2, t_1)); ToString(gn_red(t_1, t_11)); ToString(gn_red(t_11, t_1)); ToString(gn_red(FromString("1"), FromString("-1"))); ToString(gn_red(t_11, t_11)); ToString(gn_red(t_12, t_12)); ToString(gn_red(t_3, t_1)); ToString(gn_red(FromString("1"), FromString("1"))); ToString(gn_red(FromString("2"), FromString("1"))); ToString(gn_red(FromString("1"), FromString("2"))); *) (* * Séquences bitoniques * *) (* * Indications: on doit tester dans un premier temps le nombre de "pentes" * différentes. Si il y en a 1 ou 2, alors la suite est forcement bitonique. * Si elle est de 3, il faut comparer le 1er et le dernier et l'élément, et * en fonction du sens de la 1ere pente on pourra dire si la séquence est * bitonique ou non. * * * * Si a (premier point) >= d (dernier point, suite bitonique) * / \ * Sinon, suite pas bitonique * * \ / * * * * * Si a (premier point) <= d (dernier point, suite bitonique) * * / \ Sinon, suite pas bitonique * \ / * * * *) datatype variation = croissant | decroissant; (* * Avec cette fonction on determine le 1er sens de variation de la séquence * *) fun prem_variant_way (nil) = croissant | prem_variant_way (x::y) = if (nbr_elem (x::y) = 1) then croissant else if (nbr_elem (x::y) = 2) then if (compare (x, hd(y)) = GREATER) then decroissant else if (compare (x, hd(y)) = LESS) then croissant else prem_variant_way (y) else prem_variant_way (y); (* * On compte le nombre de variations (de pentes). * *) fun variant_number (nil, _, _) = 0 | variant_number ([t], _, _) = 1 | variant_number (a::b, prec, croissant) = if (compare (a, prec) = LESS) then variant_number (b, a, decroissant) + 1 else variant_number (b, a, croissant) | variant_number (a::b, prec, decroissant) = if (compare (a, prec) = GREATER) then variant_number (b, a, croissant) + 1 else variant_number (b, a, decroissant); (* * Maintenant qu'on a le nombre de variations, on a plus qu'a * tester les différents cas: *) fun est_bitonique (nil) = true | est_bitonique ([a]) = true | est_bitonique (a::b) = let val variations = variant_number (a::b, a, prem_variant_way(a::b)) in if (variations = 0) then true else if (variations = 1) then true else if (variations = 2) then if (((compare (a, hd(b)) = LESS) andalso (prem_variant_way(a::b) = croissant)) orelse ((compare (a, hd(b)) = GREATER) andalso (prem_variant_way(a::b) = decroissant))) then false else true else false end val t1 = FromString("123"); val t2 = FromString("456"); val t3 = FromString("789"); val t4 = FromString("1012"); est_bitonique([t1, t2, t3, t4]); est_bitonique([t1, t2, t3, t4, t3, t1]); est_bitonique([t1, t2, t3, t4, t3, t1, t2]); est_bitonique([t1, t2, t3, t4, t3, t1, t2, t1]);