Arithmétique






Contexte informatique
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.
  1. Récupérez ceci à mettre à la fin du fichier .emacs dans votre répertoire personnel.
  2. Les étapes suvantes sont à faire sans réfléchir, une fois tapé le code (là il fallait réfléchir).
    1. Demander la compilation, (par Control-x Control-x, ou par le menu selon le mode emacs installé, ou encore par Escape x compile, qui fonctionne toujours). Vous pouvez alors éditer la ligne du bas pour y mettre votre commande de compilation.
    2. Lancer la compilation, en tapant sur la touche Return.
    3. En cas d'erreur, le curseur se positionnera tout seul sur le bout de source coupable, (Si il y plusieurs messages d'erreur, on passe à l'erreur suivante par Control-x ` ou encore en positionnant le curseur sur la première ligne d'un message d'erreur et en appuyant sur Return.)
  3. Réfléchissez maintenant, le message d'erreur sous les yeux, le curseur positionné là où le compilateur a détecté l'erreur.
1 Algorithme d'Euclide
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
Solution.

2 Une autre technique pour le PGCD
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 :
décompose(i, 1) =     
décompose(i, u) = pi décompose(i, u/pi)    si pi divise u
décompose(i, u) = décompose(i+1, u)    si pi ne divise pas u
Notez que dans la définition « théorique » décompose, on prend quelques libertés avec les notations des listes. En Caml, la liste vide est [] et on ajoute l'élément x en tête de la liste xs par x::xs.

En fait, l'algorithme fonctionne toujours si on remplace la suite des pi par une suite croissante, commençant à 2 et qui contient les nombres premiers (les pi, 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
q1 = 2,    q2 = 3,    qj+1 = qj+2 (j ≥ 2)
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(i, u) = u    si u/qj < qj

2.1 Décomposer en facteurs premiers
Écrire une fonction decompose de type int -> int list qui prend un entier u 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 qi et la valeur courante de u. 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
Solution.

2.2 Retrouver le PGCD
Donc il suffit maintenant d'identifier les facteurs communs à u et v et de les multiplier entre eux pour retrouver le pgcd.
  1. Écrire une fonction communs de type 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.
    Solution.
  2. Écrire une fonction produit de type 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.
    Solution.
  3. En déduire une fonction qui calcule le pgcd de deux entiers selon la méthode que j'avais apprise au collège.
    Solution.
3 Vérification
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 :
Printf.printf "i=%d\n" i (* «\n» est le retour à la ligne *)

On aura ainsi par exemple : 
% ./verification 10000000 10000
Vérification, 10000 essais, sur [1..10000000]
Que des succès
Solution.

4 Le PPCM comme au collège
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.
Solution.

Ce document a été traduit de LATEX par HEVEA et HACHA.