Arithmétique |
L'éditeur du cours est emacs, la méthode de compilation recommandée est la compilation sous emacs. Son avantage est le positionnement automatique sur les erreurs détectées lors de la compilation. Voici comment procéder.
Cet algorithme de calcul du PGCD de deux entiers naturels est bien connu. Il repose sur les deux identités :
| pgcd (u, v) | = | v | si v divise u |
| pgcd (u, v) | = | pgcd (v, u mod v) | sinon |
Écrire une fonction pgcd de type int -> int -> int qui
calcule le pgcd selon la méthode d'Euclide.
Pour tester votre fonction vous pouvez copier-coller son code dans le toplevel ocaml, puis procéder à quelques appels :
… (* code de pgcd *) val pgcd : int -> int -> int = <fun> # pgcd 123 321;; - : int = 3 # pgcd 101 203;; - : int = 1 #
Ce que vous tapez est en noir, ce que le toplevel raconte est est gris.
Mais cette technique devient vite malcommode. Il vaut mieux écrire des programmes complets (stand-alone). Partez donc de ce programme somme.ml qui affiche la somme des deux arguments (entiers) donnés sur la ligne de commande. Appelez le fichier pgcd.ml, remplacez la fonction somme par votre fonction pgcd, compilez (sous emacs) par
ocamlc -o pgcd pgcd.ml
(Les options de la commande ocamlc sont décrites dans le manuel.) Ensuite, dans une fenêtre shell, vous pouvez tester.
% ./pgcd 1111 1234 1 % ./pgcd 1234 1111 1
Lorsque je fréquentais le collège, on ne m'avait pas appris l'algorithme d'Euclide. Je calculais le PGCD différemment : en decomposant les nombres u et v en facteurs premiers, puis en identifiant les facteurs communs.
Je vais m'inspirer de la technique apprise au collège. Je suppose connue la suite des nombres premiers p1, p2, p3 etc. (c'est-à-dire 2, 3, 5, etc.) L'idée est d'essayer de diviser u par les nombres premiers pris dans l'ordre p1, p2, …
| décompose (1, pj…) | = | ∅ | ||
| décompose (u, pj…) | = | pj décompose (u / pj, pj…) | si pj divise u | |
| décompose (u, pj…) | = | décompose (u, pj+1…) | si pj ne divise pas u |
Notez que dans la définition « théorique » décompose, on
prend quelques libertés avec les notations des séquences.
En Caml, les séquences sont représentées par des listes, la liste vide est
"[] et on ajoute l'élément x en tête de la liste s par
x::s.
En fait, l'algorithme fonctionne toujours si on remplace la suite des pj par une suite croissante, commençant à 2 et qui contient les nombres premiers (les pj, donc). En effet, par construction et à chaque étape, u n'est divisible par aucun des qk avec k < j, et donc u n'est pas non plus divisible par un nombre premier strictement inférieur à qj. Donc, si qj est un diviseur de u, alors qj n'a pas de facteur premier strictement plus petit que qj, c'est à dire qj est premier.
Si on veut optimiser un peu, on peut choisir la suite définie par
afin d'éviter de tester les entiers pairs à partir de 4.
On peut aussi terminer plus rapidement. Soit qj tel que v, résultat de la divison euclidienne de u par qj, est strictement plus petit que qj, alors u est premier. En effet, d'une part, v < qj entraîne qj × qj > u (u = qj × v + r avec r < qj et v < qj. et donc u < qj × (v + 1) ≤ qj × qj), et d'autre part, la définition de décompose entraîne que u n'est divisible par aucun nombre pris dans [2…qj[. Soit f tel que 2 ≤ f et f × f ≤ u, alors on a nécessairement f < qj (sinon, f × f ≥ qj × qj > u). Soit finalement f n'est pas un facteur de u. Or, si u n'est pas premier, alors il existe deux nombres f et g, avec 2 ≤ f ≤ g et u = f × g. Et donc, u possède un diviseur propre f, avec f × f ≤ u. Bref, on peut ajouter la règle :
| décompose (u, qj…) | = | u | si u/qj < qj |
Écrire une fonction decompose de type
int -> int list qui prend un entier u non nul en argument et renvoie
la liste de ses facteurs premiers.
Il est conseillé d'écrire une fonction auxiliaire préalable qui suit la définition « théorique » décompose, mais prend en argument la valeur courante de u et qj (le premier élément de la séquence restante). Dans un premier temps, on peut s'abstenir des optimisations signalées.
On pourra modifier le programme tous.ml qui affiche les entiers de 2 à l'entier passé sur la ligne de commande. Vous devriez obtenir par exemple :
% ./decompose 524287 524287 % ./decompose 1048575 3 5 5 11 31 41 % ./decompose 2097151 7 7 127 337
Donc il suffit maintenant d'identifier les facteurs communs à u et v et de les multiplier entre eux pour retrouver le pgcd.
int list -> int list -> int list qui prend en argument deux
listes d'entiers triées selon l'ordre croissant et qui renvoie
la liste des entiers communs aux deux listes.
Il convient de profiter de l'ordre des listes pour écrire une fonction
de coût linéaire en la somme des longueurs de ses arguments.
Attention, la bonne façon de décomposer les listes en Caml est
d'utiliser le filtrage.
int list -> int qui renvoie le produit des éléments de la liste
passée en argument. Trouver une convention raisonnable pour le cas de
la liste vide.
Nous disposons maintenant de deux fonctions pour calculer le pgcd. Écrire un programme qui prend deux arguments M et n sur la ligne de commande.
Ce programme doit procéder à n essais, consistant en un tirage pseudo aléatoire de deux entiers u et v compris entre 1 et M (voir Random.int), au calculs du pgcd selon les deux méthodes et à leur comparaison.
En cas d'échec le programme doit afficher un message explicatif. La fonction Printf.printf permet de composer de beaux messages. Pour afficher un beau message donnant le contenu de la variable i on procède ainsi :
On aura ainsi par exemple :
% ./verification 10000000 10000 Vérification, 10000 essais, sur [1..10000000] Que des succès
Les décompositions en facteurs premiers de u et v permettent de trouver la décomposition du ppcm (Plus Petit Commun Multiple) de u et de v.
Modifier un peu votre programme pour qu'il trouve et affiche le PPCM.
This document was translated from LATEX by HEVEA.